Need help in the optimization

[Thomas1965]

How fast does your code run ?
How fast should it be ?

[Thomas1965]

Put this at top of main, it will speed up input quite a bit.

  std::cin.sync_with_stdio(false); 
  std::cin.tie(nullptr);

[jlb]

I doubt very much that the above will be sufficient.

Start by writing a program that is not using non-legal constructs, such as:

    cin>>n>>m;
    ll a[n],b[n],c[n];

The above is not legal in C++, array sizes must be compile time constants. By the way are you sure using arrays is necessary?

Second use meaningful variable names, it'll make your program much easier to read and maybe even make it possible to follow the program logic.

Third stop using silly type defs like: typedef long long int ll;, just say what you need.

Fourth since this is C++ define and initialize your variables close to first use instead of one big glob at the beginning on some scope.

What is the maximum value of m and n?

Are you sure you're not overflowing the size of your long long int in any of your calculations?

[Thomas1965]

I think to solve such tasks properly you need to have proper understanding of algorithms and data structures.
https://www.amazon.co.uk/Guide-Competitive-Programming-Algorithms-Undergraduate/dp/3319725467/ref=sr_1_1?ie=UTF8&qid=1538914213&sr=8-1&keywords=competitive+programming

https://www.amazon.co.uk/Algorithms-Data-Structures-Competitive-Programming-ebook/dp/B078VB4HDY/ref=sr_1_3?ie=UTF8&qid=1538914213&sr=8-3&keywords=competitive+programming

https://medium.com/@andreimargeloiu/how-to-prepare-for-competitive-programming-396d557e0c12

https://www.udemy.com/introduction-to-algorithms-and-data-structures-in-c/

[MikeyBoy]

@burada
If you're brand new to programming, and don't understand the question, then why on earth are you trying to tackle competitive programming challenges?

[jonnin]

if you are optimizing ...

n=int(raw_input) -1
n=n-1 //rolled into above.
y=n%26
z=n//26
if(y<2): //better comparison
print(2**z, 0, 0)
elif(y<10): //y already checked against 2 in the previous if, and comparisons cost
print(0, 2**z, 0) //do you need a lookup table of powers of 2 for these?
else:
print(0, 0, 2**z)

[kanken]

how can we apply binary search to find the maximum range in hmappy, can somebody please help ?

[Dum]

I got 100 in digit sum and circles question.
I could give hints for both questions in return to hints for HMAPPY

[keskiverto]

What are these competitive programming challenges anyway?

Are you supposed to show the extent of your knowledge in there? If you demonstrate that you know nothing, that is also a success (in showing what you actually know).


Lets say that I would participate. To win, of course. It would then be in my interest to sabotage every rival by offering "help", wouldn't it?

[ne555]

to jab1jaby, iamdad6, shinok1, maxdaen, Dum:
create your own damn thread and provide all the info there (like, for example, the problem statement)


@op: read the limits of your problem
1≤N≤10^5
0≤M≤10^18
you decided to traverse M doing N operations each time, so 1e23 in total, that's too much
you need to change your approach to have 10e6 at most, so perhaps O(n lg n)

[kanken]

@ne555, im referring to the same problem posted by @beauty01.

[ne555]

¿how the hell I'm supposed to guess that its name?

for binary search
say that the answer is x, now simply verify if you can reach x
so traverse the array giving balloons to make sure that the cost does not exceed x in all the days. If you don't run out of ballons then it was possible and you may decrease `x', else you need to increase it

low = 0
high = M
while low < high:
   answer = floor( (low+high)/2 )
   if posible(demand, cost, balloons, answer):
      low = answer
   else:
      high = answer

the order then would be O(N lg M) which is quite good

[kanken]

@ne555 , what should i take 'x' as initially?
and ty for the reply.

[ne555]

> what should i take 'x' as initially?
suppose that you give no balloons at all, that would be the maximum possible cost, the upper limit.
may start at limit/2

by the way, the pseudocode fails in corner cases, fix that first.

[ne555]

@new accounts: please be a little more specific with what you don't understand, I don't want to repeat myself.

edit: also, don't pm me, use this thread.

[kanken]

..

[MikeyBoy]

If this is a Codechef problem, you should know that the Codechef adjudicators are aware of this forum, and that people use it to cheat on their contests. If you use this forum to try and cheat, you run the risk of being disqualified.

[Thomas1965]

@MikeyBoy,
yes it's an ongoing challenge. https://www.codechef.com/OCT18B/problems/HMAPPY
Actually quite a hard one - success rate so far 5.45

[MikeyBoy]

Well, the more people who use this forum to cheat, the more disqualifications there will be, and the lower that success rate will be...

[keskiverto]

I prefer Rhett Butler's solution.