Livace's blog

Codeforces Round #483 [Thanks, Botan Investments and Victor Shaburov!]
By Livace, 7 years 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 FalseMirror, 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. dummyies
  4. fengsuiyan
  5. K.F.Cat

Editorial

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

Comments Comments (210)
| Write comment?
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

how many problems ?

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

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

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

It is raining contests...!!!

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

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

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

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

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

Accidentally downvoted :(

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

Contests everyday, thank you

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

what does jngen mean???

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

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

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

These guys will beat tourist :

  1. gautam1212
  2. __B
  3. sarthak0797
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
7 years 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!] :).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -34 Vote: I do not like it

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

Please fix the bug. MikeMirzayanov

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

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

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

Hopefully.

Candidate master still participate in div 1 round.

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

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

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

is it rated for DIV-3?

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

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

10 min delay. why?

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      You are Adhami, however you code in C++.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        C++ is faster.

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Java is an island. An extremely verbose island.

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

        Because I used to use Java one year ago

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think they wanted to wait for more participants. It's reaching 6k now. Apparently they've got ~100 more participants in the last 10 mins.

      → Reply
»
7 years ago, # |
  Vote: I like it -49 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -24 Vote: I do not like it
    The comment removed because of Codeforces rules violation
    → Reply
    • »
      »
      »
      7 years 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??

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

No Hacks !!

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

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

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

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

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

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

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

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

      Dint precalc use SOS dp. ??

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

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

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

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

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

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

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

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

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

How to solve C?

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

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

      How did you find prime factors with such time constraints?

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

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

          Ok thanks got it

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

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

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

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

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

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

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

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

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

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

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

Hack-Free contest !

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

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

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

    Infinite

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

      why is that ?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        For it to be finite you should be able to multiply denominator into a power of 10

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

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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

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

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

Thanks Botan Investments for my decreased rating...

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

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

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

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

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

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

        Write a program that simulates the function f.

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

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

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

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

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

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

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

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

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

      thanks

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

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

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

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

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

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    me, i even made a comment in russian

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

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

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

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

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

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

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

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

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

      Thanks riadwaw 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.

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

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

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

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

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

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

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

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

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

An interesting game

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

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

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

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

    → Reply
»
7 years 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://mirror.codeforces.com/contest/877/standings

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

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

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

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

    :)

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

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

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

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

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

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

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

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

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

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

Any ideas for D?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Probably, it's wrong

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Do you know any good tutorials for kd-tree?

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

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

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

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

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

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

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

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

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

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

    The language selected is the mistake on your side.

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

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

    Pretty sure it is. Python needs more love!

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

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

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

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

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

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

→ Reply
»
7 years 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://mirror.codeforces.com/contest/983/submission/38296856 http://mirror.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?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

When are we going to get the tutorial?

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

So, did noone notice this: 1 2?

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

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

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

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

    weak pretests are needed for hacking:)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Hacking is needed for weak pretest (not the opposite)

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

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

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

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

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

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

→ Reply