antontrygubO_o's blog

Good Bye 2019
By antontrygubO_o, 5 years ago, In English

Hello again, Codeforces!

We are glad to invite you to Mathforces Thinkforces Good Bye 2019, which will take place on Dec/29/2019 17:05 (Moscow time).

Some information about the round:

  • Rated for all participants!
  • 3 hours!
  • No subtasks!
  • There will be an interactive problem in this round. You can read the guide for interactive problems here
  • Editorial will be published right after the system testing

All problems in this round were prepared by us, antontrygubO_o and 244mhq. We worked on this round for a long time and tried to make all the problems very interesting. We hope that you will enjoy the round!

We would like to thank:

The number of the problems and point distribution will be announced shortly before the round (or earlier).

Good luck and have fun!

UPD1: Using opportunity, we would like to advertise the match between tourist and Um_nik, which will start in half an hour after this round ends.

UPD2: The last contest of the decade on Codeforces will feature 9 problems .

Score distribution:

500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3750 — 4000 — 4500

UPD3: Editorial

UPD4:

Congratulations to winners:

  1. Radewoosh
  2. Um_nik
  3. yosupo
  4. FizzyDavid
  5. ksun48
  6. isaf27
  7. Petr
  8. WZYYN
  9. AndreySergunin
  10. saba2000
Announcement of Good Bye 2019
  • Vote: I like it
  • +1517
  • Vote: I do not like it

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

You forgot Speedforces, Gapforces and Checker-is-incorrect-forces.

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

is this rated??

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

    Nah, it doesn't matter because you won't lose your LGM anyway.

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

No subtasks! This is what already makes the round good

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

    What does it really mean though? Will our solutions be judged with all the testcases during the contest or will they be judged only after the contest is over? I'm deeply sorry for not knowing what a subtask is

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

    what is a subtask

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

      Two problems which only differ in the nature of constraints and the score distribution.

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

Wow, my favorite author is antontrygubO_o. P.S. How I want to see constructive tasks with weak pretests

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

Are you serious? should a cyan prepare such important contest?

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

    Are you serious? Should a cyan complain about a cyan preparing such an important contest?

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

      Are you serious? Should a cyan tell something about a cyan complain about a cyan preparing such an important contest?

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

        Are you serious? Should a pupil complain about a cyan complain about a cyan complain about a cyan preparing such an important contest?

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

          Are you serious? Should... Uh, sorry for bothering you, Mr. Grandmaster.

          (Edit: Mr. Grandmaster just changed his color just for this comment?)

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

            Stack overflow for real cyan!

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

              Are you serious? Is he a real cyan though? I guess it's time to show off my skills obtained by watching scooby doo since childhood. TIME TO UNMASK

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

    Only a newbie can prepare such important contest.

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

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

    only the coders with more than 2500 rating should make problems for such great contest

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

So you advertise your contest by saying problems are not gonna require thinking? Let me grab my HLD and suffix automaton. Or maybe I have even better idea. Skip the contest.

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

    Nope, these crossed-out words have the exact opposite meaning :)

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

    hello swistakk, why you are grabbing so much. I already told you as you grow older you as not as grabber as in your young days.

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

    You shouldn't really. I think he meant the opposite, that their contest will be labeled as "mathforces" by people who can't use their brain and can only press the buttons on their keyboards.

    Maybe that's only my taste, but previous contests by antontrygubO_o were really good.

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

      hey, what would be the color of your hair in 2020.

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

      Ok, thanks, I see that it indeed could be interpreted in two opposite ways and Radewoosh suggested to us the version I mentioned by writing something like "Ideal description of GoodBye, there will be no stupid thinking, I am so horny now" :P. And when I look at Anton's past problems indeed I think they were good, I really liked C and H from SEERC.

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

    → Reply
»
5 years ago, # |
  Vote: I like it +64 Vote: I do not like it
  • Favorite Authors
  • No subtasks
  • Three hours contests
  • Super-strong testers army
  • Div 1 + 2.
→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It looks like no of problems is not ready but editorial is ready :3

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

It's a delight to see a specialist posting the announcement. :')

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

Terrific way to end the decade. 3 contests in a row, just codeforces style.

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

2019: Give me your sadness and i'll keep it for you =))

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

Looking forward to antontrygubO_o's new haircut!

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

    Legendary problem setter > International grandmaster :)

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

I hope this year ends well :)

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

OOOohhh i get it now! it is number line-forces

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

Edit: This was meant to be a comment for the Div 3 Contest.

$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!

Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!

This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.

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

    This comment should be posted here.

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

    thanks for early editorial

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

      What editorial? Its not a solution. I am just posting a cool fact I thought I should share. And I have clarified on top that I posted this on the wrong thread. :)

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

P.S. — This was meant as a comment for the Announcement thread for $$$611$$$ Div $$$3$$$.

I really liked this Div $$$3$$$ contest because

  • The difficulty balance was decent. It was not too difficult, yet not too easy.
  • The problems were not very implementation based (like $$$598$$$ for example). After getting the basic idea, it was easy to implement it.
  • There were no subtasks

A great Div $$$3$$$ Contest to end the year !

mango_lassi I generally refer your solutions. How to solve $$$F$$$ ?

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

GOODBYE 2019!

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

A contest to tell goodbye every year. What about a contest to tell goodbye the decade?

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

It might take a decade to update the ratings! XD

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

nearly codeforce becomes best site in coders life :D

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

goodby contests are best

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

Hope there would be strong tests. I really don't want to be hacked in the last contest of the year

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

tourist vs Um_nik who will win ?. Enter your suggestion in reply .

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

can anyone explain why such things are happening on codeforces that : like this blog's author's rating is 2364 and they are showing him as specialist only. This problem is actually there with a lot of users

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

D was too nice for me.

Couldn't solve it.

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

Hoping to be expert after this contest.

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

9 problems :o I love it!

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

    I don't like it. Let's go back to good old days with 7 problems :(

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

      Well, I like the fact that you have to find yourself in every possible category to perform really well and can always find something for yourself if you just want to perform well. Also, it's good when the speed matters.

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

        I think it's better to have more time spent on individual problems because that means we can solve tougher problems for oneself.

        Of course, different round setters may have different ideas :)

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

        I think you love it because you become the first with it! Congratulations!

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

    I didn't participate partially because there are so many problems.

    [you] can always find something for yourself

    The number of interesting hard problems doesn't really increase if they use more of those easy and medium problems. IOI has 3 problems for 5 hours, ICPC has 12 problems for 15 hours (kind of). That's a lot of time to think about solutions. Doing well in a 9-problem CF round means that you likely spend at most 2-3 minutes of thinking on each of maybe 6 problems. Yay, so much fun.

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

4500 points!
Is this the highest ever score?

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

I think hacking will be so hard this round because of the magic :\

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

13k+ registration. I hope all works fine during contests.

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

    Yeah, and for 3 hours...

    I really hope the servers will sustain the pressure...

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

Best of Luck to Servers as well.

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

speedforces strikes again

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

syrian goverment be like : oh there's a cool round what a great time to shutdown electricity

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

MultipleAnswerForces

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

Interactive killed me

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

I have sent my solution for B from the main website, and after about half a minute of page loading I got 502 Bad gateway :( Since my submission did not appear on m2.codeforces.com, I submitted the same code from there, and — hooray! — both of my submissions appear Accepted, but I got 50 points penalty for resubmission. The codes are exactly the same, arsijo could you please take a look at it? Thanks.

P.S. Great contest by the way, nice thinking problems, and seems to be very well balanced!

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

ConstructiveForces

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

Solution to C :

Let's define s as the sum of a1 to am, and x as the xor of a1 to am. Append x to the array. Now the sum of (m+1) elements is s+x, and the xor of (m+1) elements is 0. And append s+x to the array. Now the sum of (m+2) elements is 2(s+x), and the xor of (m+2) elements is s+x. So the array becomes good.

In short, for any cases,

2

x s+x

can be the answer.

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

    How you came up with this solution?

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

      I put a pen on a piece of paper and found out in half an hour.

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

Jesus. This round was so fuckin good. The best in my entire life.

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

My solutions:

A B C D E F G H

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

How to solve D?

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

    pick k+1 elements ask every subset of k elements. Count the times of the minimum number appears. The answer is k+1 — times .

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

      Please explain the logic behind it too.

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

        if m = 1 it will be the minimum if it exist

        if m = 2 2nd smallest will be 2nd smallest if both 1 and 2 exist

        if m = 3 3rd smallest will be 3rd smallest if both 1 and 2 and 3 exist

        ........

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

      Ugh, now thanks to your comment the task seems super easy and my idea super ugly.

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

How to solve C?

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

    Print x,s+x

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it -22 Vote: I do not like it 
    for _ in range(int(input())):
    am = int(input())
    arr = list(map(int,input().split()))
    add = 0
    xor = 0
    used = []
    for i in range(am):
        add+=arr[i]
        if i == 0:
            xor = arr[i]
        else:
            xor ^= arr[i]
    if add == 2*xor:
        print(0)
        print("")
    else:
        used.append(xor)
        add += xor
        used.append(add)
        print(len(used))
        print(*used)

    Tell me, if u still don't understand it

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

      Can you please explain the logic behind your code?

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

        First you add Xor value to makeits value zero then you add Xor+Sum Its something like this:

        Sum Xor

        Sum+Xor 0

        2(Sum+Xor) Sum+Xor

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

        Let's say you have T where you calculate xor sum and S where you calculate normal sum.

        Now we add T and we obtain T xor T which is always 0 and S + T in normal sum.

        If we now add S + T, we obtain 0 xor (S + T) which is S + T always, and 2 * (S + T) in S.

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

Congratulations to the organizers/writers of the contest. As far as I can remember, this is the best codeforces contest I have participated in.

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

Goodbye 2019 and Goodbye ratings. (Great contest btw!)

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

It's neither Mathforces nor thinkforces.

It's Construct-forces :/

Problems are fantastic, but maybe I should say goodbye to both 2019 and my rating.

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

How did 88 people solve a problem tourist couldn't in 2 hours 30 minutes??

EDIT: looks like lots of heuristic solutions passed :(

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

    tourist got a call from his angry girlfriend that he never cares abt her....

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

Good bye 2019 and Radewoosh is on the way taking 1st place from Tourist. what an ending year!

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

Congrats to Radewoosh, first place at context, first place at top

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

Really nice problems, I especially loved C, E, G.

When I was fixed a bug in H, I switched to Chrome and a wild "Round has finished" pop-up has appeared. I hope it would have failed anyway :-)

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

    What is your solution to E?

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

      Split the points by the parity of $$$x_i + y_i$$$. If this is not a valid split, move all the points $$$1$$$ to the left if their parity is odd, to ensure it is even.

      Then, split the points by the parity of $$$x_i$$$. If this is not a valid split, move all the points to $$$1$$$ to the left and $$$1$$$ up if the parity is odd. Then, all coordinates are even. Divide them by two and repeat the whole process.

      Proof by AC.

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

H

I'm an author...

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

    Notorious coincidence

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

    For me it's not swapping but shifting an array. I can solve first but not second. How to reduce to swapping?

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

      Well, not reducing, but you can notice that for sorted (by value) array of positions it's enough to for every two neighboring positions $$$a$$$ and $$$b$$$ to prohibit cuts on segment $$$[a, b]$$$ (if $$$a<b$$$). So you keep a set of positions sorted by value.

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

        Oh wow. Very nice criteria. That makes me sad..

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

How to solve E?

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

    Observe that if two points with different parities of $$$x + y$$$ exist, then we can just partition the initial point set into points whose $$$x + y$$$ is odd and points whose $$$x + y$$$ is even. Otherwise, assume all sums $$$x + y$$$ are even (other case is similar) and transform all points so that $$$(x, y) \mapsto (\frac{x + y}{2}, \frac{x - y}{2})$$$. This preserves equality of distances and halves the maximum of $$$x^2 + y^2$$$, so we can just repeat this process until we get a solution (note that this has to happen since the input points are distinct).

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

      Thanks for the solution. I am not sure what'll happen when we have a points on a square. (1, 1), (1, -1), (-1, 1), (-1, -1). It'll transform to (1, 0), (0, 1), (-1, 0), (0, -1). And then? In the next step all will become (0, 0).

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

        if $$$x+y$$$ is odd, points will be shifted to the left by one first.

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

        To understand what the transformation does, draw some points with same parity of $$$x+y$$$ on a paper, then rotate the paper $$$45$$$ degrees.

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

    0) Move all points, so that (x0, y0) is at origin: Pi=(xi,yi)=(xi, yi)-(x0,y0);

    1) Let t(a) in {0, 1} be the group of a-th point (We can restore group A uniquely using t(0), ... t(N-1)

    2) Consider quadruples of points (a, b) (c, d) such that |a,b|==|c, d|. Using our array t this becomes t(a) xor t(b) == t(c) xor t(d)

    3) Define parity of i-th point as (xi+yi)%2

    3.0) If parity of all points is 0 (we must have at least 1 (0-th point) with this parity).

    3.0.0) All points have xi%2==yi%2==0. Then solve same task for "scaled down" version of this problem (xi/2, yi/2).

    3.0.1) There's at least one point with (xi%2, yi%2)==(1, 1). Then answer: t(i) = x(i)

    3.1) Parity of some point is 1. Then, assign t(i) = (xi+yi)%2.

    4) Why this works? For step 3.1. consider mod 2: (xa-xb)^2+(ya-yb)^2 == (xa+ya) + (xb+yb) = (ta ^ tb)%2 For step 3.0.1 consider mod 4: * distance between (0,0)<-->(0,0) and (1, 1)<-->(1,1) is 0 (mod 4) * distance between (0,0)<-->(1,1) is 2 (mod 4)

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

      Thanks for the nice explanation of a super nice solution. Could you please tell me, how did you come up with the idea of using parity of x+y? Did you guess randomly and then peoved, or did you make some observation?

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

        At first, I was surprised this can always be done, so I thought about the case where $$$y = 0$$$ and $$$x = 0, 1, 2, \dots$$$ — this seemed to work well with parity (and in no other easy to spot ways). I recalled when I solved a problem using a checkerboard coloring, so I then did the algebra (as shown by A_Le_K above) and concluded this should be the way to proceed.

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

My soln of G -
If 0 exists print it.
Else replace ai by i-ai
Now we have to find a subset of vertex such that ai+aj+ak+...=i+j+k+....
Since all elements are in range 1....n there exists a cycle in it.
Find it and print it.

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

    wow, great.

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

    How did you find that subset, which cycle you are talking about

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

      Permutation cycle.
      Basically find a permutation such that ai=j,aj=k,...., a_=i.
      Another way round create a directed graph with edges i -> ai. Find a cycle in this graph, and it can be proven that there exists a cycle in it.

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

    HOWRUSOGOOD??

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

    Damn that is smart. I spent half the competition on G but no luck.

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

    omg so beautiful

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

Didn't like D. Read the statement multiple times, but there was no mention of printing query in sorted manner, which caused WA.

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

    how to solve D?

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

      Keep querying for $$$k$$$ undiscovered elements at random ( you can do this $$$n-k+1$$$ times ). If at any point you already have discovered $$$k$$$ points, you can print answer then and there by querying those points.

      Otherwise, you have $$$n-k+1$$$ points discovered with $$$k-1$$$ points undiscovered ( and $$$n-k+1<k$$$ ). First thing to notice is, since you have asked for all sets of k points, the discovered points are all in the "middle" i.e. there will be $$$m-1$$$ undiscovered points smaller than all of the discovered points and $$$k-m$$$ undiscovered points greater than each discovered point. Now, for these $$$k-1$$$ undiscovered points, we can find where ( left or right of the "middle" part they lie ), with one query. Ask query without the point i ( $$$k-2$$$ undiscovered points ) and add 2 points from middle. It is guaranteed that response will be one of the middle points. If it is the smaller middle point, then i belongs to the "right" part, else "left" part.

      Then if you have identified $$$k$$$ elements as being in either left or middle or right part, you ask those $$$k$$$ points and again one of the middle points will be the answer. This time, you know all left points are smaller than middle ones, so ans is $$$left.size() + x$$$ ( position of response in "middle" ).

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

    My queries are not in order, but I got accepted?

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

      The only change between 67912676 and 67920459 is that I put the final query in a set ( i.e. which sorted it ).

      Difference in submission here.

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

        Maybe you printed some equal numbers.

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

          Looks like that is the only possibility, according to others' replies. Will see what case it failed on.

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

        Silly error! Forgot to put spaces in query originally.

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

    My queries are definitely not sorted, did not seem to be a problem o_O

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

What a terrible page error...

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

was it just me or anyone else who waited for an epic finish by tourist..?

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

How to solve D

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

How to check if integer is odd?

Normal people: x % 2 != 0 0 ms

Smart people: x & 1 0 ms

Me: x % 2 == 1 25 min

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

I hope there are some strong tests in G to fail stupid solutions (including mine), aren't they?

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

    What's your stupid solution? I tried but didn't manage to pass pretests with wrong greedies.

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

      I coded two different approaches. First one is shuffle numbers randomly in 100 random ways and check all subsegments, second one was some hill climbing. Hill climbing alone was not sufficient, but together with first one it was (maybe hill climbing wasn't executed even once on pretests, I don't know).

      EDIT: Indeed, shuffling (+1 check on sorted) and checking subsegments was enough to get AC.

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

    It seems that all stupid approaches sucessfully pass systests :<. So sad.

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

      I wonder if there is a way to prove that they are always going to work by demonstrating some nice lower bound on success probability; alternatively, what would be the test to break random_shuffle.

      (I also tried my best thinking about holes and pigeons, but didn't succeed on recalling how this one is supposed to be solved, so I ended up doing random shuffle too)

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

        $$$-N, (N-1), 1, 1, 1, \ldots$$$

        I think this will only succeed in probability $$$\frac{1}{N}$$$, since two large values should be close. So I added sorting by absolute value, but I'm pretty sure there is still a countercase.

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

can anyone explain B as TLE in my case ??

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

    We can prove that if there's two consecutive elements with difference > 1 output the index of the two elements else there's no solution.

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

Best contest that I participated, so far. Thank you, antontrygubO_o and 244mhq! : ) .

Happy to end this wonderful year with a beautiful contest, thank you Codeforces team as well!

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

7 out of 9 problems with tag "math".

I like Mathforces

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

67929171 why it takes wa? Can you tell me the test?

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

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

Was not able to see the simplicity in B and C :/

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

Who is waiting for the stream to start?

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

F and H can be, but the rest... Don't do such CF rounds... Ad hoc problems are OK individually, I liked each of your problems, but not a whole contest made up of them. How would you feel with 9 geometries or number theories? Already AtCoder doesn't make normal contests and uses only ad hocs, let CF stay normal.

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

    It's not like everybody thinks some sqrt decompositions and data structures are only "normal" tasks. I like original tasks and your normal is my definition of boring. I came here to think not to code and problem DEG were much more fun than FH.

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

      I also don't like doing the same all the time, F and H are different from each other. There are soooo many topics... Not only ad hocs and the rest...

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

        Yes, cause D, E and G were so similar, they almost felt like doing the same problem. /s

        It is not like problems can be partitioned into "sqrt decompositions", "data structures" and "other" and all problems within "other" category are similar.

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

          You have to try random options without knowing if they lead anywhere in these problems. Also, it's somehow random if you figure it out or not.

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

            Yeah, sure. Completely random.

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

              Don't you agree that F and H are definitely more deterministic?

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

                Sure they are, cause they are standard and boring. And now go to IMO where no hard problems are standard and tell all the USA and China teams that these problems require nonstandard thinking so they are random cause "you either get the good idea or not" and all their participants are just lucky every year.

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

                  It's programming competition, not math competition... And before you say something, I'm not saying that these problems are bad on CF, but there were a bunch of them. Why are you even competing in programming competitions if you expect only doing math/proving stuff?

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

                  Everytime somebody says "this is programming competition, not math competition" a kitten somewhere in this world dies. Do not do that. I do not expect math problems only, but problems requiring good amount of thinking are much more fun. Why don't you go to the industry if you love coding and hate all kinds of thinking?

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

                  Don't focus on what's fun for you, AtCoder already makes unbalanced contest because they are "fun".

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

                  "It's programming competition, not math competition..." said no one ICPC world champion ever :D

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

                  Didn't read a single comment from the thread beside yours.

                  It's programming competition, not math competition...

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

                  Well, now my comment is invalid, so sad :(

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

              Also, we aren't here to do math only...

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

                So you got two coding-heavy standard problems. Do you really feel overwhelmed by E and G and think it is beyond what is reasonable to put them in one contest? Or is the problem D the one that causes amount of thinking to overflow for you?

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

                  They weren't coding-heavy, they were easy as shit to implement if you KNOW HOW TO SOLVE THEM PROPERLY... See? You also have to know how to solve them and how to implement them as quickly as possible. That's your problem, you think that the only skill is coming up with the solutions, but there are so many side's of competing in contests and each of them has to be developed independently. That's why programming is a way better than math.

                  To DEG, how would you feel with 3 problems, one for centroids, one for HLD and one for some jump-pointers? I'd feel great, but I know that contests should be balanced and unfortunately this one wasn't enough...

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

                  In my opinion even the skill to know when you can try to squeeze too slow solution or when to try some random shit is important in contests. Unfortunately, even if the problemsetter has great math/coming-up-with-solutions/inventing-new-algorithms skill, then if he doesn't have PROBLEM-SOLVING(yes, it's definitely different than coming up with the solutions/coding)/competing skill the contest won't be prepared perfectly, what we can see in G's testset.

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

    Also, tests look poor... I wanted to hack someone's G with a test good enough to make people fail but to which my solution is immune, but there were no Gs in my room...

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

I think F and H is hard-coding but not hard-thinking Edit: It's wrong

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

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

G(almost) https://www.russiancodecup.ru/en/tasks/round/20/B/

Upd: also https://codeforces.net/gym/100239/problem/B

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

Goodbye 2019, we'll go in a new decade!

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

F is definitely easier than D and E for me. I don't even know how to prove my solution for E and my frustrating attempt somehow passed pretests...

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

    I would say it is much more standard: one may skip problem statement and only read constraints, and that would be enough to guess that we are asked to do some sqrt decomposition.

    Both D and E are in ad hoc land :) I wouldn't go as far as saying that they are harder than F, but they are much less standard to me.

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

How to solve B?

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

    Consider only subarrays of size 2.

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

    if the difference in absolute value of some adiacent integers si greater than 2 the answer is "YES"; Otherwise is "NO"

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

    can you explain the logic please?

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

      if you have adiacent values in the array the distance k is 1 and if the difference is >=2 then the answer is "YES" because 2>1 If there isn't anything with the difference greater than 2 than the elements are consecutive for example 2 3 4 3 2 and you can't have the answer "YES"\If the answer is "YES" print i and i-1 where abs(v[i]-v[i-1])>=2

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

Well this was pretty interesting. I didn't quite enjoy the round, but i also didn't hate it. Problem D as interactive is a big mistake IMO, since problem D is the one that usually is the barrier between easy and harder problems for most people. It was only a matter of finding the idea (which is what i don't like about interactive problems too much). It's like solving a riddle, not a true CP problem. I think it being problem G or H or even an easy problem B (to introduce some people to this concept) would have been a better idea.

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

Arterm ksun48 any idea why I works? I just wrote something which looks enough randomly and strange to be the hardest solution on this contest, having no idea if it calculates anything what makes sense...

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

    First assume all cells are 0 or 1. We work mod $$$2, x^{2^k}-1, y^{2^k}-1$$$ and consider polynomials in two variables, where cell $$$i,j$$$ represents the polynomial $$$x^iy^j$$$. The input polynomial is some polynomial $$$S(x,y)$$$, and we'd like to invert the polynomial, to find some $$$T(x,y)$$$ with $$$T(x,y)S(x,y) = x^iy^j$$$ mod $$$2, x^{2^k}-1, y^{2^k}-1$$$.

    Since $$$(P(x,y) + Q(x,y))^{2^a} \equiv P(x,y)^{2^a} + Q(x,y)^{2^a}$$$ mod 2, this tells us that $$$P(x,y)^{2^a} = P(x^{2^a}, y^{2^a})$$$. $$$P(x,y)^{2^k} = P(x^{2^k}, y^{2^k}) = P(1,1) = 1$$$ (as $$$t$$$ is odd).

    In particular the inverse of $$$P(x,y)$$$ is $$$P(x,y)^{2^k-1} = P(x,y)P(x^2,y^2)\dots P(x^{2^{k-1}}y^{2^{k-1}})$$$. Furthermore, $$$P(x^a,y^a)$$$ is also a figure with $$$t$$$ cells as it has $$$t$$$ terms, so we can multiply by this polynomial in time $$$O(tk 2^{2k})$$$.

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

when could we see others solutions?

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

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

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

GH is very cool. Kudos to author

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

How would one natually come up with the solution of G? It seems very hard to come up with the thinking process that would get you to find it.

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

    Well, this is a common technique in mathematics competition.

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

      Emmm, what is exactly common here? It's beautiful idea but I don't think I can name anything here as "_some name/word_ technique".

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

        "Beautiful"? Solving this problem involves nothing but decoding an extremely contrived statement (I can tell as somebody who solved it and never turned the brain on during doing so).

        (I am too lazy to explain my "thinking process", because yuhoooo already did it below pretty well.)

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

          "Solving this problem involves nothing but decoding an extremely contrived statement" — what the fuck?

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

            Do you agree that the problem is very easy after restating it in the following way: we are given $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$, all between $$$1$$$ and $$$n$$$, find a non-empty subset $$$S$$$ of $$${1, 2, \ldots, n}$$$, such that $$$\sum\limits_{i \in S} (i - p_i) = 0$$$ (at the very least, I very much suspect that the problem is not original when stated this way)?

            If no, then I am sorry. If yes, then I say that the only difference between this and the original problem is getting rid of a contrived statement $$$i - n \leqslant a_i \leqslant i - 1$$$ and replacing it with a more natural $$$1 \leqslant p_i \leqslant n$$$ for $$$p_i = i - a_i$$$.

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

          I totally agree with you, the solution is obvious due to the unnatural restrictions. I have a similar but more elegant problem from a math competition several years ago:

          There are $$$2^n$$$ distinct $$$n$$$-dimensional $$$\pm 1$$$ vectors initially, some of the components of some vectors are changed to $$$0$$$. Please find a nonempty set $$$S$$$ of vectors such that the sum of $$$S$$$ is zero.

          Solution: if a vector $$$v_1$$$ is changed to $$$v_2$$$, then we can consider $$$v_2$$$ to be $$$(v_1 - v_3) / 2$$$ Notice that $$$v_3$$$ will be a $$$n$$$-dimensional $$$\pm 1$$$ vector, the rest is trivial.

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

          I mean, what, that's a very big difference.

          For me, it was about having one number in range [-4, -3, -2, -1, 0], [-3, -2, -1, 0, 1], [-2, -1, 0, 1, 2], [-1, 0, 1, 2, 3], [0, 1, 2, 3, 4]. What isn't natural about this statement? It looks symmetric, looks reasonable, it's not at all obvious to me there needs to be a different restatement of the problem to solve it. A case such as -2, -2, -2, 3, 3 looks pretty natural under the original statement, and the given formulation suggests.

          If it's contrived, it means it should be easy to see through, or at least see that there needs to be a different restatement. But so many contestants didn't solve it.

          Just because you didn't spend much time on it doesn't mean you didn't turn your brain on to solve it. It's an idea you came up with, to subtract the i to the other side. Tons of strong contestants can't come up with that idea, and when I learned the solution after, I don't feel tricked, I feel that I just wasn't able to come up with that good idea.

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

            I agree. For me, during the whole time I spent trying to solve it I was picturing "sliding windows" of size n as intervals and, for me, it didn't feel unnatural at all, and I didn't feel the need to restate it in some other way.

            I guess it's one of those things that for some people it's very easy to come up with the good way of approaching this particular problem, and it might make it seem very obvious,

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

            Exactly my thoughts. Maybe $$$i-n \le a_i \le i-1$$$ doesn't look encouraging, but if you picture it as sliding windows it looks very nice. After reformulating it indeed looks even nicer, but as you and bicsi said as well, I didn't feel the need to look for reformulation since it already looked natural to me (it seems that of course I should have, however it could have been solved even without restating it as VadymKa explained below).

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

    You should somehow use weird condition $$$i-n\leq a_i \leq i-1$$$, it's much more nice to write this as $$$1\leq i-a_i\leq n$$$. After this one way to solve is to define new array $$$b_i=i-a_i$$$ and writing $$$sum=0$$$ condition for this array, which is $$$b_{i_1}+\cdots+b_{i_k}=i_1+\cdots+i_k$$$ and after this it's pretty easy to come up with cycle solution.

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

    There is also a solution by induction by Marcin_smu. He claims you can reduce problem for n to problem for n-1 by either removing maximum or removing minimum or removing both of them and adding their sum. Induction was kind of natural way of thinking here, but I couldn't make it work either.

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

      I guess it's quite easy to come up with the following solution: Consider some permutation of the initial array. In case we have two equal prefix sums, we also have a zero-sum subset (this idea is smth quite standard). Well, now it's enough to select a's one by one in a way that the current sum is between 1 and n — 1.

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

        "Well, now it's enough to select a's one by one in a way that the current sum is between 1 and n — 1." — but you can't really do that.

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

          Let's imagine that array values are actually hidden from us. If the current sum is k, then you need to select the next number from range [-k, n — 1 — k]. Instead of picking an arbitrary one, just go for a[n — k — 1]. If it's not available, you already have two equal prefix sums.

          It's in some sense identical to the solution from editorial, but this one explains some intuition behind the constructed graph.

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

            Wow, that is great! Too bad I thought about exactly that solution but missed final conclusion "If it's not available, you already have two equal prefix sums."

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

        What happens if you have only one or two positive numbers and the rest are negative?

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

      I also tried to work it out using induction, without much success.

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

Why can't I see other's submissions?

The contest ended quite a while ago!

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

antontrygubO_0 G is a beautiful problem, but did you even consider killing heuristic solutions -.-? I'll tell you what, random tests are not sufficient in such problems. Simple test that ko_osaga posted already cause my accepted solution to fail and probably a lot of accepted solutions from contest as well. I think if somebody thinks a bit more on tests then he can come up with tests that will fail almost all, if not all, heuristic solutions. It's obvious from the very start that this is "heuristicable" problem and creating strong tests, coming up with many heuristic and ensuring they do not pass is very important.

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

    We tried to cut heuristics and to come up with specific tests :c . Best tests we came up with were tests of the form:

    Fix some $$$i$$$ such that $$$gcd(i, n) = 1$$$. Take $$$a_j = i-n$$$ for $$$1\le j\le i$$$, $$$a_{i+1}$$$ is any valid number, $$$a_j = i$$$ for $$$i+2\le j \le n$$$. It can easily be seen that these kind of tests have only one subset with sum $$$0$$$.

    We added such tests, but, unfortunately, this wasn't enough. We are sorry for this and hope that you still enjoyed the round!

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

      Wow, it seems that vast majority of people actually got legit solutions. I was convinced it must have been the case that 80% of ACs are some random shit and just a small portion of them are provable, but it seems it is the other way around.

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

I really like these problems. They are short and easy to understand.

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

Why can't we view others' codes?

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

Thanks to the 244mhq, antontrygubO_o for this round. For me, this is the best round for 2019

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

Can submissions be made public? The contest has been over for some time now.

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

Is it intentional that I you can't see other people's submissions from this round?

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

Can you please open visibility all solutions?

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

I got disqualified from the contest and got a message saying that my solution for problem E coincides with the solution of gamegame. It must be some kind of mistake since I didn't copy any code from another place. (I can not see the other solution yet to compare anyway) Can anything be done about that?

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

    I can confirm that I didn't giveaway my solution and its not quite possible to steal, as I compile with my Dev-C++ locally (not ideone). I think its is a coincidence

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

      Notorious coincidence? Problem C too?

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

is it normal that other people's submissions are locked ?

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

saketh and I were discussing 1270E - Divide Points, and tried to uphack our solutions, but got "Unexpected Verdict", so we think something is wrong with the judge/checker.

Link to the two hacks: https://codeforces.net/contest/1270/hacks/608570 https://codeforces.net/contest/1270/hacks/608578

We used the test case

4
524288 0
-524288 0
0 524288
0 -524288

(the same as the second sample, just scaled up by a large power of 2)

Using custom invocation, socketnaut's submission (67907624) has no output for this input, and mine (67906687) outputs a correct answer, but both receive "Unexpected Verdict" (instead of "(Un)successful Hacking Attempt").

Is it possible to fix the judge/checker?

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

    looks like the checker has been fixed, thanks!

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

67939710 Why no TLE in B...? I found solve idea aleady but It's solution can be O(10000 * 2 * 10^5) so I assumed B is need O(nlogn) solution to solve...

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

I'm curious how can people read problems so fast and submit so fast.

For example tourist, he read problem A and B and solved them under 2minutes 59seconds. and then he went directly to problem E and he solved it in minute 7. which means he thought and coded it in 4 minutes.

Do people who are this fast, skim through all problems and find the easiest in their mind and then implement it ? like personally just reading A took me a whole 2 minutes

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

Can someone please explain to me how top coders solved E , it seems like most of them have used common and concise approach.

Thanks in advance! Edit :. The sol is above , didn't see that

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

Bye 2019，the year in which I met my girl friend

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

Statement of problem I defines x twice in the same context :(

... choose any $$$x, y$$$ with $$$1 \leq x, y \leq 2^{k}$$$, any nonnegative integer $$$x$$$, and ...

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

Thanks for the Christmas gift,it helps me to keep my master. I and each of my classmates who did this contest lost about 100 rating.

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

For the problem E: DIVIDE POINTS

Can someone explain me, how to divide the points into groups for the following example: (1,2), (9,14), (9,2) ?

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

    A: (1,2) (9,14) B: (9,2)

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

      Hey, thanks for your reply. I completely agree with your answer. But I just wanted to know how can we decide this division, when all of them are of the format (Odd,Even) and also they can't be scaled down by 2 ? (in reference with the tutorial). I would be thankful, if you could explain me that.

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

        If x coordinates of all points are odd, move all points (+1,+1)

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

What if we change B slightly (okay, maybe not slightly): you need not only to say if there exists some interesting subarray, but instead find the longest. I think I can solve it in O(n log n) with a bit of math, segment tree and sorting queries. Is there a simpler approach using greedy/dp?

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

Good bye 2019!

→ Reply