Livace's blog

By Livace, 11 days ago, In English,

Hello, Codeforces!

Codeforces Round #483 will take place on May/15/2018 17:45 (Moscow time). The round will be rated for both divisions.

Problems were prepared by neckbosov, KAN and me.

Many thanks to testers qoo2p5, manoprenko, AlexFetisov, winger, cyand1317 and ashmelev.

Also thanks to MikeMirzayanov for Codeforces and Polygon and ifsmirnov for jngen.

Upd. The scoring distribution is 500-1000-1500-2000-2500 for div2 and 500-1000-1500- 2250 -2500 for div1.

Congratulations to the winners!

div1:

  1. fateice
  2. skuecrk
  3. Egor
  4. dotorya
  5. LHiC

div2:

  1. wevetriedly
  2. mraron
  3. adeliaut
  4. fengsuiyan
  5. K.F.Cat

Editorial

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

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

how many problems ?

»
11 days ago, # |
Rev. 2   Vote: I like it +159 Vote: I do not like it

Judging from the name, it seems like a round in honor of people who donated some satisfying amount. Why are such special rounds not held on weekends so that as many people as possible could participate? Also maybe include some more information about the sponsors in the announcements.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

My rating is waving on the border of specialist and pupil these days.

And bless everybody and me to get more rating in this contest.

»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

It is raining contests...!!!

»
11 days ago, # |
  Vote: I like it -14 Vote: I do not like it

It will be very helpful if you please provide the scoring distribution for each problem.

»
11 days ago, # |
  Vote: I like it +34 Vote: I do not like it

Don't worry that your division can change after ratings update after Codeforces Round #482 (Div. 2). I'll fix all the registrations to match your actual division.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Both divisions ? Now we have three in Codeforces ! Thanks Codeforces

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    But rounds are still div1 + div2

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -54 Vote: I do not like it

      Next rounds may be one day div1+div2+div3 as div3 is considered a division

»
11 days ago, # |
  Vote: I like it +124 Vote: I do not like it

I believe if it is a thanks round, then the blog post should include some information and thanking for the supporters in this round. Otherwise it'll be no different from a normal round.

»
11 days ago, # |
  Vote: I like it -19 Vote: I do not like it

Accidentally downvoted :(

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Contests everyday, thank you

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

what does jngen mean???

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Contest of Div1 and ((div2 — div3) union div3) ) :P

»
11 days ago, # |
  Vote: I like it -114 Vote: I do not like it

These guys will beat tourist :

  1. gautam1212
  2. __B
  3. sarthak0797
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully, (Div. 2) Problems will be interesting like today's one.

»
11 days ago, # |
  Vote: I like it +114 Vote: I do not like it

Wow, there are real jngen users :) I haven't promoted it for several months, so I'm very happy to see that sort of self-promotion exists.

I would be glad if you could share the problems with me after the round. If I see how the community uses the library I can maybe improve the docs, give you some advice or see new development directions. My polygon login is the same as here.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow, nice short description. Hope the description of the problems will be as short as the blog. :)

»
11 days ago, # |
  Vote: I like it -8 Vote: I do not like it

My semester final exam start from today and I am waiting for Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!] :).

»
11 days ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

My rating is below 2100 but I cannot register at the home page.

Please fix the bug. MikeMirzayanov

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    If there is a div1 round, you only can participate in it. You are still a div1 contestant.

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

    Candidate Masters are in Div 1 when both Div 1 and Div 2 round are scheduled at same time.

»
11 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Hopefully.

Candidate master still participate in div 1 round.

»
10 days ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

She: "What would you do alone at home?"

Mobile chimes, " Codeforces Div ..."

He: "I am not alone, anymore."

»
10 days ago, # |
  Vote: I like it -37 Vote: I do not like it

you said the round rated for both divisions

is it rated for div3?

or div3 is n't a division

»
10 days ago, # |
  Vote: I like it -28 Vote: I do not like it

is it rated for DIV-3?

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

    DIV-3 is a subdiv of div2, not an independent div.

    As it is rated for div2, it is rated for div3

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Q. Why did Scarlet witch fell in love with Vision?

A. He was Red. :P

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck & hack for Both divisions

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

10 min delay. why?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    They did not give any reason in the past. So I do not think we can know the reason.

»
10 days ago, # |
  Vote: I like it -49 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
10 days ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Problems difficulty is Unbalanced at all A and B**** are extremely easy compared to C and D

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it -24 Vote: I do not like it
    The comment removed because of Codeforces rules violation
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      just searching the problem C and going to the top result leads to the answer

      why you copy the question from somewhere else and then remove the comments??

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

No Hacks !!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
10 days ago, # |
  Vote: I like it +21 Vote: I do not like it

I solved problem C without the condition of 4 guys in the elevator, and was thinking why I had got WA 4 during all contest.

»
10 days ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

What's the point in making such a tough TL in div1A? Nice problems btw.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    After finding g = gcd(q,b), If you divide q by g only once, it may reduces TL.(In TC 13)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Furthermore, the next value of g will always be a divisor of the previous one. So you can initialise g = b and then do g = gcd(q, g).

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Is Div1 E just finding greedily till lca from both nodes and summing it??

Also is Div1 B using SOS dp or something easy??

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did simple interval dp with precalculating function on all intervals.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dint precalc use SOS dp. ??

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        F[i][len] = F[i][len — 1] ^ F[i + 1][len — 1]

        dp[i][len] = max(f[i][len], dp[i][len — 1], dp[i + 1][len — 1])

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thanks!! I dont know how to react to this to miss such a simple observation but find a very nice pattern...

  • »
    »
    10 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Easy.
    dp[l][r] = max(dp[l][r-1], dp1[l, r]) where
    dp1[l][r] = max(dp1[l+1][r], dp2[l, r]) where
    dp2[l, r] = (dp2[l][r-1] ^ dp2[l+1][r])
    calc dp2 for all [l, r], then dp1, then dp.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Is Div1 E just finding greedily till lca from both nodes and summing it??

    Almost. The way I see it, you should go greedily (precomputing jumps by 2^k buses up) and stop before reaching lca, then check if the two vertices you stopped at can be connected by 1 bus. That check seems harder to me, I solved it using offline+sweepline+segtree in or , but I'm sure there's a simpler solution.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      That check is equal to query "Is there any number from interval [tinx, toutx] in the subtree of vertex y?" so it can be done with simple merging of sets.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?

        My solution represents each "do we need 1 bus?" query by a rectangle formed by the intervals corresponding to the subtrees of its end vertices and each bus by a 2d point formed by the coordinates of its end vertices (both sorted to avoid casework). I avoid using a 2d interval tree by sorting and sweeplining by one coordinate, using an interval tree with operations "add/remove labeled interval" and "check off all intervals containing some point". In the end, I made it have amortised complexity per query, it's just more work and a clever structure.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?

          Yes

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think you need to know whether you can "save one bus" because the stops from both subtrees are connected by the same bus.

    Since I'm not too sure how to phrase that properly, maybe I'll just highlight the problem by asking a simpler problem: Given 2 nodes, how do you know if they are connected by a bus (i.e. answer = 1 for that query)?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    is finite iff q contains only prime factors of b. So just divide q with the prime factors of b, and check if at the end whether q is 1 or not.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you find prime factors with such time constraints?

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        You don't need to find prime factors, just divide by the gcd until they are relative prime.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok thanks got it

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          i exactly did that but i got TLE on test 13:(

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            set b = gcd(q,b) before iterating, it decreases the complexity of finding the gcd, cuz you don't care about the other factors.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You have to divide q by g(g = gcd(b,q)) till q % g == 0. This statement cost me 6-7 WA. RIP rating

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I solved C as your described, but i do not know why I got TLE in test11.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I was getting it too, until i switched to fast IO.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          mraron, can u please, explain in detail? I knew that prime factors of q must be subset of b during contest. But seeing, constraint I couldn't figure out how to code i.e, prime factor for number till 10^18, would be TLE? Update : Leave it, understood :)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      What I was thinking was to convert q to base b and then check if the new q contains only powers of 2 or 5. Is this a correct approach?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know the theory but I did not checked q is 1 or not

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mraron p/q is finite iff each prime factor of q and b are equal OR each prime factor of q divides b???

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    A rational number p / q has finite decimal representation in a base b iff there exists a positive integer n such that q|bn. From this we conclude that the set of divisors of q must be a subset of the divisors of b. I tried implementing this idea in PyPy but got TLE on pretest 9 (though asymptotically it should pass, guess the constant factor for PyPy is too large or my implementation was bad. :( )

    Edit: Reading mraron's reply above, I think that my implementation was bad, kind of overkill.

»
10 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Hack-Free contest !

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

    I have seen someone had a successful hack. It was really unbelievable!

»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

why second pretest in B doesn't equal second example in task? wtf

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

I realized that the TITLE of the Problem Div2D,Div1B was such a huge hint, but it was too late. no time to debug.

»
10 days ago, # |
  Vote: I like it -47 Vote: I do not like it

Problem Div.2 C

What is the answer for :

1 1000000000000000000 999999999999999999 10

the calculator shows : 1000000000000000000/999999999999999999 = 1.000000000000000001 which is finite

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Infinite

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I'm sure your calculator would also show finite fraction for 1/3

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

    The answer is infinite if q / gcd(p, q) has prime divisors which b doesn't have and finite otherwise. The problem is I couldn't realise it.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    i don't think calculator can show infinite number of digits

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer for you case is "Infinite", you can learn some about precision of calculator.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    You are right! Checker is wrong so contest needs to be unrated!!!

»
10 days ago, # |
  Vote: I like it +32 Vote: I do not like it

Thanks Botan Investments for my decreased rating...

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For div2d, I thought of some kinda O(N^N) preprocessing but I had no clue how to calculate f() efficiently.. What is the idea behind this problem ?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Look at the title of that problem. There's a huge hint.

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If len = ar - al then
    f(al, ..., ar - 1) = f(al, ..., al + len - 2k - 1) xor f(ar, ..., ar + len - 2k - 1),
    where 2k is the maximum power of two that less than len

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I can't understand why that works. How to prove that?

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Write a program that simulates the function f.

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    First, Calculate the 2d dp:

    A[j][i+j] = A[j][i+j-1]^A[j+1][i+j]

    then calc max as:

    M[l][r] = max(A[l][r], max(M[j][i+j-1], M[j+1][i+j]))

    then the query will be O(1)

»
10 days ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

how can we solve problem D , i know we need to find max xor pair in given range , but how to optimise it from o(n^2) ?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using 2d segment-tree would be enough, I think.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ((r-l)log (r-l) for each query ?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        NVM. my approach was wrong. it was a simple pyramid-dp problem like answered below.

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    build a table : d[n][n] where d[0] = a, d[i][j] = d[i-1][j] xor d[i-1][j+1]

    precompute mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])

    answer queries mx[l-r][r]

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

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

      I think it should be:

      precompute, mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])

      Correct me if I am wrong.

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

To be honest, I must appreciate how setters choose cases for pretests in this one — really careful and cover nearly everything one can slip into. Cheers. ;)

»
10 days ago, # |
  Vote: I like it +35 Vote: I do not like it

too tight time limit on Div.2 C....

»
10 days ago, # |
  Vote: I like it +158 Vote: I do not like it

Anybody else wants to complain against time limit of div1 A?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    me, i even made a comment in russian

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    It depends on what is an intended complexity. Firstly I did something like log times gcd per testcase (which is O(log^2)) and it turned out to exceed TL. Then I did some optimization which looks silly, but I think it may actually improve complexity and passed in TL/3. However this task is actually doable in O(log(log(b + q)) per testcase, because it suffices to check if q|b64 which can be done with 6 multiplications if we have big integers or __int128_t that Codeforces doesn't have (taking mod q after each step of course).

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I tried bigint solution with python, and got TLE..

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I have log times gcd and it got AC. On the other hand, the numbers I'm computing gcd from decrease very quickly — it's "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible".

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        That's what I did in the end as well. I mean you and I both finally have "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", but in the beginning I had "while Q > 1 compute gcd(B, Q), divide Q by it" without "as many times as possible". I am not sure what is the worst case complexity of this solution, but after some thought I got an impression it is really useful and it is not as silly as it looks.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For having "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", it may takes even longer time in worst case. An example is q = 260, b = 231 then gcd(q, b) = 231 but we can divide it only once. However to check whether dividing it one more time is possible, we have to compute a division to check its remainder. (That cause extra time)

          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, in some cases it may be worse but thats not a worst case. In your example in next iteration we will have gcd=2^29 and divide everything, so there is only 2 computations of gcd(which also has divisions btw). If you divide by gcd once you have up to 60 iterations of gcd (which gives per test comlexity. If you divide while you can, it's no more then sqrt(60) iterations of gcd, which gives you (and comment shows that complexity may be shown to be

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm pretty sure this is asymptotically faster. It's no more that O(sqrt(log()) iterations of gcd because you divide by numbers with different number of primes each time

        (and may be it's even faster)

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +18 Vote: I do not like it

        If you do that + making B = gcd(B, Q) after not being able to divide makes the complexity O(log) amortized. This works because for each 2 iterations of Euclid's algorithm, one number is at least half of before and you use that number for the next iterations so the maximum number of iterations is O(log). Other than that, the number will obviously be divided at most O(log) times. Did I miss something?

        Edit: also, for your optimization my friend's reasoning applies. There will be 1 prime that will get below the exponent of B in one while iteration and it will disappear in the next one. So you get rid of at least one prime for each 2 iterations.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks AlexDmitriev for this comment, he is right, this solution works O(nlog1.5M). Optimization is same as "divide as we can", but works faster because numbers are smaller. But I think that it doesn't make less complexity. Editoral will be updated.

      • »
        »
        »
        »
        9 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It actually does make the complexity O(logM) per case. Maybe I wasn't clear on the comment above. If you call gcd(q, b) for each 2 iterations b will be at least half so the sum of iterations until b is 1 is O(logb) (amortized).

        By iteration I mean iterations inside gcd

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Sorry, it's not clear to me why the complexity is O(log M) per case.

          If you have log(N) + log(N/2) + log(N/4) + log(N/8)..., that's still log(N)^2 time, no? Since it's log(N) + (log(N)-1) + (log(N)-2)... complexity.

          Seems to me like the real complexity is still . Since the worst case involves all the primes having different exponents, we can divide by more than half each time, we can divide by 2i for each iteration. So, our computation is log(N) + log(N/2) + log(N/2^3) + log(N/2^7)..., or log(N) + (log(N) -1) + (log(N) - 3) + (log(N) - 6) ....

          So, the number of log(N) operations we have to do is based off of how fast 1,3,6... reaches log(N). As that's just simply the triangle numbers, there's terms.

          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
            Rev. 2   Vote: I like it +10 Vote: I do not like it

            If you had one gcd take x iterations then B will be <= B / 2^(x/2). So the complexity isn't log(N) + log(N/2) + log(N/4) + log(N/8)... and the sum of steps will be <= 2 * log(B).

            So if a gcd computation takes indeed log(B) or a big number of steps, the number will be much lower than B and the maximum number of iterations for the rest will be lowered. This is amortized analysis, not every gcd will be worst case. Also as you get closer to worst case for gcd, worst case implies that gcd is 1 and you don't need to continue so more iterations == B is much lower.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          If I'm not mistaken the following simpler code works in :

          b = gcd(q, b);
          while (b > 1) {
            q /= b;
            b = gcd(q, b);
          }
          return q;
          

          Suppose that the loop has several iterations, and the value of variable b in the i-th iteration is bi. Time complexity of the i-th invocation of Euclid's algorithm is . So the total complexity of the loop is , since for some Q.

»
10 days ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

solution for Div2. C (Div1. A):

https://math.stackexchange.com/questions/310402/proving-finite-vs-infinite-representation-of-p-q-in-base-b

(i think now there is no violation with codeforces stupid rules)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    they didnt even change the p,q,b!!!

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      well if you know the solution. why you couldn't get accepted verdict? they have tighten the time limit so you must try different approach.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        i tried 19 different approaches!

        and now when i see others approaches some of them are same whit me and the only difference is that they print the answers immediately but i print all answers after calculating all of them

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      A very high chance that it's just a coincedence. Integer fraction is very often (almost always) presents as p/q and base is ussualy presents as 'b'.

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

An interesting game

»
10 days ago, # |
  Vote: I like it +21 Vote: I do not like it

problem C looks trivial. Does this dp works? dp[i][pos][x1][x2][x3][x4]=minimum cost if the first i people already entered in the elevator, currently we are at floor pos, and the elevator contains people that wants to go to floors x1,x2,x3,x4.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, i think. but you should consider memory limit in that problem.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      well, we only need the last two rows so i={0,1}

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    You can reduce the complexity and memory space only considering the ordered multisets of (x1, x2, x3, x4). There is only 715 such multisets. Also looked trivial for me, just a careful implementation was needed.

»
10 days ago, # |
  Vote: I like it +35 Vote: I do not like it

This is the first round when I solved div1 E. I solved div2 E for the first time when Livace was the problem setter too (Codeforces Round #442).

Link: http://codeforces.com/contest/877/standings

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Perhaps you should plan to meet him in person?

    I don't think it's just notorious coincidence ;)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem (B. Minesweeper) 1 1 * how test like this can be valid ????

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It satisfied all constraints.

    There is only one cell with a mine. No cells left un-mined, so no numbers could be found.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The one cell satisfies both criteria given in the problem statement:

    • there is not a digit in the cell, so you don't check for the count of bombs in neighboring cells;
    • the cell is not empty, so you don't check for neighboring cells having bombs.

    :)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      there is a bomb with no number point to it !! this is a violation for the game rule ??

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Indeed, in the real game it would not make much sense. But if you just abide by the problem statement it does. In my case, I didn't think about this apparent inconsistency because I never played that game :)

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

During the contest I wanted to hack leon_ldy's solution(38273146).I had 2 unsuccessful submissions in this problem and after my second submission I noticed in pretests 8 , n=1.but why his submission passed pretest? this is his code:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int a[MAXN];

int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int j = n - 1, k = 0;
	while (true)
	{
		j--;
		if (j == k)
			break;
		k++;
		if (j == k)
			break;
	}
	cout << a[j] << endl;

	return 0;
}

but when n=1 so j=0. and in the "while (true)" we had TLE. because at first "j--" and after that j=-1. so always j!=k.

»
10 days ago, # |
  Vote: I like it +78 Vote: I do not like it

»
10 days ago, # |
  Vote: I like it +22 Vote: I do not like it

C+E = (Code*Code*Code+Code^2)^Code

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

    What's wrong with C? Seems fine to me.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      That it is obvious to come up with a solution and nontrivial how to properly code it. It is a programming task, not an algorithmic one. Some people would say that it is ok, but I think that it is also ok to say it is not an interesting problem.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        OK, I see what you mean (but I still think that it's pretty easy to code)

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +29 Vote: I do not like it

          It seems that whenever contest goes well for me I think tasks were fine and when it doesn't I always declare tasks as programming and noninteresting ones :P.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For C I check whether the divisors of q are a subset of the divisors of b with gcd but still get TLE on 13.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is because of slow input

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used fast input for java but it may be bcause I used slow output xD

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Any ideas for D?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Probably, it's wrong

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

      Do you know any good tutorials for kd-tree?

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Unfortunately, I haven't seen.

        For D I followed this easy-to-implement solution(actually, it's not classical KD-tree, it's more likely as joined KD-tree and Segment tree, just intersecting rectangles instead of segments) Probably, the author forgot about inclusion/exclusion case with boundary points in some quadrant.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Author's solution is scanline + segment tree with sets in vertices.

»
10 days ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
a=input()
while(a>0):
    a-=1
    p,q,b=map(int,raw_input().split())
    r=gcd(p,q)
    q=q/r
    r=gcd(q,b)
    while(q!=1 and r!=1):
        while(q%r==0):
            q=q/r
        r=gcd(q,b)
    if(q==1):
        print"Finite"
    else:
        print"Infinite"

even after writing exactly the same code as it is being discussed in the comment section, my solution failed. Time limit for python is too strict. i got tle in 11. Please verify if there is a mistake on my side or this happened because of the language selected. Thanks :)

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    my English is poor,emmmm,

    while(q!=1 and r!=1):
            q=q/r
            while(q%r==0):
                q=q/r
            r=gcd(q,b)
    

    ~~~~~ while(q!=1 and r!=1): q=q/r while(q%r==0): q=q/r r=gcd(q,r)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it means while q not equal to 1 || r not equal to 1

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i know , it is the first time for me to reply you can look the code i changed.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I even tried this in my submission but even that failed pretest 11

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            oh i know ,and you should know if p == 0 output Finite change like that ~~~~~ while(q!=1 and r!=1): q=q/r r=gcd(q,r) ~~~~~

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              ohh shoot I think I got my mistake i thought all were having constraints >=1 Thanks a lot mate

              • »
                »
                »
                »
                »
                »
                »
                »
                10 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                it dosent matter whether p==0 or not as when p==0 gcd(p,q)=q and q/q=1 and so ans would be finite it is definitely fault of strict time limit

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The language selected is the mistake on your side.

»
10 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Is the time limit for python and c++ same every time for every question???

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pretty sure it is. Python needs more love!

  • »
    »
    10 days ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    no I guess its 5x for python but at times even that is slow it makes the competition more fair if the setter/tester try it in python as even python is being used a lot as compared to c++ and java

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      no I guess its 5x for python

      Where did you hear of this? All I see is there is only a single time limit for each problem, e.g. it's 1 sec for Div2 C

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        python has a time of 5x likewise java has 2x. this time is allocated according to the processing time of the language. as python is a slower language than c++ it gets 5x time. But this dosent mean python has more advantage.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You aren't answering my question though, are you sure you are not just making this up?

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            no I am sure as on various platforms like codechef and hackerearth this rule follows

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

For Div2D , if (r-l+1) is power of 2 then we can take all elements from l to r.

If I am right then please someone say the answer of this input and how ?

24

1 2 128 256 512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 4 8 16 32 64

1

5 20

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

During the contest I had the following problem. In my template I have a few pragmas that should optimize operations and make Codeforces submissions faster (they’re pretty common to include nowadays).

However, for today’s problem E, something weird happened. The solution with these pragmas got RE verdict on pretest 1, while the solution without them got accepted.

http://codeforces.com/contest/983/submission/38296856 http://codeforces.com/contest/983/submission/38297301

I assure you the only difference between the two sources is in the pragma macros.

Have you ever experienced something like this? What pragma do you think is broken, in this sense?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Leaving my comment, cuz I am curious as well and I wanna be notified :D

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tested on custom invocation and put the bits/stdc++ line before the pragmas and oddly it worked. I have no idea why

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Third pragma. The problem may appear in situation, when CF uses different machines with a different architecture to compile and run code. It's common problem on Yandex Contest system. I use following pragma for it:

    #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
    
    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      So, is it only the tune=native setting I shpuld remove or all the rest of them?

      Also, I can’t test myself right now, have you tried running it without tune=native and seen it work?

      Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok, I tested. In your case it's "abm" setting.

        Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

        Actually, It depends not on platform, but on problem and on your code. That is, if the bottleneck of your solution can be vectorized, then the pragma will help. Otherwise, the optimizer can apply vectorization where it is not needed, and your solution will slow down.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I agree with that. However, I’ve seen consistently better results overall on Codeforces, while I’ve never seen improvements on Yandex (Opencup for example). I think it depends on the architecture and the compiler as well. I’m not pretending to know anything here, but my guess is that the running on Windows the pragmas will have a bigger positive impact than on Linux.

          Have you ever had noticeable changes using these pragmas on Yandex? (compared to not using them, obviously)

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There were some problems from SNWS contests, PTZ and MIPT camps, that I solved with not optimal complexity, and I'm pretty sure that pragmas helped in that solutions.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        abm changed the implementation of std::__lg, which is later called by std::sort. Here's a simple example of it being unstable, even on other platforms:

        #pragma GCC optimize("Ofast")
        #pragma GCC target("abm")
        #include <bits/stdc++.h>
             
        using namespace std;
             
        int main() {
            cout << __lg(1) << endl;
            volatile int i = 1;
            do {
                cout << __lg(i) << endl;
                ++i;
            } while (i <= 1);
        }
        

        Output:

        0
        31
        

        with abm

        without abm

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.

        Lol, I added the Ofast pragma to my code for E and it slowed down by ~50%.

        On the other hand, one secondary school student in our IOI selection used

        # pragma GCC optimize ("O3")
        # pragma GCC optimize ("Ofast")
        # pragma GCC optimize ("unroll-loops")
        

        to almost solve a problem with bruteforce.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The time limitation on Div2C is too tight.... just reassigning gcd value made it passed.. -_-

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Systests for div1B are weak, i see some O(q*n) solutions accepted

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why first gives TLE and the other one AC 38300452 and 38300601

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because cin/cout is much slower than scanf/printf. So, don't use cin/cout to solve big I/O problems.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can just write first line from int main(): ios::sync_with_stdio(false); and this will give you a boost

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Really bad from my side . Had I written it it would have been AC :(

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When are we going to get the tutorial?

»
10 days ago, # |
  Vote: I like it +182 Vote: I do not like it

So, did noone notice this: 1 2?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain why the first query of the second test case of Div.2-D is 60 instead of 63? shouldn't it be 1 ^ 2 ^ 4 ^ 8 ^ 16 ^ 32?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You misunderstood how f function works. Acturally, the answer for f(1,2,4,8,16,32) = 51. You may implement it yourself. :)

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Pretests for B were pretty weak. In my solution I put a "n" instead of "m" in the second loop when I wanted to traverse my matrix. Apparently that was enough to pass the pretests. I noticed that error only after the system tests.

Then I changed "n" for "m" and got AC. Sad day for me :( .

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    weak pretests are needed for hacking:)

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Hacking is needed for weak pretest (not the opposite)

»
10 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Q. When does one grow up? A. When one reads more comments on CF than FB.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2 problem C For values of p,q,b=(10,5,3) in TC#3 how the answer is finite

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10 / 5 = 2 in base 10 which is 2 in base 3. This does not have a non terminating decimal part(rather does not have any digit after decimal point)

    I guess you are confusing with the case (p,q,b) = (5, 10, 3). In which case it would be non terminating and hence infinite in problem's context.

    So you only need to take into consideration the prime factors of denominator and base since for improper fraction a/b you can always write it as [a/b] (greatest integer function) + {a / b} (fractional part) where the former will always be translatable to different bases without recurring decimals . Refer editorial for more insights.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well if we convert both numerator and denominator firsthand to base 3 i.e. 10 in base 3 would be 101 and 5 in base 3 would be 12, so 101/12 will be infinite. I am confused here.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes it is correct to say that but notice that since you convert numbers to base 3, conventional division(in base 10) does not work.

        You can still observe that base3(12) * base3(2) = base3(101). Hence we don't have a recurring decimal. An easier way to do the this is the same as mentioned in samples in the question .

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got it. I misunderstood the notes of the problem given in the contest. Thanks alot. :D

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was trying to solve Div1E with O(n * sqrt(n)) complexity, sqrt(n) jumps instead of binary lifting. When I debugging I changed my sqrt variable to 1. And it got accepted.

38320734

It simply tries to jump lca and stop when there's a route from this node to lca. And same thing for second node, also check for ans - 1, no different solution.

You can check my code and see that for every query I'm calculating the answer with increasing res one by one.

while(!inside(c, go[x])) {
	if(go[x] == x) {
		res = -1;
		break;
	}
	res++;
	x = go[x];
}

And sad part is I have no clue how good my O(n * sqrt(n)) solution is. It actually got slower time :(

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

My solution was missjudged in contest. Please kindly look into it.

Detailed post: http://codeforces.com/blog/entry/59503

Submission on contest: 38291441

Same solution accepted: 38328663

Thank you.