When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

tourist's blog

By tourist, history, 4 years ago, translation, In English

Hey!

On Oct/16/2019 17:35 (Moscow time) we will host Codeforces Global Round 5.

It is the fifth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

The round will last for 2 hours 30 minutes, 8 problems are waiting for you, and one of them will be proposed in two versions.

Scoring distribution: 500 — 750 — (750 + 750) — 2000 — 2500 — 3000 — 3750 — 4000

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me, and here is the list of people who can't take part in the round as they know the problems beforehand:

KAN, Endagorion, arsijo, Rox, lperovskaya, Aleks5d, Learner99, MikeMirzayanov.

Coincidentally, this is also the list of people I'm thankful to for making this round what it is.

The round will be perfectly balanced. As all things should be.

Welcome!

UPD: The round is over! Editorial is here. Congratulations to the winners:

  1. Radewoosh
  2. Petr
  3. 300iq
  4. ecnerwala
  5. RomaWhite
Announcement of Codeforces Global Round 5
  • Vote: I like it
  • +3664
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +524 Vote: I do not like it

I think this is tourist's way of telling Um_nik "Go ahead, enjoy being the highest rated guy on CF while you can".

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

Reason for so early registration opening or this has been done before?

»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

So, characters are from the Avengers in this round..

»
4 years ago, # |
  Vote: I like it +340 Vote: I do not like it

Can tourist even think about question of level A and B

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

    I bet they all sound to him like something of "what time is it?" difficulty.

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

      Actually I find it pretty hard to identify time in standard clocks xD

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

    Duh bro...... Every question is A or B for tourist xD!!!

»
4 years ago, # |
Rev. 3   Vote: I like it +387 Vote: I do not like it

normal setters(hours before contest) — We have tried our best to keep the round balanced,

tourist(days before contest) — The round will be perfectly balanced. _/\_

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Codeforces be like : best , better , bestest :D

»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

But it is a soul for a soul

»
4 years ago, # |
  Vote: I like it -50 Vote: I do not like it

You forgot to thank MikeMirzyanov and Codeforces.

»
4 years ago, # |
  Vote: I like it +118 Vote: I do not like it

Come on, snapping half of living beings sounds very short-sighted.

»
4 years ago, # |
Rev. 2   Vote: I like it +108 Vote: I do not like it
GLHF
»
4 years ago, # |
  Vote: I like it +374 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +270 Vote: I do not like it

$$$-150$$$ after the round feels like "Mr. Mike... I don't feel so good..."

»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

TOURIST!!!!!

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

A tourist written round? immediate upvote of round announcement

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Why on weekdays!!

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

    Maybe because they want less no of coders with their ratings fall ? :P

    .... Wait a minute, who's gonna miss Tourist's round xD ?

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

    Yes, why let more people to participate. Why would someone do that?

»
4 years ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

This contest announcement will definitely going to become the most upvoted contest announcement :)
UPD -: It has become the most upvoted contest announcement :)

»
4 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Everytime I refresh this blog, I can see an increase in the amount of upvotes.

»
4 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Hope there won't be any DDOS attacks...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this round will be rated till the end

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

i just upvoted the blog and then refreshed it ...then i was like Wait!..Am i worth 20 votes ?...because the number of upvotes are raised by 20

»
4 years ago, # |
Rev. 2   Vote: I like it -49 Vote: I do not like it

<3 <3

»
4 years ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

Wowwww.. tourist is writer o.0 this is opportunity for Um_nik to break rank 1 CF =))

»
4 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I wonder what "perfectly balanced" means?

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

tourist's round=upvote the announcement

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great ! so exited for the contest !

»
4 years ago, # |
Rev. 2   Vote: I like it +45 Vote: I do not like it

dont.jpg

»
4 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

It will be the best contest ever

I can't wait :)

»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

The round will be perfectly balanced. As all things should be

So do you wanna wipe out half of our rating? :3 I'm quite a bit afraid

»
4 years ago, # |
  Vote: I like it +147 Vote: I do not like it

2019-10-14-15-22-03)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    All of them worked very well not only tourist

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

      Relax, I just meant that everybody wants to participate in tourist's round.

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

        ^^ yass bro

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

        It also meant that you dislike other writers round which is not good.

»
4 years ago, # |
  Vote: I like it -77 Vote: I do not like it

It's tourist!!!The GOD!!!

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Will Um_nik overtake tourist in tourist's round?

»
4 years ago, # |
Rev. 5   Vote: I like it +71 Vote: I do not like it

As always, Pretests_Passed, accepted and SuccessfulHackingAttempt shall be welcome to the round. Meanwhile, may _Wrong_Answer, TLE, ISeeDS, MemoryLimitExceeded and YaAAbu stay away from our land. And let's all hope that Queue, DDos and unrated do not cast doom on this contest.

P.S. And the occasional appearance of PresentationError is also less than desirable.

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Upvote too.

»
4 years ago, # |
  Vote: I like it -45 Vote: I do not like it

When you just comment your opinion or a random comment :

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

    Same, I saw some other good comments got massive downvotes, I don't understand why there are so many random downvotes.

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

      Well, I mean there is also comments with upvotes too. Votes will be perfectly balanced. As all things should be.

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Tourist posting meme is something quite special

»
4 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Everyone is too much excited for the contest because of tourist.... I am also excited and also frightened about the difficulty level... Anyway hope this will be interesting...

»
4 years ago, # |
  Vote: I like it -55 Vote: I do not like it

rating++; CBGer are champions :>>>>>>>>>>

»
4 years ago, # |
  Vote: I like it -66 Vote: I do not like it

Wish no DDOS attacks.

»
4 years ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

Writers::Tourist

Wow.....It's Really Amazing

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Can upvotes become equal to tourist rating?

»
4 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Good luck and high rating to all! Can’t wait to see the problems :)

»
4 years ago, # |
  Vote: I like it -34 Vote: I do not like it

It's the time for Um_nik being the highest rated guy!

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

tourist nb!!

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I really don't know why i left a courteous comment but many people disliked it :< Because of my poor english??

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

    it's seem interesting with you but not everybody. you should comment something useful or amusing

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

      or amusing

      How does one know what is amusing to everybody, even top standup comedians don't know if they will bomb or kill.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably it's gonna be my last round this year, I hope to do well in it, at least to stay in Div. 1

»
4 years ago, # |
  Vote: I like it +162 Vote: I do not like it

if we have a long queue in the contest oie-89p-ATi9-PUAxh

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

The upvotes just crossed the number of upvotes in Good Bye 2018.

»
4 years ago, # |
  Vote: I like it -33 Vote: I do not like it

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

Hopefully this contest is as good as iberico ham made from pigs fed entirely with acorns.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

While everyone is waiting for the round to begin, I am also waiting for the editorials. Damn sure, the editorials are going to be short and crisp and with bags full of learning. All the best everyone!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I love tourist!

»
4 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Omg!! I can't wait!! I bet I'll learn a lot in this round.(hopefully without minus ratings.)

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

    Come on. Such comments only suit when immature kids like greens and greys post them. You are orange. Maintain some dignity

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

please , how many problems are prepared?

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Oneday, I will precede you, tourist.

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

    BREAKING NEWS

    tourist tripled his practice after reading this

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

      How making jokes is preferred than encouraging others? Idiots are spreading all the time. Go ahead, do whatever you’re good in! :D

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

        Okay let me motivate you. Tourist is even sweating head to toe. Go ahead man. Give him a tough fight. My best wishes with you

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

What will be the scoring distribution and the contest length?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey guys watch me become grandmaster

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Who are these people, that they still don't upvote at this round?

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I want to be a Candidate Master in this month :)

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

He is the chosen one... He will...bring BALANCE...

And he is the guy with the high ground.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rank 3 contributors will come soon

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i hope problems grammar is clear as this blog :D

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hoping for a CodeForces round, not an AtCoder round :P

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

    Hoping for no DDOS, no stuck queue, correct statements, no bugs in test data.

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

      I hope attacker buys a bunch of server and becomes poor and fails in attack eventually

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

perfect Hello from tourist

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"On Wednesday, October 16, 2019 at 15:35UTC+1 we will host Codeforces Global Round 5."

Real version:

"On Wednesday, October 16, 2019 at 15:35UTC+1 we will lost a lot of points."

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

After reading the names of the problems in the contest, one realizes what he meant by The round will be perfectly balanced.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to submit my code. It is saying that "you have submitted the exact same code before". Why so? Did anyone facing the same problem?

»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Achievement unlocked: pass pretests on (Harder) problem, fail pretests on (Easier) problem.

P.S. I had at least two severe mistakes in my code, still passed C2!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C1 ?

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

    Choose any point, and pair it with point that area will be minimised.

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

      Are there any corner cases for this solution? I did exactly the same but failed on the pretest 4.

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

        I think you might have had integer overflow; I also failed pretest 4 and had that issue.

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

    sort by x,y,z 1. first if two adjacent(in the sorted list) x,y are same then they can be pair 2. Once all with x,y equal pairs are done processing all adjacent pairs with same x can be pair 3. rest of adjacent two points can be pair

    need to wait system test but I solved it this way, hope its correct

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

      me too. but it's WA :( i don't understand

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

        Actually I did the same and I got TLE. I’m surprised

»
4 years ago, # |
  Vote: I like it +47 Vote: I do not like it

In E, I misunderstood for a while the condition of being perfectly balanced: 'max of depths" instead of "sum of depths". In that case it becomes a true counting problem, which I think is solvable in O(N log N)... If only I faced that version!

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

    Are they both not the same thing?

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

      If you only restrict max depth then you get a lot of play with some of the other vertices and can place them suboptimally; for example in the n=10 case for restricting sum of depths you are forced to have the complete binary tree on 7 nodes as your first three layers, and then the last three nodes can be distributed in the fourth layer, but when you only restrict max depth then you can take some of the nodes in the third layer and put them in the fourth layer without messing up the restriction.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
             6   
           /   \ 
          3     7
         / \   / 
        2   5 8  
       /   /     
      1   4      
      
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ohh i thought it was max depth til now lol

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

    Did you come up with something that can be solved by FFT?

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

      Exactly.

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

      Well, I did and i was wondering why i was getting WA6 and after the contest i realized that it's sum and not max...

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

    I realized that was sum instead of max only after reading your comment.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the pretest 4 for C1?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Spent 1h30m debugging C1, I can't pass pretest 5, did anybody have a similar problem? What was the mistake in your case? (I still can't find my error)

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

    I have some error and failed test 5. I don't understood what I did wrong. I wrote the stress, stressed some test with $$$n=50$$$, then remove some sorts which did nothing in the code, change some variable names and the second solution becomes correct. lol

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

    I had WA6. I reduced the 3d problem to 2d problem (for each x), and then to 1d problem (for each y). Whenever I could not find a pair from the same vertical line, I was looking for a matching point in another vertical line in the same vertical plane, and then was deleting it. Then some lines did not contain any points, and I was still iterating through them, so that made a mess (=WA).

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

    Well in my case I had 3 wrong submissions for pretest 5 .. but later on upsolved it.. What I did in my algo was first sorted the points on the basis of x and then y and then z. Then picked out pairs which are on the same line.. then on the same plane and then the remaining I failed pretest 5 because I didn't find the pair on same line correctly. What I did previously was that when in the sorted points list I found a pair I started searching for the next pair with first point ahead of the second point of the found pair. I changed it to first point should be ahead of the first point of the found pair and it worked! Hope it helps!

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

      Thanks, I just realized my stupid, stupid mistake, I had forgotten to add a return in one of the cases ...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasted more than a hour in D because I forgot to return value in query and Codeblocks does not even show that. From now on I will use pre-written codes.

»
4 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I think I missed 2 characters for H....................

UPD: Yep it was actually just 2 characters from my last minute submission.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    iterate through all b[i] reverse. keep a variable tmp and each time you iterate, update it to the smallest j such that a[j] corresponding to the b[i] has occured. Now for each b[i], it pays a fine if curresponding a[j] occured after tmp, else update tmp. (curresponding means the choosing j such that a[j]=b[i])

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

    use two i,j indices for in and out arrays, then if in[i]!= out[j] remove out[j] element from in array and j++

    otherwise i++,j++

    while (y < n - 1) {
        if (in[x] != out[y]) {
          auto pos = find(in.begin() + x, in.end(), out[y]);
          in.erase(pos);
          ans++;
          y++;
        } else {
          y++;
          x++;
        }
    
  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    My thought process during the contest went like this:

    Let t[i] be the time the i-th car entered the tunnel.

    So for instance: in[i]: 3 5 2 1 4

    Then t[3] = 0, t[5] = 1, t[2] = 2, and so on..

    Also keep the opposite array so you can determine which cars to fine, that is: inv[t[i]] = in[i]

    When the cars leave the tunnel, if there are two cars j and i such that j < i but t[j] > t[i], then that means that even though j entered the tunnel after i, it left the tunnel before i, so in that case car j definitely surpassed car i and j must be fined.

    Let's create a set s which will contain the entrance times of the cars that already left the tunnel.

    Now let i be the i-th exiting car, for every car j that's already left the tunnel and hasn't been fined (so they are in s) such that t[j] > t[i], j must be fined and removed from the set (you can do that by using upper_bound).

    Note this is $$$O(n\log{}n)$$$ because you insert and remove each element at most once.

    But after the contest I realized you actually don't need that set! You can just keep the minimum entrance time :`), though at least to me this way of thinking was more natural.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve problem E?

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

    .

    .

    <----

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

    Not sure. Thought answer is 1 if $$$n$$$ is between $$$[2^i , 2^i + 2^i/2)$$$, otherwise 0. got $$$WA$$$ on test case 6.

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

    I completed the code at the last moment but couldn't submit in time.

    Here's my solution in short:

    Perfectly balanced tree must have the condition that every level, except possible the last, must be completely filled.

    What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $$$u$$$,

    $$$ \text{key of parent} = u + \text{size of right subtree of } u + 1 $$$

    This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $$$u$$$,

    $$$ \text{key of parent} + \text{size of left subtree of } u + 1 = u $$$

    This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $$$h$$$ like this,

    For height $$$1$$$, there is only one tree, one node with no children. For height $$$2$$$, there is only one tree, one node with one child on its left and no child on its right.

    For each height $$$h$$$, let's store all the possible trees as a pair $$$(a,b)$$$ where $$$a$$$ is the number of nodes in the left subtree of the root and $$$b$$$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:

    For height $$$1$$$ possible trees: $$$(0,0)$$$, possible sizes: $$$1$$$

    For height $$$2$$$: $$$(1,0)$$$, possible sizes: $$$2$$$

    For height $$$3$$$: $$$(1, 2)$$$, $$$(2,2)$$$, possible sizes: $$$4$$$, $$$5$$$

    For height $$$4$$$: $$$(4, 4)$$$, $$$(5,4)$$$, possible sizes: $$$9$$$, $$$10$$$

    For height $$$5$$$: $$$(9,10)$$$, $$$(10,10)$$$, possible sizes: $$$20$$$, $$$21$$$

    Can you spot the pattern and prove it? For every height $$$\geq 3$$$, there are exactly two trees possible.

    Proof: If for height $$$i$$$ we have possible trees $$$(a,x)$$$ and $$$(b,x)$$$ where $$$x$$$ is even, $$$a$$$ is even and $$$b$$$ is odd, then for height $$$i+1$$$, we can have the right child only as $$$(b,x)$$$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $$$(a+x+1,b+x+1)$$$ and $$$(b+x+1,b+x+1)$$$, which can then be replaced with new $$$A$$$, $$$B$$$ and $$$X$$$ having $$$A = b + x + 1$$$, $$$B = a + x + 1$$$ and $$$X = b + x + 1$$$. Thus, we can say that the pattern holds by induction.

    Base case has $$$i = 3$$$, which is satisfied as $$$a = 2$$$, $$$b=1$$$ and $$$x=2$$$.

    So, find all possible trees till height $$$\log(\text{max value of n})$$$ and output $$$1$$$ if $$$n$$$ is one of those values and output $$$0$$$ if it isn't.

    AC Code: 62737057

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

    1 can be used on the left, 2 can be used oh both sides

    4 can be used on both sides, 5 can be used on the left

    9 can be used on the left, 10 can be used on both sides

    20 can be used on both sides, 21 can be used on the left

    so


    int solve(int x) { int cur[] = {1, 2}; int st = 0; while(cur[1] < x) { if(st == 0) { cur[0] = 2 * cur[1]; } else { cur[0] = 2 * cur[0] + 1; } cur[1] = cur[0] + 1; st = 1 - st; } return (x == cur[0] || x == cur[1]) ? 1 : 0; }
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

After a long time most difficult problem of codeforces will be changed.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D ?

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

    Here is my solution — First for each element calculate the next number in direction of clock which is less than half of this value. Build minimum segtree over this values. Then iterate elements in non-decreasing order, you can use segtree to get the moves from i then set value at i to infinity.
    Maybe there is not so coding solution.

»
4 years ago, # |
  Vote: I like it +154 Vote: I do not like it

Duh, I spent freaking hour on C, it was so hard to come up with for me >_>

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

    I am not retard anymore, thanks man for the motivation

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

      Exactly, now I can sleep peacefully at night knowing that I took 25 minutes for a problem that a red needed 1 hour for.

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

        He is exaggerating, he only took 35 minutes

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

          No, I am not, I spent fair amount of time thinking on this problem before getting E, probably even more than on E itself.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 3   Vote: I like it -8 Vote: I do not like it

          .

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

    Same happened with me...finally submitted at last minute. And didn't got time to even read D,E,..

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

    Agreed, C was much harder than DEF for me (at least if you include implementation)

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

    Good to know I'm not alone xD

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

    I thought there are more AC of C than D. Anyway how to solve F guys ?

»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

thanks tourist for the greatest contest of all time. great round whit great tasks!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

We all love G because of the reconstruction ;_;

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the solution for C1 that fails on C2?

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

    For each point, select the closest one? $$$O(N^2)$$$, I think.

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

    You can solve C1 in n^2, but not C2.

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

    I did this. For each point, iterate over all other remaining points, find the point which forms a cuboid with minimum area, and delete these two. Repeat till no points remain. O(n^2).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any easy implementations for C? My approach to C1+C2:

For all vertical lines (x = const, y = const) containing points, just pair them (and forget) in order of increase of z. Then, you do not care about z anymore, so just drop all the points on the floor and solve 2d problem (reducing it in the same way to 1d).

Looks simple but, damn, took hours to make it work.

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

    Well, you can just sort them by z, then y and then x.

    Then for adjacent points in this sorted set if they have same y and z, pair them.

    Then you do another round and pair those with same z.

    Then finally pair the remaining ones.

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

      Haha, it is actually the same approach, but very much easier to implement when phrased like this. Thanks mate!

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

    C2. Simple greedy solution with much sort. Easy implementation.

    'Pseudocode':

    Edit. Same as errorgorn's explanation.

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

The queue times today were amazing, best I have ever seen. Thanks Codeforces!

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

    one reason can be questions were good, so random submissions were less.

»
4 years ago, # |
Rev. 2   Vote: I like it -46 Vote: I do not like it

I am not smart as tourist, but I am smart enough to tell that this statement came out wrong- "The round will be perfectly balanced. As all things should be."(not talking about name of problems). I guess overconfidence is bad for everyone.

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Anyone use BIT to solve B?

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

    I almost did. Used ordered_set, shame on me

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

    I used segment tree.

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

    I did, though it seemed ridiculous to use BIT in B (which is supposed to be at Div2B level)...

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

      I actually thought the same but BIT is intuitive. Don't want to waste time thinking.And then I found no one use BIT in my room XD.

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

        I actually had no idea how I can do without BIT until I heard the solution from others lol Was kind of confused...

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In problem F, if there are no dominoes initially, number of ways for a (h, w) grid, $$$f(h,w) = f(h, w-1)+\sum_{i=1}^{h}f(i-1,w-2)*f(h-i,w-2)+\sum_{i=1}^{h-1}f(i-1,w-1)*f(h-i-1,w-1)$$$

where $$$f(h, 0) = 1,f(0, w) = 1$$$. Is this recursion correct? Edit: Okay, it was wrong.

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

    Why is it wrong?

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

      The two parts (upper and lower) created by placing a domino in the leftmost column are not independent.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got runtime error on test 1, but it works fine on my pc. It is simiar to this erorr: . Why does this happen? How can I get identically same compilers etc. on my machine? Because this is really frustrating.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Have you tried custom invocation?

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

      Yes, I am fixing it to work on custom invocation right now, but the contest is over so who cares now. I am just wondering why codeforces judge doesnt work same as mine. How can I configure my compiler to be same as cf custom invocation?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Protip: to win a contest, solve problems quickly and correctly. if you want to see the front of the queue + failures on systests, filter by verdict Rejected and go to the page where the queue ends. You'll also see your solutions there if they fail.

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve D ?

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

    Can't you wait for editorial

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Funny solution for C2 (surprisingly not the one I was unsuccessfully trying to debug for 1h30min...):

Use WSPD to solve the all-nearest neighbors problem in $$$O(n\log n)$$$. Observe that in the resulting graph, there is always some matching of size $$$\theta(n)$$$, which can be found greedily (max. degree is bounded).

We can surely print the matching and recursively solve the rest. The complexity of this is actually $$$O(n\log n)$$$, since we always divide $$$n$$$ by some constant.

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it
tourist making Reds and Oranges go derp on problem A
»
4 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it
The problem-set was indeed balanced.
»
4 years ago, # |
  Vote: I like it +90 Vote: I do not like it

Is the heuristic solution intended to solve H?

You can kill many heuristic solutions by setting the problem to sort a signed permutation instead of a binary sequence.

And I think this problem is also easy to solve by Google and find a paper of it.

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

    This was not intended, I probably should've done a better research beforehand, sorry about that.

    The intended solution uses exactly $$$n+1$$$ reversals, and I think it heavily utilizes the fact that it's a binary sequence.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +44 Vote: I do not like it

      My solution is deterministic and works for sequences over an arbitrarily large alphabet. More specifically, it does the following:

      Given a sequence of numbers $$$\pm1$$$, $$$\pm2$$$, ..., $$$\pm n$$$ where each absolute value occurs exactly once, we can do the following operation: choose a prefix, reverse it and multiply it by $$$-1$$$. Using no more than $$$2n$$$ operations I can transform it into $$$(1, 2, \ldots, n)$$$.

      Basically on each move we spend $$$2$$$ operations to do one of the following:

      • put some $$$k$$$ and $$$k + 1$$$ together in this order and then merge them into one block thus reducing the size by $$$1$$$
      • put some $$$-(k + 1)$$$ and $$$-k$$$ together in this order and then merge them into one block
      • if we have $$$k$$$ and $$$-(k + 1)$$$ in any order, it's also possible to merge them somehow
      • if we have $$$n$$$, we can move it to the end and pop back

      (after each operation we renumber the whole sequence for convenience, but it is more about the details)

      When it's not possible to do any of the above, it means that our sequence is exactly $$$(-1, -2, -3, \ldots, -n)$$$, and now we can alternate "flipping" prefixes of length $$$n - 1$$$ and $$$n$$$ ($$$2n$$$ operations in total).

      When we are lost with a sequence of length $$$1$$$ we may need to spend one more operation to make it positive. It couldn't occur in the last case, so in this case we spent no more than $$$2n - 2$$$ operations and the total number of operations is $$$2n - 1$$$. If we ended up transforming the $$$(-1, -2, -3, \ldots)$$$ then we spent $$$2n$$$ operations in total.

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

        Could you clarify what exactly is done when the sequence is $$$(-1, -2, \dots, -n)$$$?

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

          Do the operation with prefixes of sizes $$$n-1$$$, $$$n$$$, $$$n-1$$$, $$$n$$$, etc. Each pair of operations moves the last number to the beginning, multiplying it by $$$-1$$$. Consider it for $$$n=5$$$:

          • -1 -2 -3 -4 -5

          • 4 3 2 1 -5

          • 5 -1 -2 -3 -4

          • 3 2 1 -5 -4

          • 4 5 -1 -2 -3

          • 2 1 -5 -4 -3

          • 3 4 5 -1 -2

          • 1 -5 -4 -3 -2

          • 2 3 4 5 -1

          • -5 -4 -3 -2 -1

          • 1 2 3 4 5

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

with same code I got WA_on_33 for C1 and AC for C2 :3 and I should have got WA for C2 also :3 have you forgot to add the same cases for C2 which have been used for C1 ? :3

»
4 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Congratulations to Um_nik on the tenth place!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

 .

This was not all that balanced, to be honest. Though, I am not the one to complain, as I was too slow to write F in time.

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

    I'll opt for a response that's balanced between "completely balanced" and "not all that balanced": it was quite balanced for a combined division round. There's one problem that can separate the winner, one problem that can separate the top few from the rest of skilled contestants, two that can separate the skilled contestants from the rest, two that can separate roughly div1 from div2 and then some easy shit.

    The number of solutions in longer contests can be misleading if they span a wider range of points and situations like yours add some variance too.

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

      Well, you're right, it was a good contest. But it was the first time I was participating in a Global Contest and maybe I just like the classic format more, when you have time to think on harder tasks.

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

        I prefer that format too. I just don't care much about quickly solving easy problems or competing against low-rated people.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

300iq, top 10 codeforces !!!

»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

I think the contest should be rated for everyone who opens contest page not only for those who submit answers. Because one can check the problems and if they look unsolvable for him then he can leave the contest and nothing will happen!!!

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

    The downvotes depict how much people care about what you think

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

    I don't think so. Some people, like me, like to open the problems, think about how to do each question in their mind, and then do other things.

    Also, if you're strong enough, you don't need to care about these people.

    Every game will be as fair as possible, but it will not be absolutely fair.

»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

when will T-shirts winners announce ?

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I let one of my friends borrow my laptop... -198 :):):)

»
4 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I'm still unable to view other users' submissions for this contest. Is that intentional? (Submission links appear the way they do when the contest is still in progress.)

Edit: now it's working as expected.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Runtime Error in B on SysTests is not what I exactly expected. I mean I understand that is my fault, but it is really strange.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Since the test cases are still hidden, could anybody please help me find what is wrong with my solution for C1?

Code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
     const long long cur = calc(x[i], y[i], z[i], x[j], y[j], z[j]);
    

    is incorrect, it should be

     const long long cur = calc(x[i], x[j], y[i], y[j], z[i], z[j]);
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for your help! What a silly mistake that I couldn't find for hours!

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

62736318 62724834 Can anyone explain what is wrong in both submissions?

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

    If you want to divide a negative number by 2, doing (x >> 1) is wrong ._. It will break the structure of the int, for example, it will become positive.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm really comfuse that I only change vector to array then TLE bacame AC on problem D, can anyone help me. TLE AC

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

    (this comment is old, but in case you didn't figure that out) It's simply an out-of-bound write to array. The ans array is written to at indices > n+5.

    (It took me way too long to realize that it triggers undefined behavior, while if vector is used for ans then it would just cause WA and Codeforces can run the diagnostic.)

    When v is a local array, writing to indices past n in ans array would actually write to indices approx. i-n in array v (because of how GCC implement VLA), so it doesn't affect the result.

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

      Thanks you for looking my code and reply, that was really hard to figure out.

»
4 years ago, # |
  Vote: I like it +102 Vote: I do not like it

Finally, people who will receive T-shirts!

List place Contest Rank Name
1 1237 1 Radewoosh
2 1237 2 Petr
3 1237 3 300iq
4 1237 4 ecnerwala
5 1237 5 RomaWhite
6 1237 6 zemen
7 1237 7 izban
8 1237 8 mnbvmar
9 1237 9 rng_58
10 1237 10 Um_nik
11 1237 11 maroonrk
12 1237 12 LHiC
13 1237 13 jqdai0815
14 1237 14 ksun48
15 1237 15 krijgertje
16 1237 16 Golovanov399
17 1237 17 fivedemands
18 1237 18 hbi1998
19 1237 19 ppc_qjd
20 1237 20 yosupo
21 1237 21 zdolna_kaczka
22 1237 22 beginend
23 1237 23 pashka
24 1237 24 betrue12
25 1237 25 Cirno_9baka
26 1237 26 Egor
27 1237 27 zscoder
28 1237 28 rainbow_tree
29 1237 29 gop2024
30 1237 30 dreamoon_love_AA
45 1237 45 nikolapesic2802
56 1237 55 GaloisTears
106 1237 106 train_driver
127 1237 127 saketh
145 1237 145 codelegend
149 1237 149 user202729_
162 1237 162 AsrielDreamer
179 1237 179 ei133333
215 1237 215 RobeZH
225 1237 225 buko
242 1237 242 Simon
312 1237 312 hamlet
333 1237 333 SeventeenYears
419 1237 419 wildwolf_pty
432 1237 431 dilsonguim
439 1237 439 Okrut
455 1237 455 Infinityedge
481 1237 481 NoLongerRed
497 1237 497 hocky
498 1237 498 AwakeAnay
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone use Kd tree to solve C2?

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

    Can you elaborate more on how to use Kd tree for this problem?

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

      Yes, it can be used to solve C2.

      Just use Kd tree to get the closest point for each point and pair them together, there are O(logn) phases and each phase is O(N * sqrt(N)) or O(N * logN) if you assume points are randomly distributed. Overall the complexity is O(N * sqrt(N)) or O(N * logN) because the number of points gets at least halved in a phase.