tourist's blog

By tourist, history, 4 weeks 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
Announcement of Codeforces Global Round 5
 
 
 
 
  • Vote: I like it
  • +3664
  • Vote: I do not like it

»
4 weeks 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 weeks ago, # |
  Vote: I like it -82 Vote: I do not like it

Omg, the GOD of CP talking to us

»
4 weeks 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 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

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

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

Can tourist even think about question of level A and B

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

»
4 weeks 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 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Codeforces be like : best , better , bestest :D

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

I want to win a T-shirt, I hope I'll get it.

»
4 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

hope c is c and not e or f.

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

But it is a soul for a soul

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

You forgot to thank MikeMirzyanov and Codeforces.

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

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

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

»
4 weeks 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 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

TOURIST!!!!!

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

A tourist written round? immediate upvote of round announcement

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

Why on weekdays!!

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks ago, # |
Rev. 3   Vote: I like it -71 Vote: I do not like it

This is the first time I registered to participate in tourist's contest on Codeforces. Hope for high rating and a T-shirt as a souvenir.

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

Yes, I did nothing wrong. All things should be perfectly balanced.

»
4 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

For normal people tourist = Someone who visits a city, town, or historic site just for the pleasure of exploring it can be described as a tourist. For a programmer tourist = Gennady Korotkevich

»
4 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah Finally a tourist round :)

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

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

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

I hope this round will be rated till the end

»
4 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it -49 Vote: I do not like it

<3 <3

»
4 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I wonder what "perfectly balanced" means?

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

tourist's round=upvote the announcement

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

great ! so exited for the contest !

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

dont.jpg

»
4 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Finally, So happy to see that tourist is setting problems after a long time.

»
4 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

"The Round will be perfectly balanced." tourist has surely earned this confidence over the years of his Competitive Programming.

»
4 weeks 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 weeks ago, # |
  Vote: I like it +147 Vote: I do not like it

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

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

    All of them worked very well not only tourist

    • »
      »
      »
      4 weeks 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ^^ yass bro

      • »
        »
        »
        »
        4 weeks 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 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

I wanted to upvote for the contest but downvote for the tags so this balanced perfectly as all things should be. thanosdideverythingwrong but me, I am his greatest creation.

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

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

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

Will Um_nik overtake tourist in tourist's round?

»
4 weeks 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, Runtime_error_, MemoryLimitExceeded and Hacked 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 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

When I’m done, half of humanity will still exist. Perfectly balanced, as all things should be.

--Thanos.

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

    Now i got it why they are saying this round perfectly balanced

»
4 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Tourist=Thanos xD Him be like-

I am inevitable

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

Upvote too.

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Hmm, interesting...

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

When you just comment your opinion or a random comment :

  • »
    »
    4 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah.I think so, too.

    • »
      »
      »
      4 weeks 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 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Tourist posting meme is something quite special

»
4 weeks 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 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

WOW, tourist entered top contributors list

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

Wish everyone lots of good luck.

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

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

»
4 weeks ago, # |
  Vote: I like it -68 Vote: I do not like it

I hope this round is not balanced according to tourist, else A be like use segment tree D:

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

Wish no DDOS attacks.

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

Writers::Tourist

Wow.....It's Really Amazing

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

Can upvotes become equal to tourist rating?

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

tourist nb!!

»
4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Awesome!! hoping for good ratings :)

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Finally a tourist round :) Yeah Enjoy.........:)

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I love tourist!

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

Wow! This blog makes tourist one of the top contributors.

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

please , how many problems are prepared?

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

Oneday, I will precede you, tourist.

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

    BREAKING NEWS

    tourist tripled his practice after reading this

    • »
      »
      »
      4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

What will be the scoring distribution and the contest length?

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

hey guys watch me become grandmaster

»
4 weeks 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 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

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

»
4 weeks 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 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I hope there won't be a DDOS attacks sincerely.

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

Rank 3 contributors will come soon

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Best contest announcement ever!

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

i hope problems grammar is clear as this blog :D

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

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

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

perfect Hello from tourist

»
4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

I misunderstood perfectly balanced as perfectly balanced contest and not perfectly balanced problem statements.

»
4 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C1 ?

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Are they both not the same thing?

    • »
      »
      »
      4 weeks 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 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
             6   
           /   \ 
          3     7
         / \   / 
        2   5 8  
       /   /     
      1   4      
      
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ohh i thought it was max depth til now lol

  • »
    »
    4 weeks 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 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Exactly.

    • »
      »
      »
      4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the pretest 4 for C1?

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

    I initially failed pretest 4 then converted all of variables to long long :D after which it passed the pretests

»
4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You might fail sys tests as it looks n^2.

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

      I use a similar approach but i use a set where to keep track of outgoing cars, i check every time if a[i] is already out then i++ otherwise increment j while a[i] != b[j] and adding b[j] in the set and the final answer is the size of the set.

      Here is my submition.

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

        Thanks! I used set and changed auto pos = find(ALL(s), in[x]); to auto pos = s.find(in[x]);,then it passed.

        the solution in O(n) is more elegant.

  • »
    »
    4 weeks 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 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve problem E?

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

    .

    .

    <----

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Awesome round tourist. The questions were very clear and easy to understand. This made my day.

Thanks a lot!

»
4 weeks 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 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D ?

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +91 Vote: I do not like it

    I am not retard anymore, thanks man for the motivation

    • »
      »
      »
      4 weeks 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        He is exaggerating, he only took 35 minutes

        • »
          »
          »
          »
          »
          4 weeks 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 weeks ago, # ^ |
          Rev. 3   Vote: I like it -8 Vote: I do not like it

          .

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Good to know I'm not alone xD

  • »
    »
    4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial?

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

We all love G because of the reconstruction ;_;

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

What is the solution for C1 that fails on C2?

  • »
    »
    4 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C:

My answer seems to be correct in the first example but in the secound one it apears to me as if it was inverted (first line is at the end etc.). My code is in Java 62732376. (I think in this exact submission I changed the output order therefore the TreeSet in ex 1 apperas to be inverted)

My idea is to eliminate the negative values by shifting all values by 10^8. Then I maintain a TreeSet, which is ordered by the manhattan distance to (0,0,0) (Alternatively I would have tryed euclidian distance). Then I go on to say that the first element of the TreeSet together with the last will be contained in the last "Snap" (the next two in the pre-last and so on). This should allways remove two elements that are closest together, hence there is no other element in the bounding box.

Is my solution wrong or did I mess something up?

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

    Nevermind everything works as intended. I just didn't notice.

»
4 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Anyone use BIT to solve B?

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

    I almost did. Used ordered_set, shame on me

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

    I used segment tree.

  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is it wrong?

    • »
      »
      »
      4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Have you tried custom invocation?

    • »
      »
      »
      4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve D ?

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

    Can't you wait for editorial

»
4 weeks 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 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it
tourist making Reds and Oranges go derp on problem A
»
4 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it
The problem-set was indeed balanced.
»
4 weeks 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 weeks 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 weeks 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.

      • »
        »
        »
        »
        3 weeks 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)$$$?

        • »
          »
          »
          »
          »
          3 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

Congratulations to Um_nik on the tenth place!

»
4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

300iq, top 10 codeforces !!!

»
4 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The downvotes depict how much people care about what you think

  • »
    »
    3 weeks 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 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

It was not balanced.

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

when will T-shirts winners announce ?

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

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

»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What on earth is this pretest 5 of C1!!!!

»
4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      62747147 then why this one passed?

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

        Similar thing happened to me.. i think it's because float has -0 .. so without converting to int it can print -0.. which is not int... int has no -0, only 0. You can test it by giving -1 as input multiple times.

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

        This is interesting. I was wrong.

        Ok, so it was because of double 0.0 was outputted as "-0". It happens.

»
4 weeks 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 weeks 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 wxhtxdy
14 1237 14 ksun48
15 1237 15 krijgertje
16 1237 16 Golovanov399
17 1237 17 tmw168_orz
18 1237 18 hbi1998
19 1237 19 bip_oqq
20 1237 20 yosupo
21 1237 21 zdolna_kaczka
22 1237 22 beginend
23 1237 23 pashka
24 1237 24 betrue12
25 1237 25 Cinro_9baka
26 1237 26 Egor
27 1237 27 zscoder
28 1237 28 rainbow_tree
29 1237 29 DmitryGrigorev
30 1237 30 dreamoon_love_AA
45 1237 45 nikolapesic2802
56 1237 55 86723zyxjf
106 1237 106 train_driver
127 1237 127 socketnaut
145 1237 145 codelegend
149 1237 149 user202729_
162 1237 162 Promenade
179 1237 179 ei133333
215 1237 215 RobeZH
225 1237 225 buko
242 1237 242 Simon
312 1237 312 hamlet
333 1237 333 777777777
419 1237 419 seekluna_xrc
432 1237 431 dilsonguim
439 1237 439 Okrut
455 1237 455 Infinityedge
481 1237 481 UtahaSenpai
497 1237 497 hocky
498 1237 498 anayk
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

{Del}

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

Did anyone use Kd tree to solve C2?

  • »
    »
    4 weeks 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 weeks 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.