GreenGrape's blog

Codeforces Round #471 (Div. 2) Editorial
By GreenGrape, 7 years 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

Comments Comments (16)
| Write comment?
»
7 years 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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does the function root() in problem C solution

→ Reply
»
7 years 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.

→ Reply
  • »
    »
    7 years 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

    → Reply
»
7 years 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

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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]

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years 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.

→ Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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

      → Reply
      • »
        »
        »
        »
        7 years 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.

        → Reply
»
7 years 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'?

→ Reply