Блог пользователя GreenGrape

Автор GreenGrape, 9 лет назад, По-русски
Tutorial is loading...

Код: 36605296

Tutorial is loading...

Код: 36605336

Tutorial is loading...

Код: 36605356

Tutorial is loading...

Код: 36605449

Tutorial is loading...

Код: 36605502

Tutorial is loading...

Код: 36605519

Разбор задач Codeforces Round 471 (Div. 2)
  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what does the function root() in problem C solution

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -6 Проголосовать: не нравится

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.

»
8 лет назад, скрыть # |
Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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]

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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'?