SerezhaE's blog

Codeforces Round 586 (by FAMI and MIPT LITED)
By SerezhaE, 5 years ago, translation, In English

Hello Codeforces!

We are glad to invite you to the Codeforces Round 586 (Div. 1 + Div. 2). Yes, it is rated!

The problems were invented and prepared by Alexponomarev7, adamant, lesswrong, wrg0ababd, VeryLonelyRaccoon, CepryH9, msmlkm and me, SerezhaE. A lot of thanks to 300iq and cdkrot for help in contest preparation, and also we want to thank MikeMirzayanov for Codeforces and Polygon systems.

The contest starts on Wednesday, September 18 at 16:05 UTC and you will have 2 hours to solve the problemes. I believe everyone will find interesting problem for themselves :)

UPD. Editorial is published!

Good luck!

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

Comments Comments (167)
| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

is it rated?

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

    I think copy pasted part has been skipped.

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

    I asked the question when post didn't mention it. Now it's updated.

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

2 back to back contests! Reason we all like codeforces.

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

This will be what, the 4th combined division round in a row for me? 5th if I count virtual Global Round 4.

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

    Did you account for up coming round "Dasha Code Championship"? :)

    I think combine round is different from separating them. People usually earn more and lose less rating. :)

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

      Only accounting for rounds I know I can participate in.

      You can't have everyone earning more rating if the sum of ratings is non-increasing (which it should be, extra rating comes from new users). It should be that high-rated contestants can lose more rating if they clearly underperform and low-rated can gain more thanks to that. There are more participants, which allows for more extreme situations.

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

      But one clearly advantages of Div.1 + Div.2 combined rounds is to prevent people from quitting the rounds. In Div.1 only rounds, some guy can read a problem, find it too difficult and quit the round without losing any ratings. While in combined rounds, he always solved some very-easy problems first and can't quit the round.

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

    Combined rounds should be used only for events (usually with prizes). Normal rounds are much better. Problems fit participants more and hacking is more balanced.

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

The time really fits Chinese! I love it!

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

    It's literally midnight (i.e. 12 AM) in China when this starts

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

I hope the statement will be short and nice like the announcement :D

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

Why does a new problemsetter prepare a Div.1+2 contest?

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

Good luck to all particopants and thanks for the contest!!!

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

How many problems?

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

It will be a fun contest! :)

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

    There are known knowns, there are things we know we know. We also know there are known unknowns, that is to say we know there are some things we do not know. But there are also unknown unknowns, the ones we don't know we don't know.

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

What about score distribution?

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

Hi everyone, today we are going to play HungerGames mode in Minecraft. Guys, would you like to join us????

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

1AM over here in Korea! Willing to give up tomorrows class for this contest :)

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

I guess "problemes" is not the appropriate word!

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

300iq <3 contest .

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

this is my best contest ever !!!!!!!!!!! :)))))))) thank you so much SerezhaE

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

How to solve B ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    you have the results of: a1*a2,a1*a3,a2*a3

    a1*a2 = r1

    a1*a3 = r2

    a2*a3 = r3

    a1*2 = r1*r2/r3 --> a1 = sqrt(r1*r2/r3)

    Hope it works after test

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

      Can we use gcd?

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

        I think GCD would give an approximation for each column, could you provide the context of using GCD?

        using GCD I think would have to do special work for 1

        EDIT: I mixed GCD and LCM :(

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

          (For n=3 example)The first row is 0 a*b,a*c so if we get gcd(not including 0), we at least get a, but this is the problem here, if gcd(b,c) is not equal to 1, it becomes a problem. I could not figure it out for bigger value of n

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

            Thinking in solving 3 unknown variables using 3 equations is much simpler, but for GCD you would need to do second iteration to validate values, I think you could do it that way

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

        I have used GCD of a column... but then also to avoid some corner cases I have checked all the divisors of the GCD value for which the matrix becomes valid... https://codeforces.me/contest/1220/submission/60795097 Here is the code.

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

          Your codes are very well written i wish only if i could also write such codes.

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

      Thank You. IslamOmar

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

    why im so stupid to use gcd ?

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

      i used the most stupid form of gcd ( gcd all of the line thing ). then make up my mind and skipped B.

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

      Well. You're not... because I've also used GCD and actually solved B using it... The only extra part was, I checked all the divisors of the GCD value for which the matrix can be valid... https://codeforces.me/contest/1220/submission/60795097 So the idea was not wrong, just needed a little modification... This is the fun of problem solving, there are so many ways to solve it. So never underestimate that. ^_^

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

How to solve D?

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

    I'm not sure but... If we have A and B, where A is odd and B is even we can create a cycle with odd length. So we will use recursion There are two possible ways: delete all even numbers in an array and leave recursion or delete all odd numbers, divide all numbers left by 2 and do recursion again. We continue recursion and divide by 2 because there can be something like this: 2, 4. We can create cycle 0 — 2 — 4 — 0. So we can solve this problem with O(n log n)

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

    you have to realize that:

    A and B can be in S if and only if the maximum power of 2 that divides A is equal to maximum power of 2 that divides B.

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

why problem D example 1 i can't simply delete vertex 1 and 3, the problem only states that we can connect 2 vertex if it absolute value after subtract each other belong to set B, so if it in the example we should have a triangle and it doesn't matter which vertex we choose cause it gonna turn into a bipartite graph anyway

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

    It asks you to delete the minimum number of vertex, so you could delete either 1, or 2.

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

      You can't delete vertex 1 and keep 3.

      Draw the graph for vertices 2, 3, 4, 5, 6 and B = {2, 3} and you will see it's not 2-colorable.

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

    It's not a traingle. 3 elements in set B doesn't mean there are 3 vertices. There are infinte vertices actually

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

      prabalsingh24 are there infinite vertices marked from $$$-\infty$$$ to $$$+\infty$$$. I am misunderstanding the statement.

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

how to solve D. I only know O(n^2)

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

    Can you please tell O(n^2) approach?

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

    One fact is you can only pick two numbers that are divisible by same power of two (for example you cant pick 6 and 40 but you can pick 10 and 22).

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

      Start from a arbitrary number and find the next time that two integers from B can both reach to another number. that number is LCM of those two number and simply you can see if they are not divisible by same power of two then you can find an odd loop.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +27 Vote: I do not like it
        If they are not divisible by same power of two then you can find an odd loop.
        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi , is this an observation or is there some mathematical proof behind this? Why cant 4*a and 2*b (where a and b are odd numbers) be in the set? sorry if its a noob question , but i am not able to find a proof for this.

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

        Consider this example :

        0 2b 4b 6b ... 4ab (Theses 2a numbers make a path because of having 2b in the set)

        0 4a 8a 12a ... 4ab (Theses b numbers make a path because of having 4a in the set)

        So you can see it makes a loop with size of 2a+b and that's an odd number so graph is not bipartite.

        The loop is like this : 0 2b 4b ... 4ab 4a(b-1) 4a(b-2) ... 4a 0 .

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

how to solve problem D?

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

    in the set there can only be numbers of the form

    2 ^ s * i , where i — any odd number, and we can iterate s

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

Wow, second round in a row I'm f**king with epsilons in geometry for no good reason. Just wow.

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

    AAAAAAAAARGH

    Maybe it's finally time to write a geometry library using bigints only. Or something. -.-

    (At least it's gonna be useful on GCJ geometries.)

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

    I tried something like: consider several small primes, get possible values of X and Y modulo them, combine it using CRT. I didn't have enough time to think it through but maybe it is the intended solution.

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

      Can it solve the problem for n=2? If so, it seems reasonable to be (part of) the intended solution.

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

        Just doing all calculations mod $$$MOD=10^9+7$$$ suffices. Suppose that we want to find the intersection of two circles in the form $$$(x-a_i)^2+(y-b_i)^2=c_i\pmod{MOD}$$$ where $$$i=1,2.$$$ First subtract the two equations to find the radical axis. Then substitute for $$$x$$$ in terms of $$$y$$$ (unless $$$a_1=a_2$$$) and solve the resulting quadratic with modular square root.

        (Code: 60845080)

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

          Better way (No quadratics) to find intersection of circles: Wolfram link From Wolfram link you can find how to calculate intersection $$$(x;\pm y)$$$ if centers are $$$(0,0)$$$ and $$$(d,0)$$$. If centers are $$$A$$$ and $$$B$$$, treat them as complex numbers, then intersection points are $$$A+(B-A)*(x/d\pm i*y/d)$$$. I have doubt about my solution, because I only checked 20 distances to other points (if it is subset of given multiset it passes). How it doesn't get WA? (Code: 60952855)

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

    Checking if distance from center of mass is exactly as needed makes solution faster. After this check you can try about 100 points around the intersection and not get TLE.

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

    Having finally solved this, I want to strangle the next person who mentions geometry to me in person. I tried so hard to make calculating cos() from cosine theorem precise enough, but in the end, I gave up and did all subtraction in bigints.

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

thanks for weak pretests for B! 4 hacks, yay!

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

Can someone tell me what is the 12th test in problem D ? :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +76 Vote: I do not like it

In problem D. when you finally notice $$$i,j\in N$$$. not $$$\in B$$$... :(

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

    What? Really? Noticed it right now :)00)

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

    I think the statement was very poor in problem D :/

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

      I agree. And I talk the statement to people knowing nothing on math and programming, they think that's for integers in B. By the way, I have checked manually the first example during the contest, the result is OK for this understanding as well...

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

        I would say its nothing about knowing math or programming, its about the confusion that the problem statement has. Notice that even a lot of candidate masters were confused.But you are absolutely right, the statement supports the both way of thinking.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    [Deleted]

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

    I spent 1 hour thinking a different problem :c I didn't notice that until now xD

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

    Ow maan, but, $$$i, j \in \mathbb{Z}$$$...

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

Awesome problems, really like them.

Nice job!

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

How to solve E? My idea was to continuously remove vertices with only one remaining neighbor (except the source), compress the rest of the graph into one component, then restoring the removed vertices find the path with largest sum starting from the component/vertex where S is. What is wrong with this or did I just do something stupid?

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

    any node in a cycle or in the path from $$$s$$$ to the cycle, can be always taken by $$$s$$$->cycle back-> $$$s$$$. all the nodes can be treated as $$$s$$$. so remaining graph is a tree. find longest path to some leaf.

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

      Yes, that's what I do. Probably I have some stupid implementation bug ...

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

        What do you do in this case?

        The optimal path is (s) -> (compressed graph) -> (node on the left). Are you sure you don't for example count the weights between (s) and (compressed graph) twice?

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

          No, I (at least in theory) compress S, the middle node, and the compressed part together. So the final graph looks like

          A — B — (S+middle+compressed)

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

What a huge gap between C and D !!

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

How to solve F ?

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

    Notice that element $$$a$$$ is an ancestor of an element $$$b$$$ when it's minimum on a subsegment from $$$a$$$ to $$$b$$$. Count amount of ancestors for every element in initial permutation. Now, when you remove element $$$l$$$ from the left, all elements between it and the leftmost element smaller than $$$l$$$ now have one ancestor less. When you move it to the right, all elements between it and the rightmost element smaller than it have one ancestor more. You can store amounts of ancestors in a segment tree with lazy propagation. Solved.

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

How to solve C??? Use suffix array???

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

    Just consider the smallest char already seen. The game will not last longer than 1 move :)

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

      Hi, I understand that there will be only one move in the game. Can anyone clarify why we are comparing only the first character with the substring?

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

    Only thing that matters is the first character on the left that is smaller than s[k]

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

    The game either has 0 moves or 1. If a smaller alphabet occurs before the start pos, ans is Ann, else Mike.

    Not sure though.

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

    Thanks everybody. It was seriously difficult problem...

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

      Instead of choosing smallest alphabet, what about choosing smallest suffix before current index? Doesn't it work similarly?

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

        It does, but it's harder than intended solution

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

          I think it doesn't as I first used suffix array and failed on test "abas" for k = 3.

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

          Well actually it didn't...

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

    I first used suffix array but failed on test as "abas" as for k = 3 the answer is Mike not Ann but using suffix array would print Ann as suffix "as" is bigger than "abas" but after that I realized the simple solution considering the minimum char already seen!

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

      That's absolutely right!!! Now I understood why my approach got WA. Thanks a lot!!!

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

Couldn't you give some actual samples in F? Especially in order to distinguish rotating to left and right xd.

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

I think I've seen F in a atcoder round, not sure. I do remember the trick of storing $$$X_{i} + Y_{i}$$$ in a segment tree, where $$$i$$$ is the longest decreasing sequence starting from $$$i$$$ to the left, and $$$Y_{i}$$$ is the longest decreasing sequence starting from $$$i$$$ to the right. Then the depth of the cartesian tree is the maximum of $$$X_{i} + Y_{i} - 1$$$ in the interval, and $$$X, Y$$$ are easy to update.

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

    Seems completely doable without that to me. Duplicate the permutation, then for each index, calculate the depth the tree rooted here would have if it covers everything between the closest smaller elements to its left and right (excluding these). Finally, for each index, calculate the depth of the tree we'd get if we took everything from the closest 0 to the left up to this element, using these precomputed simpler depths; same for closest 0 to the right.

    I almost managed to code it in those 20 minutes I had left after getting E passed... damnit.

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

    Another solution — if we add an element to the right, the depth can only increase and if we delete one from the left, depth can only decrease. So we can binary search to find the points where the depths of the left and right subtrees are closest.

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

    The answer is non-decreasing with respect to expanding the interval. So, you can binary search on the answer, and for a fixed $$$k$$$ find the maximum interval to the right of $$$1$$$ that has depth $$$k-1$$$. Now simply check whether the rest (to the left of $$$1$$$) can also be done with depth $$$k-1$$$. Complexity is $$$\mathcal O(n \log^2 n)$$$, but quite fast in practice.

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

    We can actually simulate the entire process as well and get depths of all cyclic shifts.

    Moving from one cyclic shift to the next will require simple range updates.

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

Made one wrong assumption for D, got stuck the whole contest: I assumed that the set of elements taken finally for forming bipartite graph,say has minimum element k, so all other numbers of set must be odd multiples of k. Anybody made the same mistake ? :(

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

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

    And which version is better? I know people preferring either.

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

      I prefer second version but without weird version of $$$\leq$$$.

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

      I don't care too much about scientific notation vs lots of 0s, but I think the horizontal line ≤ and ≥ look much nicer.

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

Is WA in case 49 (problem B) an overflow? (using Int instead of Long Long Int)

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

    Yes probably. You need 64-bit integers to solve the problem.

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

    I took me 15 minutes to find out from my first submission :v

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

What is test 46 in E?

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

    It is generated test with a tree and many loops of size 3 added to it.

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

    It contains some cycle with zero weight.

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

In problem E statement, this sentence make me confuse:

"Alex believes that his trip will be interesting only if he will not use any road twice in a row."

and the phrase "in a row" can be viewed as "continuosly". So I totally misunderstanding this problem (I think a edge can be use twice)

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

for alex and julian question d, for given input 5 10 20 ,erasing 10 is sufficient but why answer is 10 and 20

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

    It's not sufficient to erase 10.

    5 & 20 create odd cycle which is not bipartite:

    0 -- 5 -- 10 -- 15 -- 20
|                     |
\--------------------/
    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My solution for B: 60809853. I get the gcd of all elements in first row, this results in $$$a_1 * constant$$$. For every divisor of this value, I try to see if this is "valid".
The validation assumes that the divisor is $$$a_1$$$, I can get $$$a_2$$$, ... $$$a_n$$$ from the first row. then using these values, I check if $$$a_i * a_{i+1}$$$ matches the given table. Could somebody tell me why this is sufficient?

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

Can anyone explain how do we decide a substring is lexicographically less or not in problem C? Please help.

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

    Here

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

      Thank you very much

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

        Can you clarify why we are comparing only the first character with the substring?

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

          Since the first substring to use is $$$s[k,k]$$$ it's just a letter, and it can only be beaten by a string that differs in the first letter. Thus, if no $$$s[i,i]$$$ can beat $$$s[k,k]$$$ in the possible range ($$$[1,k-1]$$$ or empty set if $$$k = 1$$$), then there is no possible move (Mike wins). Otherwise, our best choice is to move to the minimal $$$s[i,i]$$$ since the other player won't be able to make a move from there (because it's the minimal) (Ann wins).

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

How to solve D?

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

nice contest! There is one problem with no solves while all the other problems were solved by the top contestants in under 40 minutes.

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

I have got an message from codeforces telling that one of my answer is matching with some other user. But I have not copied or not given my code to any other user. As far as I can understand maybe the other user has copied my code from ideone.com, i have valid proof of that. If someone can help please let me know and what would be the consequences that i have to face if it's not resolved.

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

    I don't understand, did you publish your solution? But why

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Some contestants hacked in problem B after contest and before rate change by dorijanlendvaj and the scoreboard does not change for them .Could anyone explain me why ?

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

Got WA on D in test 54 because I didn't know (1<<n) is an int from what I understood. How do you make it a long long then?

http://codeforces.me/contest/1220/submission/60799996

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

When will be the editorial?

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

I think problem D is one of the coolest C/D problems of CF rounds. So, I just want to put a detailed solution here :P, if anybody is interested...

Take two numbers $$$x$$$ and $$$y$$$. When two numbers cannot be in a bipartite sequence (the complement of required output)? If they both are in the bipartite sequence, we can find a cycle of length $$$\frac{x}{\gcd(x,y)}$$$ + $$$\frac{y}{\gcd(x,y)}$$$, which must not be odd. Also, both of the terms cannot be even (otherwise gcd could be doubled). Only fuss is when one of them is odd and other one is even. This essentially means that their least significant bits are different. Now, we already have a necessary condition — group numbers by their least significant bits, if two numbers are in the bipartite sequence, then they have to be in the same group. Wait, but can this be sufficient, meaning, can we take a whole group (the maximum sized one)? Trying not to be saviour of the human race, seeing that this is a Div2D, I quickly infer(?) that this has to be sufficient! Voila, AC! After the contest I proved it as follows: Let the chosen bipartite sequence be $$$S$$$ and $$$k$$$ be the lsb of all numbers i.e. $$$\forall x \in S, 2^k \mid\mid x$$$. Suppose, there is an odd cycle $$$c_1, c_2, c_3, \ldots, c_m$$$. Take a look at the values of $$$c_i \mod 2^{k+1}$$$. This value must be alternating between $$$0$$$ and $$$2^k$$$. So, if there is an odd cycle, it has an odd number of nodes, thus that cycle cannot afford this alternating property. Contradiction.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +16 Vote: I do not like it

    It can be proven more easily.

    If two numbers in the set are $$$(2a+1), (2b)$$$, then $$$2*(2a+1)*b$$$ makes contradiction. That means that all numbers are either odd or even. If odd -> we have a bipartite set of odd/even numbers. If even -> divide all numbers by 2.

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

      As for me, memento's proof is more interesting as it has some reasoning on how such an answer was obtained. In author's solution we as well started from $$$x/gxd(x, y) + y/gcd(x, y)$$$ to see that any pair of numbers with different lsb give contradiction and then we saw that if lsb is same, we can divide all numbers with it.

      Yours is, indeed, simple, but once again I'm confused with the fact that someone who tried to explain something and didn't make any mistakes while doing so gets downvoted.

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

        But the short proof also has reasoning. You start by looking for an obvious case where we get an odd-length cycle (odd+even), which gives two cases you need to analyse and notice that one is "ok" and the other can be solved recursively.

        I'm confused with the fact that someone who tried to explain something and didn't make any mistakes while doing so gets downvoted.

        CF.

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

mathforces

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

G has a lot in common with P5 from Romanian Master of Mathematics 2011: https://artofproblemsolving.com/community/c6h393848p2188641

Namely, following the same reasoning as in that mentioned problem (which is basically using a Steiner theorem or as some would prefer to put it — simple tricks on formulas) we get a conclusion that all candidates lie on a circle whose center is center of mass of antennas with some known radius.

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

    They're pretty similar indeed. Well, I'm not any kind of maths Olympiad guy, so I totally missed it. And yes, simple tricks on formulas is the way I prefer to call the intended solution :D

    Btw, are you talking about parallel axis theorem?..

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

      Yes, I am talking about exactly this theorem. When we shave off all that physics blabbering about some moments of inertia what we get is that

      $$$\sum d(P_i, Q)^2 = \sum d(P_i, C)^2 + n \cdot d(Q, C)^2$$$

      where $P_i$ are some points on the plane and there are $$$n$$$ of them, $$$C$$$ is their center of mass and $$$Q$$$ is some arbitrary point what immediately gives us $$$d(Q, C)$$$, what means that all hypothetical candidates for point $$$Q$$$ are on some fixed circle.

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

        Hey, moments of inertia are cool actually! Why would we shave them off? >:(

        I knew the theorem from the Physics, by the way, but couldn't relate it with the problem this time. Kind of shame for me, since it seems to be third programming challenge I give somewhere based on something near inertia moments :D

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

        Well, yeah. Moments of inertia are just symmetric bilinear forms after all, getting to a circle from that isn't tough. Even in experimental physics, if you want to know moments of inertia for any axis, you just need to measure 3 principal ones (corresponding to eigenvalues+eigenvectors) and use the fact that all moments of inertia lie on an ellipsoid.

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

.

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

Is the editorial published??

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

Now I realized that I misinterpreted D. I read "let all integer numbers be vertices" as "let all integers in the set $$$\bf B$$$ be vertices," and struggling with completely different problem...

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

    Really? I understand the same as you. Waiting the editorial for the analysis ...

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

Will the editorial be published?

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

I hacked my solution E after the contest. submission:60808754(https://codeforces.me/contest/1220/submission/60808754)

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

    I hope everyone is able to picture the meme that should be posted as a reaction and we can move on. You can save your upvotes for the poor.

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

    Can you please tell which case was missing?? k24

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

Please make an editorial. Or at least answer whether there will be an editorial.

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

how to solve problem C?

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

    the thing is when is you start with L=R=i you can never make R=R+K,K>0 as it will always increase the sequence lexicographically, also you only move to any L=L-K,s.t., a[L-K]<a[L],so it will decrease the sequence,so you have many options, but as first player wants to win he will place L for the leftmost possible,else the second player wins,always.

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

Hello everyone, I was wondering how accepted solution of problem D is solved. I was going through teh solution and noticed that i cannot come out with the same output as those accepted solutions. I think test cases are too weak for this problem. 2 1 4 My answer is 0 as both are disconnected and hence bipartite. But accepted code's output is : 1 4... Can any please explain where am i getting it wrong? SerezhaE

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

    Perhaps you are making the same mistake as me. Maybe you are thinking about a graph consisting from two vertices (1 and 4) and no edges, right? Actually, it's wrong. You have to think a graph with infinite vertices, among whom every pair of vertices whose difference is 1 or 4. Therefore, there exists a cycle of odd length, $$$0 - 1 - 2 - 3 - 4 - 0$$$, which means that this graph is not bipartite.

    I think the problem statement was ambiguous for some participants, and it was virtually impossible for those who misread to realize it, because sample cases on the problem statement was too small and has no explanation.

    → Reply