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

Автор ksun48, 8 лет назад, По-английски

Hello denizens of Codeforces once again!

After our last two rounds, Yang Liu (desert97) and I (ksun48) are pleased to announce Codeforces Round #492, which will happen on June 24, 2018 at 19:35 MSK. There will be two versions of the contest, one for users in Division 1 and one for users in Division 2. Both versions will have six problems, with four problems shared between the versions.

The round will feature our friend and superstar member of ACM-ICPC team MIT TWO, Allen Liu (cliu568).

The scoring distribution will be visible once the contest begins. As usual, we'd like to thank our wonderful problem coordinator KAN and Codeforces administrator MikeMirzayanov, as well as the rest of the Codeforces staff for keeping this site an amazing place for competitive programming. Thanks also to our testy testers winger, AlexFetisov, and demon1999.

This round is in honor of uDebug who have supported Codeforces on its anniversary. Thank you, uDebug! uDebug is an enthusiastic community of competitive programmers who help each other out by answering questions on chat, providing hints and solutions to problems from several online judges, furnishing test input and sharing feedback. On uDebug, you can select a problem you’ve coded up a solution for, provide input, and get the "accepted" output. You can visit it by the link.

Good luck! As always, we encourage competitors to read all the problems.

(̶a̶l̶s̶o̶,̶ ̶I̶ ̶s̶e̶e̶m̶ ̶t̶o̶ ̶h̶a̶v̶e̶ ̶h̶e̶a̶r̶d̶ ̶s̶o̶m̶e̶ ̶r̶u̶m̶o̶r̶s̶ ̶f̶l̶o̶a̶t̶i̶n̶g̶ ̶a̶r̶o̶u̶n̶d̶ ̶a̶b̶o̶u̶t̶ ̶a̶ ̶s̶p̶e̶c̶i̶a̶l̶ ̶ ̶s̶u̶r̶p̶r̶i̶s̶e̶ ̶w̶h̶i̶c̶h̶ ̶m̶i̶g̶h̶t̶ ̶b̶e̶ ̶h̶a̶p̶p̶e̶n̶i̶n̶g̶ ̶d̶u̶r̶i̶n̶g̶ ̶s̶y̶s̶t̶e̶m̶ ̶t̶e̶s̶t̶i̶n̶g̶,̶ ̶s̶o̶ ̶k̶e̶e̶p̶ ̶y̶o̶u̶r̶ ̶e̶y̶e̶s̶ ̶p̶e̶e̶l̶e̶d̶!̶)̶

EDIT: And the rumors are confirmed! Go to http://codeforces.me/blog/entry/60176 after the contest is over to discuss the problems or voice your complaints along with scott_wu and ecnerwala!

EDIT: Due to some last minute changes, each version will have six problems, with four shared problems.

EDIT: The Div. 2 score distribution is 500-1000-1500-1750-2500-2750 and the Div. 1 score distribution is 500-750-1500-1750-2250-2500.

EDIT: Congratulations to the winners of the round!

Div. 1:

  1. EvenImage

  2. Swistakk

  3. Um_nik

  4. bmerry

  5. ainta

Div. 2:

  1. Fortin

  2. Aleks5d

  3. KsCla

  4. hopcroftkarp

  5. davidberard

Thanks to everyone for participating! The editorial is available at http://codeforces.me/blog/entry/60217.

  • Проголосовать: нравится
  • +303
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by ksun48 (previous revision, new revision, compare).

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

"a special surprise which might be happening during system testing"

fast system testing!

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

Yaaay

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

I had enough surprises after today's D problem :(

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

Its for me:

)

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

Can't wait to see that special surprise :)

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

Is it on english only or you have russian version of contest too?

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

I heard that, as per this blog post, scott_wu and ecnerwala are going to call ksun48 immediately after the contest for a lively discussion about the contest.

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

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

why the score distribution will be revealed after the contest starts ?

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

I smell math problems.

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

is it rated?

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

How is scott_wu orange in your post? o_O

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

Why the 2 divisions are divided by 1900? Anyway I am glad to take part in Div.1.

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

I want to be the man with the worst contribution can you downvote me please?

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

Amazing email id: [email protected]

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

Will the conditions of tasks in the Russian language?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится -33 Проголосовать: не нравится
»
8 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

500-1000-1500-1750-2500-2750 not 500-100-1500-1750-2500-2750

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

Div.2 B = 100 points XD

EDT : Fixed

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

swap(C, D);

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

What exactly was the point of having a problem like div1 A which is conceptually pathetic but extremely cumbersome implementation?

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

hello i don't know my word is right or not bud div2 D problem was duplicated. here it's not a classic algorithm like shortest path it's the solution itself!

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

maths too hard~~

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

I solved Tesla in a very roundabout way...

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

thanks for beautiful task F

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

Stream starting now! Check out https://www.twitch.tv/ttocs45 to discuss problems and watch tests.

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

[Edited] http://codeforces.me/contest/996/submission/39627469 can someone point out the mistake with this dp implementation of problem E ?

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

Не знаю почему, но мне было намного легче решить задачу С из второво дивизиона, чем задачу D. Чувствую многие со мной не согласятся :D

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

IMHO, some of last rounds really proved that codeforces reduced quality of problems required for contest. Div1A — very easy to solve, very hard and boring to implement. Div1B — super simple and super old classic problem, I would expect it for div2A-B, not even close to div1A-B, div1C — duplicated problem.

Don't know about other problems though.

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

how to host contest :-

randomly select problams from other platform

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

One of the best rounds lately (IMHO), except that Div1C is boyan.

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

I cowarded out of submitting div 1 B and C and then it turned out both solutions were correct

How do you learn to prove greedies?

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

Я не понимаю. Многие решили задачу B двойным циклом. Но хаки не проходят!!!! Как это понять?? 7 раз пытался хакнуть, всего лишь один раз удалось сделать.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +113 Проголосовать: не нравится
1.59.59
»
8 лет назад, скрыть # |
 
Проголосовать: нравится +38 Проголосовать: не нравится

Despite known C, I really liked the problems. 'maintain sum of numbers in array' for div1D (and which takes 20 minutes to solve) is bold. F is beautiful. I also really liked B, nice easy problem.

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

I found B-F questions really nice, but it was totally ruined by that A, to the extent that I did not even take part. Loved the B-F problems though!

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

Is this idea for C correct?

Let the angle between two vector (a, b) the smaller one between (a, b) and (a,  - b)

Case n = 2 is trivial.

If n ≥ 3, then there are at least two vector i and j with angle smaller than 60 degree. And |i - j| or |i + j| will be smaller than or equal to max(|i|, |j|). So we can just add (or substract) these two vector up and we will have a similar problem with size n - 1. We can randomly choose any two vector until we find a pair that work.

I got WA on pretest 6 because I only do the random choice one instead of doing a loop (in a moment of panic), so I don't know if my idea is correct.

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

See this solution for problem B — http://codeforces.me/contest/996/submission/39628153 How is this passing the following testcase without TLE: 2 1000000000 1000000000 Can someone explain?

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

div2.C:toooooo difficult but 1500 div2.D:toooooo easy (than C) but 1750 div2.F:toooooo easy (than E and C) but 2750!!

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

I really think D gonna be a disaster. I am not even sure why my solution passed

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

div2C was frustrating.

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

It's not an often case for me when DEF have better ratio points/needed time than ABC :p (especially A which took me longest time XD)

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

can't understand div1.D QAQ

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

For Div 2 B, I failed to hack a solution with the case N = 2 and maximum a[i] values, when it directly simulated the problem situation. Can someone explains how this magician bamboozled me this badly?

P.S. This solution failed when run on the case on my own computer.

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

How to solve div 2 B ? I saw alot of bruteforce B that passed pretest

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

Solution for Div2D available ( https://www.geeksforgeeks.org/minimum-number-of-swaps-required-for-arranging-pairs-adjacent-to-each-other/ )

And the google query to get to this page was "minimum adjacent swaps to pair same elements".

It's ok if there are duplicated ideas, but if they are googlable by such easy keywords it is unfair.

Please take care so that it isn't repeated in future rounds.

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

My solution for div 2 B: http://codeforces.me/contest/996/submission/39614836 Will it fail?

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

Even there is several "strange solutions" for many tasks, thank you for great round ! It was really interesting solving this tasks :)

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

Such a surprise, random system testing!

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

today many div2 b will be failed

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

Even through my rating will go to hell after this round, and issue with A's difficulty and duplicated C, I enjoyed the problemset. Want to see more round where problems requires creative idea like this one on Codeforces in the future.

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

Can someone check my div1-F (didnt solve in time though).

Let dpn, d be a way to pay a subtree with root in n using a set of d different values. It's rather trivially constructed as

If d < n — that's the answer.

Otherwise lets construct Ek — number of ways to pay everyone using exactly k values.

And finally answer is

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

Expert for one day :D rip rating

Really enjoyed the set though :)

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

Your text to link here...

In which hell can these code pass the below test case?

7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

How can a 10^9 solution pass in a sec? This is quite unfair. The simulation takes no thinking and about 2-3 minutes to code and there's no chance of making a mistake. Many people got WA in system testing just trying to do it in the right way. Trying to hack thinking it'll get a TLE and getting "Unsuccessful Hack" is also unfair!

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

The difficulty for me: FBDECA.

It seems the problems are randomly shuffled for me :/

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

So I got accepted in E div1 but couldn't find any submission having the same approach.

My approach is to go from u to 0 to v. Treat u as a fraction p/q, the operations transform (p,q) to (p-q,q), (p+q,q) or (q,p) which are basically operations of Euclid's algorithm. Then I have to pick some q such that applying Euclid to (q*u%p,q) takes less than 100 steps.

I was sure that there are a LOT of q which satisfy the condition, so I chose it randomly. However, can anyone prove it, or at least give a lower bound of number of satisfying q?

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

I somehow managed to get AC on Div2E/Div1C by greedy...

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

Can anyone explain to me why the solution for Div2D is what it is. I cant understand

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

Can please someone tell me how are the solutions that are counting till a[I]-cnt <0 increasing count by one in each step are not getting tle when hacked ? I had two unsuccessful hacks due to this !! Not fair codeforces !!!

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

"a special surprise which might be happening during system testing"

I was really surprised! I have never thought my solution could pass system tests!

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

Crazy contest ToT. I am nearly become candidate master :((

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

I think problem Tesla was very hard

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

In Div.1 C Div.2 E can two vectors have the same x and y

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

http://codeforces.me/blog/entry/58229#comment-419511 — 2nd_places++ (recently also ++'ed on CSA) and still no 1st places anywhere xd

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

Just why geometric when we have a lot of good tags!!??

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

Div2 F/Div1 D is the most troll question on all of CF lmao

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

Is the sample explanation for question E wrong?

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

Can someone prove why this solution passed for Div.2 E? And if not provide a counter case that would disprove this.

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

div1B = Swap Pairing

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

EDIT: wrong contest