GreenGrape's blog

By GreenGrape, 20 months ago, translation, In English,
Tutorial is loading...

Code: 36605296

Tutorial is loading...

Code: 36605336

Tutorial is loading...

Code: 36605356

Tutorial is loading...

Code: 36605449

Tutorial is loading...

Code: 36605502

Tutorial is loading...

Code: 36605519

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

It would be a good idea to add tutorial link in contest page.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what does the function root() in problem C solution

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry for the question. I understand all the thing.

»
20 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

C's time limit was stupidly strict. 36551515 is TLE(runs in about 2.15 seconds), while 36625920 is AC. The only difference was adding special cases if the exponent>=30.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Well, usually time limits are set 2-3 times as authors' solutions. As you can see, my solution (without any optimizations) runs in ~700 ms.

    36551515 is TLE due to endl & flushes. 36629869

»
20 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

In problem C, my question is when there are much more element need to be inserted in a container so "should we prefer vector on the place of the set?" in c++.

because of the same thing I implemented using set giving TLE and by vector AC

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why are we disposing sqrts in problem c

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are 10^9 squares in the range [1..10^18], so we can't just store them to answer our queries. But floor(sqrt(x)) is a number of squares in the range [1..x], so, we just calculate floor(sqrt(R))-floor(sqrt(L-1)) to know how many squares are in the range [L..R]

»
20 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I think that in problem A first test case the ans should be 26700.0000

Because after starting from 20:00 H= 315 and H/N=315 Hence we must give cat food in upcoming 315 minutes continuously to ensure that cat gets fed after 315 min in the min cost.. But 20:00- 23:59 there are total of 240 min hence 240*(4/5)*100+(315-240)*100 = 26700.0000 This will be the ans because remaining (315-240) i.e 75 min will be out of the discount period hence we have to pay for each bun C roubles in that period giving total cost of 26700.0000 Correct me if i am wrong !

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, there could be a optimal timing in between waking up and 20:00 too right? Can someone explain why isn't this so?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D can be solved by KMP with O(n) time complexity.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

question C can be easily solved by using the Mobius function (inclusion-exclusion of numbers l<=x<=r that can be generated in several ways). However, this solution requiers accuracy of the pow function and in test 5 (very big numbers) I get an off-by-one solution. How can one use the pow function to get the actual floor of the result even if the base is 10^18?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can test it manually.

    Imagine that the number returned by pow is x. Then test xp, (x + 1)p and (x - 1)p and choose the one that satisfies the conditions.

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please help me to understand the meaning of the adorable string, I am not able to figure it out just by reading the question!please help

»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

GreenGrape. In question 955C, how do u take care of the repetitions like 1000^2,100^3 which are basically 1000000, but show up in both squares and cubes. Thank you.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I exclude all squares from the set of powers greater than two after I generate them.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then, how about 3^15, which shows up in both powers of 3 and 5. Are you keeping track of the ones chosen from power of 3 onwards. Thanks

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        They’re stored in a c++ set which doesn’t allow multiple instances.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

By saying 'Let f3(u) will be minimal k, such that heapk(u) is equal to 3.', I guess you actually mean to say 'maximum k'?