Блог пользователя tourist

Автор tourist, история, 5 лет назад, По-русски

Всем привет!

Скоро состоится Codeforces Global Round 5, время начала: 16.10.2019 17:35 (Московское время).

Это пятый раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

Соревнование продлится 2 часа 30 минут, вас ожидает 8 задач, при этом одна из задач будет представлена в двух версиях.

Разбалловка: 500 — 750 — (750 + 750) — 2000 — 2500 — 3000 — 3750 — 4000

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году:

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи раунда разработаны мной, а вот список людей, которым нельзя принимать участие в этом раунде, потому что они знали задачи заранее:

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

Так совпало, что это одновременно и те самые люди, которым я благодарен за то, что этот раунд такой, какой он есть.

Раунд будет идеально сбалансирован.

Присоединяйтесь!

UPD: Раунд завершён! Разбор здесь. Поздравляем победителей:

  1. Radewoosh
  2. Petr
  3. 300iq
  4. ecnerwala
  5. RomaWhite
  • Проголосовать: нравится
  • +3664
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Надеюсь этот раунд будет, как 2 или 4. С действительно хорошим балансом задач. А не А-700 и В-1700)))

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +524 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +340 Проголосовать: не нравится

Can tourist even think about question of level A and B

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +387 Проголосовать: не нравится

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. _/\_

»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Codeforces be like : best , better , bestest :D

»
5 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

But it is a soul for a soul

»
5 лет назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

4:19 Раунд будет идеально сбалансирован. 4:20 Sorry it is a DDOS attack. The round will be unrated.

»
5 лет назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится

You forgot to thank MikeMirzyanov and Codeforces.

»
5 лет назад, # |
  Проголосовать: нравится +118 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +108 Проголосовать: не нравится
GLHF
»
5 лет назад, # |
  Проголосовать: нравится +374 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +270 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

TOURIST!!!!!

»
5 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

A tourist written round? immediate upvote of round announcement

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Why on weekdays!!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope this round will be rated till the end

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -49 Проголосовать: не нравится

<3 <3

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +31 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

I wonder what "perfectly balanced" means?

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

tourist's round=upvote the announcement

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great ! so exited for the contest !

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +45 Проголосовать: не нравится

dont.jpg

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

It will be the best contest ever

I can't wait :)

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

So you wanna wipe out half of our rating? :3

»
5 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +147 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -77 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Will Um_nik overtake tourist in tourist's round?

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится +71 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Upvote too.

»
5 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

А как же поблагодарить за системы Codeforces и Polygon?

»
5 лет назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

When you just comment your opinion or a random comment :

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Tourist posting meme is something quite special

»
5 лет назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -55 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -66 Проголосовать: не нравится

Wish no DDOS attacks.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is a good time for wxhtxdy to being the highest rated guy on CF

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

Writers::Tourist

Wow.....It's Really Amazing

»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Can upvotes become equal to tourist rating?

»
5 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

tourist nb!!

»
5 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      or amusing

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +162 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I love tourist!

»
5 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

please , how many problems are prepared?

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Oneday, I will precede you, tourist.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +72 Проголосовать: не нравится

    BREAKING NEWS

    tourist tripled his practice after reading this

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

What will be the scoring distribution and the contest length?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hey guys watch me become grandmaster

»
5 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

And he is the guy with the high ground.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rank 3 contributors will come soon

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Раунд от тАуриста!

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

i hope problems grammar is clear as this blog :D

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -23 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

perfect Hello from tourist

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"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."

»
5 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C1 ?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
5 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Are they both not the same thing?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

      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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится
             6   
           /   \ 
          3     7
         / \   / 
        2   5 8  
       /   /     
      1   4      
      
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ohh i thought it was max depth til now lol

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the pretest 4 for C1?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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])

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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++;
        }
    
  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

How to solve problem E?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

    .

    .

    <----

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +5 Проголосовать: не нравится

    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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; }
»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

How to solve D ?

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Контест не сбалансированный, как это обещал автор. Задача С была сложной для такого балла. Минимум (1000 + 1000) нужно было сделать.

»
5 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

tourist, братишка, A — Бомба, давай еще!

»
5 лет назад, # |
  Проголосовать: нравится +154 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

editorial?

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

We all love G because of the reconstruction ;_;

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is the solution for C1 that fails on C2?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
5 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Я так и знал, что "Раунд будет идеально сбалансирован" — это постирония!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

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

    'Pseudocode':

    Edit. Same as errorgorn's explanation.

»
5 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -46 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Anyone use BIT to solve B?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

How to solve D ?

»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится
tourist making Reds and Oranges go derp on problem A
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
The problem-set was indeed balanced.
»
5 лет назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

Congratulations to Um_nik on the tenth place!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

 .

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

300iq, top 10 codeforces !!!

»
5 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

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!!!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The downvotes depict how much people care about what you think

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am a noob programmer but my** I accepted a problem in CF global round 5. But in the main test got no verdict at that problem then I clicked on my profile submission and I saw runtime error in case no : 1 how this is possible?****

»
5 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

when will T-shirts winners announce ?

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

Code
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
     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]);
    
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    (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.

»
5 лет назад, # |
  Проголосовать: нравится +102 Проголосовать: не нравится

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
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как мне подтвердить то, что мой код совпадает с кодом каких-то случайных людей? Решение первых часто бывает одинаковых, просто потому что там мало строк кода и идей, следственно и вероятность совпадения высокая.

»
5 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

проверь дз по алгосам у М3139 пж

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone use Kd tree to solve C2?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.