SerezhaE's blog

By SerezhaE, 21 month(s) 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, I_love_QMsh, 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

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

is it rated?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think copy pasted part has been skipped.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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. :)

    • »
      »
      »
      21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it -81 Vote: I do not like it

too late

»
21 month(s) ago, # |
  Vote: I like it -159 Vote: I do not like it

The time really fits Chinese! I love it!

  • »
    »
    21 month(s) 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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it -44 Vote: I do not like it

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +70 Vote: I do not like it

How many problems?

»
21 month(s) ago, # |
  Vote: I like it -13 Vote: I do not like it

Fast tutorial plz.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be a fun contest! :)

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +44 Vote: I do not like it

What about score distribution?

»
21 month(s) 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????

»
21 month(s) 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 :)

»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

I guess "problemes" is not the appropriate word!

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

300iq <3 contest .

»
21 month(s) ago, # |
  Vote: I like it -27 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can we use gcd?

      • »
        »
        »
        »
        21 month(s) 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 :(

        • »
          »
          »
          »
          »
          21 month(s) 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

          • »
            »
            »
            »
            »
            »
            21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.com/contest/1220/submission/60795097 Here is the code.

        • »
          »
          »
          »
          »
          21 month(s) 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.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank You. IslamOmar

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    why im so stupid to use gcd ?

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What do you mean? I couldn't understand. Do you think that using gcd is stupid? (Sorry for my bad English)

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you shouldn't think like that. This is not a stupid form. Maybe you could get to solution from that. And sorry for confusion, my English is bad :D

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        You are not the only one. Same happened with me. I had almost given hope on it.

        Happens when our way of thinking solutions is Depth First instead of Breadth First, it's our way of thinking.

    • »
      »
      »
      21 month(s) 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.com/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. ^_^

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        my hero

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I used cgd too but I got WA on test 21. Can you look at my code please? 60891456 It is a short input but I got WA and couldn't figure out why.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    21 month(s) 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)

  • »
    »
    21 month(s) 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.

»
21 month(s) 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

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    21 month(s) 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).

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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.
    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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 .

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

how to solve problem D?

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.)

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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)

        • »
          »
          »
          »
          »
          21 month(s) 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)

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) 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$$$... :(

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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...

      • »
        »
        »
        »
        21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    [Deleted]

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Awesome problems, really like them.

Nice job!

»
21 month(s) 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?

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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 ...

      • »
        »
        »
        »
        21 month(s) 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?

        • »
          »
          »
          »
          »
          21 month(s) 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)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

What a huge gap between C and D !!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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 :)

    • »
      »
      »
      21 month(s) 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?

  • »
    »
    21 month(s) 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]

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Thanks everybody. It was seriously difficult problem...

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        It does, but it's harder than intended solution

        • »
          »
          »
          »
          »
          21 month(s) 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.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          Well actually it didn't...

  • »
    »
    21 month(s) 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!

    • »
      »
      »
      21 month(s) 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!!!

»
21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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 ? :(

»
21 month(s) ago, # |
  Vote: I like it +50 Vote: I do not like it

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) 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)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

What is test 46 in E?

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It contains some cycle with zero weight.

»
21 month(s) 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)

»
21 month(s) 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

  • »
    »
    21 month(s) 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
    |                     |
    \--------------------/
    
»
21 month(s) 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?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe because of when the n gets bigger, gcd is getting closer to the a.

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank you very much

      • »
        »
        »
        »
        21 month(s) 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?

        • »
          »
          »
          »
          »
          21 month(s) 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).

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

»
21 month(s) 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.

»
21 month(s) 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.

»
21 month(s) 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 ?

»
21 month(s) 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.com/contest/1220/submission/60799996

»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

When will be the editorial?

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it -51 Vote: I do not like it

mathforces

»
21 month(s) 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.

  • »
    »
    21 month(s) 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?..

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

Is the editorial published??

»
21 month(s) 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...

  • »
    »
    21 month(s) 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 ...

»
21 month(s) ago, # |
  Vote: I like it +37 Vote: I do not like it

Will the editorial be published?

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it
  • »
    »
    21 month(s) 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.

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

    Can you please tell which case was missing?? k24

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

  • »
    »
    21 month(s) 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.

»
21 month(s) 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

  • »
    »
    21 month(s) 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.