### Magolor's blog

By Magolor, history, 4 years ago,

This round is in memory of Leopoldo Taravilse.

Leopoldo Taravilse (ltaravilse) was a distinguished member of the competitive programming community in Argentina and Latin America. As a contestant, he reached the ACM-ICPC World Finals in 2010 and 2012, and was active in CodeForces and TopCoder. After 2012 he became a problemsetter for the ACM-ICPC South American regionals and the Argentinian Programming Tournament, and later coach for a World Finalist team in 2016.

Leopoldo's passion was helping others realize their full potential in competitive programming. He taught at various competitive programming schools in Brazil, Cuba, Peru and Bolivia, and his role organizing the Argentinian Training Camp cannot be overstated. Under his wing, it grew from a small group of friends in 2010 to a major event featuring international sponsors and having hundreds of participants coming from all corners of Latin America. Through successive editions of the Training Camp, Leopoldo inspired students to learn and improve, to give back to the community, and to have fun doing it.

With his intelligence, warm heart, relentless work ethics and witty sense of humour Leopoldo touched countless lives. We will miss him as a friend, a mentor, a teammate, a drinking buddy, a role model, an overall great person.

Rest in peace my dear Leo.

You can see this blog: A round in the name of ltaravilse.

And you can donate for prizes of this round: In Memory of Leopoldo Taravilse.

Hello everyone!

I'm pleased to announce: Codeforces Round #502!

This round will take place on Aug/08/2018 17:05 (Moscow time). It is rated for all participants and everyone will have 8 problems and 2 hours 15 minutes to solve them.

The contest is created by Magolor. This is the first competition I proposed. I hope that you will enjoy it. The heroes are from a TV show that I like and do not have any relation to Leopoldo.

6 of the 8 problems are created by myself. Thanks to:

• ODT for inspiring me and discussing the problems with me.
• Anton BanRussiaAtIOI Tsypko for examining my problems, helping me a lot on this contest and designing problems B and G.
• Max MaxZubec Zub, Danya danya.smelskiy Smelskiy, Sofia Sonechko Melnyk, Stanislav stanislav.bezkorovainyi Bezkorovainiy, Vitaliy kuviman Kudasov, Aleksandr Kostroma Ostanin, for testing the round and improving the problems and solutions.
• Mike MikeMirzayanov Mirzayanov for Codeforces, Polygon and the help he offered to me.
• Nikolay KAN Kalinin for helping with the contest and designing problem G.
• Ahmed ahmed_aly Aly for his initiative to host this round in memory of Leopoldo.

...Yet Another Chinese Round...?

Scoring distribution: 500-1000-1500-1500-2000-2500-3000-3250.

Prizes distribution: \$153 for top 30, delivered using bitcoin or amazon gift card (each contestant chooses).

UPD1: Chinese Editorial is published. You can view it through This link. English Editorial well be published soon.

UPD2: Congratulation to winners!

10.step_by_step

UPD3: English Editorial is published.

• +812

| Write comment?
 » 4 years ago, # |   +59 Prize distribution, wow
 » 4 years ago, # |   +220 It is really sad that such great people pass away...I have a suggestion. In several countries, there's a tradition called "moment of silence". Generally, it is a minute of silence during some important events as a gesture of respect. Can we all agree, as the community, that we won't submit anything during some particular minute during the contest?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -47 'moment of silence' cannot be done by no submission for some time during the contest.
•  » » 4 years ago, # ^ |   +255 With all my respect, I doubt this will be appropriate. A moment of silence is a period of silent contemplation, prayer, reflection, or meditation. If it's really meant for contemplation, reflection, etc, I would rather skip contest at all because you have to be in rather different emotional conditions during competition and during moment of silence. Switching between them forth and back in such a small time span seems both unrealistic and disrespectful.
•  » » » 4 years ago, # ^ |   -15 Just a suggestion, if it can be done like in football matches. A minute of silence before the contest begins? Maybe the problem statements are displayed a minute late and the round is of duration 2:14.
•  » » » 4 years ago, # ^ |   +13 I still think that would be appropriate, but looking at all comments below, I have changed my mind that would be a good idea. Nevermind.
•  » » » » 4 years ago, # ^ |   +138 Your idea came true. There was no one to submit in 25 minutes, only 502.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +24 rated&bitcoin i don't think that could happen, naturally server will be down for more than 1 minute don't worry.., btw i got your point!
•  » » » 4 years ago, # ^ |   +45 wow, are you a time traveller?
•  » » » 4 years ago, # ^ |   0 Did you use Velorian car? :O
•  » » 4 years ago, # ^ |   +67 Now everybody knows this was a bad idea. :(
•  » » 4 years ago, # ^ |   +83 i think the hardware of codeforces servers agreed with your opinion and made a few minutes of silence by their selves, even though it was not the thing that everyone wanted...R.I.P leo...
 » 4 years ago, # |   +22 Finally, Div.1+Div.2 combined round!
 » 4 years ago, # |   +4 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # |   -109 null
 » 4 years ago, # |   -581 Upvote if you are waiting new problems from Taravilse
•  » » 4 years ago, # ^ |   +296 You’re undebatably one of the most disgusting and miserable people I’ve seen here on CF.
•  » » 4 years ago, # ^ |   +59 you're a fucking piece of shit you know, have some respect for people who were friends with him. If I were in front of you I would hit you in your fucking face scumbag
•  » » » 4 years ago, # ^ |   -272 Blue guys are not allowed to hit my face
•  » » 4 years ago, # ^ |   -30 Seriously,I didn't expected that comment from u!!
•  » » » 4 years ago, # ^ |   -95 Are you jealous?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -29 Do you think this will help,vote-cheater?We admire Taravilse not because of your votes.
•  » » 4 years ago, # ^ |   +27 Even though this comment was obviously not written in good faith, does anybody know if ltaravilse had written any unpublished problems? They could be added to another round.
•  » » 19 months ago, # ^ |   +28 Upvote if you are waiting new problems from rotavirus
 » 4 years ago, # |   +12 WOW!The contest is made by a middle-school student Chinese ??
•  » » 4 years ago, # ^ |   -128 You f***ing racist f*ck. I bet you're white. Stupid white trash
•  » » » 4 years ago, # ^ |   +13 Sincerely, i wasn't racist at all. I was showing my respect to Chinese students because they are clever and prodigious.So,please never judge a comment directly without dissecting its real meaning
•  » » 4 years ago, # ^ |   0 It's surprising but normal :D In China, even primary school students can set up a contest add you can find them on some OJs. Show my respect to those 'dalao' OIers. orz
•  » » 4 years ago, # ^ |   0 It is actually a junior-high school (still very impressive). See Wikipedia.
 » 4 years ago, # |   -123 ooh. good. finally a combined round. so awesome people like me can really show my skills. I really should not be on Div 2. These losers man.....
 » 4 years ago, # |   +30 Rest in Peace Leopoldo ltaravilse Taravilse!!
 » 4 years ago, # | ← Rev. 11 →   +68 I'm glad to find the Chinese contest again. However,I'm sadder after noting the first part of this article and hearing that such a great person left. Hope the contest can be hold successfully. And hope Leopoldo rests in peace. I can't speak English very well,please forgive me. (So I hope that the description of the problems can be concise.)
•  » » 4 years ago, # ^ |   0 I agree with you so much.
 » 4 years ago, # |   +26 Sometimes I feel like this life has just been cruel, to make people, whom others love, pass away at such early ages...Too bad, never had a chance to know him or work with him before. Still, rest in peace, friend...
 » 4 years ago, # |   +23 2 hours and 15 minutes for 8 problems? That's quite challenging! :D
 » 4 years ago, # |   0 Does "Chinese round" mean wrote by Chinese or wrote in Chinese? If it is the latter, it will save a lot of time to understand the problems for the Chinese. By the way, I'm also looking forward to the Chinese editorial .
•  » » 4 years ago, # ^ |   +13 Maybe "Chinese round" means Chinese do not have to do the contest at midnight.:D
•  » » » 4 years ago, # ^ |   +11 But 22:05+2h15min=00:20... Maybe earlier than those start at 22:35 or even later. But I think if it means this, Codeforces Round #500 (Div. 2) [по мотивам EJOI] and Codeforces Round #503 are the "Chinese rounds" instead of this one.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +16 But I think we have to do this contest at midnight.We'll take parts in this contest from 22:05 to 0:20,isn't it?
•  » » » 4 years ago, # ^ |   0 I am a Chinese and now I'm travelling in USA now.It could be a good time for me to take part,but I didn't bring my computer:(
•  » » 4 years ago, # ^ |   +8 I think it's the former. Well, never saw the latter works before, but if the setters were generous enough, they might provide a link to the Chinese statements when the contest begun, maybe?
•  » » » 4 years ago, # ^ |   +6 A good suggestion!
•  » » 4 years ago, # ^ |   -18 Actually not. In fact 'Chinese round' means that the time fits Chinese people. Being a foreigner, hope that CF will prepare translation of the problems, of course it will save competitors lots of time understanding the problems.
•  » » » 4 years ago, # ^ |   +128 Actually not. In fact 'Chinese round' means that nobody will solve E div 1, one or two persons will solve D div 1, and about 10 people will solve C div 1.
•  » » » » 4 years ago, # ^ |   +13
•  » » » » 4 years ago, # ^ |   +34 This makes me think of ZJOI.
•  » » » » » 4 years ago, # ^ |   +16 ZJOI 2018 Day 1 is a nightmare. (We can only orz jiry_2)
•  » » » » » » 4 years ago, # ^ |   +23 qwq
•  » » » » » » » 4 years ago, # ^ |   +12 Wow！orz！
•  » » » » » » » 4 years ago, # ^ |   +12 Wow Orz!
•  » » » » 4 years ago, # ^ |   0 Your meaning is the problems wrote by Chinese are too hard for most competitors ?
•  » » 4 years ago, # ^ |   +14 Hey! I'm curious about how you find that? This blog was just created two weeks ago!
•  » » » 4 years ago, # ^ |   +8 It's just in your luogu personal page QAQ.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +8 I remembered that you wrote something about 502 error in your blog before the contest. A fantastic flag.
 » 4 years ago, # |   +12 I am sorry to hear that a great man passed away.In this round, it is more important to remember such a great man than to compete with others.
 » 4 years ago, # | ← Rev. 3 →   +36 IOI is comming, we lost a great man!R.I.P. ltaravilse
 » 4 years ago, # |   +1 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   -14 if (Div1 && Div2 && prize) {combine (Div1 + Div2);}
 » 4 years ago, # |   0 Mathforces?
 » 4 years ago, # |   +2 Why did CF merges Div1 and Div2 ？？
•  » » 4 years ago, # ^ |   +11 For prize distribution, perhaps.
•  » » » 4 years ago, # ^ |   +5 Oh? Maybe
 » 4 years ago, # |   +1 Really sorry for the loss :( May his soul rest in peace.... A great thing to honor him.....to which he dedicated his life most!!
 » 4 years ago, # |   +37 I will be part of this round just for you Leo(Been inactive for two yrs ), for all the things you teach us at the very beginning.
 » 4 years ago, # |   +203 Leopoldo was our coach. I met him first in 2005. We were Latinoamerican Champions in the ACM-ICPC World Finals in 2016. We had spoken 6 hours before he had the accident. So sad :(.Thanks for making this round
 » 4 years ago, # |   0 Rest in peace brother.
 » 4 years ago, # |   -93 Good that this Leopoldo Taravilse died. He is a piece of shit!
•  » » 4 years ago, # ^ | ← Rev. 3 →   +14 Why do you have to be toxic in every posts?
•  » » » 4 years ago, # ^ |   -23 Coz i like to spread negative vibes :)
•  » » » » 4 years ago, # ^ |   0 It's sad that there is someone so pathetic, having to look for attention in the most disgusting of ways.
•  » » 4 years ago, # ^ |   +3 If he is then what kind of useless stuff are you?Everyone has no permission to look down at such a great man.
•  » » 4 years ago, # ^ |   0 How can you say something like this for someone who has passed away? You are such a pathetic and disgusting person!
»
4 years ago, # |
-29

# Is It Semirated?

 » 4 years ago, # |   -97 Div1 + Div2 combined? My rating would be as dead as leopoldo now.
•  » » 4 years ago, # ^ |   0 You are a disgrace to the Codeforces community.
 » 4 years ago, # |   +19
•  » » 4 years ago, # ^ |   0 What's bad about common round?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 No offence,just crack a joke about the difficulty of Chinese Round(hell) .
•  » » » » 4 years ago, # ^ |   +47 Not all Chinese rounds are duliu >^<
•  » » » » » 4 years ago, # ^ |   +4 However,your last round is very duliu
•  » » » » » » 4 years ago, # ^ |   +2 yep! ( >﹏<。)
•  » » » » » » » 4 years ago, # ^ |   -8 Please trust me, Chinese rounds will make you "happy". I think that you understand my meaning.
•  » » » » » » » » 4 years ago, # ^ |   0 yeah...it makes me "happy".In another sense，maybe just lucky of survival.
•  » » » » » » » » » 4 years ago, # ^ |   0 Sorry, my meaning is that Chinese rounds will be very hard sometimes. Really, I agree it with you that survival is very lucky.
•  » » » » » » » » » 4 years ago, # ^ |   0 Rest in peace great Leo.
 » 4 years ago, # |   +29 Wish Leo a peaceful rest and Magolor a great debut.(Too sad GoFundMe doesn't accept PayPal for personal campaigns)
 » 4 years ago, # |   +6 RIP ltaravilse
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # |   +23 such people.... they have always inspired us by there great patience and fresh minds , a round is a great respect for soul that loved and lived its career sincerely , thnx guys for that great work and hope the best for every real worker like ltaravilse
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # |   +7 C and D have the same scores? Does it mean the difficulty will be similar?
•  » » 4 years ago, # ^ |   +4 Yes.
•  » » » 4 years ago, # ^ |   +6 Thanks.
 » 4 years ago, # |   -23 it will be great that contest starts 10 mins later so i could participare in it from the start
 » 4 years ago, # |   -42 Please, no delay
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   +223 Round 502 and Error 502Coincidence? I think not.Contest should be unrated imo. It's a pity since the problem-set is nice :(
•  » » 4 years ago, # ^ |   0 Hi. So to me seems like a notorious coincidence.
 » 4 years ago, # |   +5 Is it just me or Codeforces is heavily lagging ?
 » 4 years ago, # |   +4 looooooool what just happend !!!
 » 4 years ago, # |   +18 It's been a long time since the unrated round. That day has come!
 » 4 years ago, # |   -48 Looks like both Leopoldo Taravilse and Codeforces servers passed away, RIP :(
 » 4 years ago, # |   +18 It’s a pity to be unrated.
 » 4 years ago, # |   0 Unrated! Goodbye.
 » 4 years ago, # |   +139 Please, sorry to the issue. One of our subsystems failed completely unexpectedly. It was internal assertion failed in https://github.com/greg7mdp/sparsepp (Assertion num_deleted failed). We are investigating the issue. It was the first time ever this subsystems failed with such message.The round is unrated and the prizes are postponed to be awarded in some of the next rounds.Sorry again. I apologize to problem writer Magolor, the coordinators and everyone who helped prepare the round. You did a great and good job.
•  » » 4 years ago, # ^ |   +32 Unfortunate that this happened. As always, thanks for your hard work on the platform.
•  » » 4 years ago, # ^ |   +10 You should not make such announcements in the middle of the round (no matter how obvious it is that it will be unrated) because it just instantly kills everyone's motivation to continue with the contest.
•  » » » 4 years ago, # ^ |   +76 I think he did the right thing, it would have caused a lot of confusion had he not announced it. Those people who 'lost the motivation' would have felt worse after realising their time was wasted.
•  » » » 4 years ago, # ^ |   +26 However, tried your best but get nothing is also bad.
•  » » » » 4 years ago, # ^ |   0 Nah. Participating in a contest has never been "get nothing", especially with such high-quality ones like today's.It's not just rating bruh.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 deleted
•  » » » 4 years ago, # ^ |   0 Yeah, rated contest just bring out some kind of weird adrenaline and motivation. to solve problems.
•  » » » 4 years ago, # ^ |   +8 But what would Benq fill, if he found out that it is unrated after the contest? He took 1st rank, and he needs only 26 rating points to become a LGM!P.S. Benq, I believe you will do it next time :)
 » 4 years ago, # |   +8 A sudden notice of unrated makes me full-body relaxed.XD
 » 4 years ago, # |   +68 Magolor you struggled a lot to make this round happen and it's unrated now,i am really sad for this
 » 4 years ago, # |   0 So bad ToT
 » 4 years ago, # |   +62 Read the text carefully! Available
•  » » 4 years ago, # ^ |   +22 Successful Hacking Attempt +100
 » 4 years ago, # |   +6 Anyway,these problems are really high-quality. Many thanks for these amazing problems.
 » 4 years ago, # | ← Rev. 3 →   +89 The website became "502" during Codeforces Round 502 :PThe problems in this round is fantastic anyway :D
 » 4 years ago, # |   -67 How to solve the D problem? I could think nothing but tries.
•  » » 4 years ago, # ^ |   +21 The contest is not over yet.
 » 4 years ago, # |   -8 Such a nice contest in memory of the great person with interesting problems and prize distribution, ...and unrated =(
 » 4 years ago, # |   0 Sad :(
 » 4 years ago, # |   0 I liked problem D, but no comment for B and C
 » 4 years ago, # |   +98 I think unrated is fair to all participants . but is not to the author and coordinators .They spent lot of time on this contest but their work does not paid off.I can understand that there does not exist a solution which is fair to everyone . And I know the sudden fail is not anybody's fault . Hope there won't be next time . And I think the author needs to be compensated , if could .
 » 4 years ago, # |   +9 9141 participants we don't see this every day
 » 4 years ago, # |   +16 How to solve C : Participate in atcoder regular contest 91 (pretty recent contest). Participate in round #502. Copy-paste the solution from ARC91_E. Add 2-3 lines and submit the code before the server goes down. PROFIT !!! (actually not, it’s unrated xp)
•  » » 4 years ago, # ^ |   0 I have actually written a brute force code using small n values and deduced the relation from there
 » 4 years ago, # |   +7 How to solve D ??
•  » » 4 years ago, # ^ |   +6 Hint: There are at most 4096 different strings, and k is between 0 and 100.
•  » » 4 years ago, # ^ |   +11 make a mask for every string in the original multi-set and keep track of occurrence of every such mask, then brute force for every possible pair of masks where 0 <= mask <= 2^n what is the resulting cost for this pair, from this loop you can keep track for every mask m what is total number of strings s in the original multi-set such that cost of m with the mask representing s is at least k where 0 <= k <= 100 using cumulative sum. then every query can be answered in O(1).
•  » » 4 years ago, # ^ |   +1 You'll need to preprocess queries to answer them in O(1).First, let's mantain a set S for each different string (stored as an integer bitmask) and a frequency array, we don't need to use a STL set, because a vector (or array) and the frequency array will help us to avoid double counting. Then, we will have a matrix ans[M][K] that will contain the number of strings in the set that has Wu value with string M (bitmask) at most K, so we will use preffix sums to process them after. What we'll do now is brute force the mask M and use our "set" to compute the Wu values and do something like this (pos is the number of different strings stored in array v): for mask=0 to 2^n - 1: for i=0 to pos-1: act = 0 for k=0 to n-1: if (mask>>k)&1 == (v[i]>>k)&1: act += w[k] ans[mask][act] += frequency[v[i]] for wu = 1 to 100: ans[mask][wu] += ans[mask][wu-1] With that you can answer queries in O(1) with a preprocess of O(n2nmin(2n, m) + K2n)). Where K is the max value of k.Note: Try to use I/O that can make it on time, maybe scanf or getchar since the lengths are fixed. :D
 » 4 years ago, # |   +9 2 minute silence for Top 30 people !! :)
 » 4 years ago, # |   +6 D in custom invocation, no input, n=12,m=q=500000,all strings="111111111111", all queries="111111111111 100", all answers=500000: about 700 ms.D with scanf: about 1700 ms.D with cin+ios_base::sync_with_stdio(0): TLE.
•  » » 4 years ago, # ^ |   0 Can you tell me why this is happening? I always use fast IO using cin and cout and thought that the difference could not be that big (to give TLE I mean).
•  » » » 4 years ago, # ^ |   0 I think the problem is the difference between speed of reading STL strings and C strings (aka char*).
•  » » » » 4 years ago, # ^ |   0 Nope. 41361499 reads chars and still gets TLE.
•  » » » » » 4 years ago, # ^ |   0 Sorry, I should saw your code before writing something. Now, we talk about different things. I compared reading STL strings and reading C strings and you use char one by one reading (it's not the same as two methods, mentioned above).
•  » » » » » » 4 years ago, # ^ |   0 Can you link some documents about this? I always think read char must be faster than cin and cout. Yet I managed to get AC using cin + ios_base::sync_with_stdio(0) but gpt TLE using read char.Thanks.
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 Don't you know that Chinese Round are always DuLiu
 » 4 years ago, # | ← Rev. 2 →   0 Sad to know that the round is unrated. But, anyway, I really enjoyed these high-quality problems.
 » 4 years ago, # |   +22 How to solve F?
•  » » 4 years ago, # ^ |   0 Seem turn out to do how bruteforce :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 I have just written an Eratosphenes sieve with sqrt memory. I think it should pass
•  » » » 4 years ago, # ^ |   0 How did you do the sieve with sqrt memory?
•  » » » » 4 years ago, # ^ |   0 It has been described here
•  » » » » » 4 years ago, # ^ |   0 The time complexity of this method is still , right? I don't think that this complexity could fit the time limit.
•  » » » » » » 4 years ago, # ^ |   +8 Don't think so, it fits very well =)
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +6 My reaction after knowing this complexity can actually pass FCodeforces server is faster than light...
•  » » » » » » » » 4 years ago, # ^ |   +16 What will be your reaction when you find out about this project: https://primesieve.org/ ?)Spoiler: their sieve works 0.44s for numbers up to 1010
•  » » » » » » » » 4 years ago, # ^ |   +5 Isn't it a common sense that the performance of Codeforces servers is very good?
•  » » » » » » 4 years ago, # ^ |   0 A clue is modulo 232 so it is smth bruteforce.
•  » » » » » » » 4 years ago, # ^ |   +11 I don't think that has any influence. I think that sieve here is a bottleneck, not computations directly influencing result.
•  » » » » » » » 4 years ago, # ^ |   0 I've never seen this module and I used long long with this extrange modulo.Luckyly it was AC anyway
•  » » » 4 years ago, # ^ |   +98 If intended solution is to enumerate all primes then do bruteforce, then the problem is trash!
•  » » » » 4 years ago, # ^ |   0 It works 2 seconds in a max test, so I think yes:) It astonished me enough too when i had realised it
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +47 Exactly. This is one of the “outstandingly dumb” problems for me in the past 6mo ~ 1yr. It doesn’t even deserve its place in a joke contest. Something is broken in codeforce’s QA process. (FYI : the author doesn’t even do sieve with sqrt memory, you can check out that in editorial)
•  » » 4 years ago, # ^ |   +11 It seems you can just use eratosphenes with n/3 memory with bitset.
•  » » » 4 years ago, # ^ |   0 It worked out with almost stupid eratosphenes and vector bool 41370869. So even no need in sqrt memory optimization.
•  » » » 4 years ago, # ^ |   0 With bitset even faster 41371002
 » 4 years ago, # |   +29 The problems are nice, but those statements are just horribly confusing. Take an example (problem E): Then, this procedure will be repeated again with all new and old power sources. Repeated how many times? The most natural way to read this without considering the impact on problem difficulty is: repeated once.
•  » » 4 years ago, # ^ |   +13 Incidentally, the Russian translation says "repeated once" more clearly ("ещё раз", "once more").Of course I agree that the statements as a whole, and this particular part, could have been better.
 » 4 years ago, # | ← Rev. 2 →   +5 Don't know about others, but with all the tricks, problem D is just straight brutal in terms of thinking imo.Not something too hard to implement after you got everything, but to reach that state is another story...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 What was you solution to D? I thought it was straight-forward k*n * 2^n precomp and O(1) answers to queries.Of course, I did not implement in contest because i left after the server crash ( ͡° ͜ʖ ͡°)
•  » » » 4 years ago, # ^ |   0 Well, my idea is pretty much the same — pre-processing offline then O(1) to queries.But that processing part was straight deadly. Even O(22n * n) didn't fit in TL for me.At the near end I realized 0 ≤ k ≤ 100 (yeah, screw me), and changed the processing method to such with complexity of O(2n * 100).
•  » » » » 4 years ago, # ^ |   0 What was your 2^2n * n idea, I only thought of the one that relies on small K.
•  » » » » » 4 years ago, # ^ |   0 Literally, I tried through all pair of distinct strings (masked to integers for simplicity), and calculated that for each pair, what would the Wu value for that pair is.After calculating everything, I sorted the values, then start handling prefix sums.The queries would be O(log(2n)) due to binary search though, but that part is insignificant compared to the pre-processing.My (failed) solution: 41366581. Still I advise against seeing it, my source code today has been a huge mess :<
•  » » » » » » 4 years ago, # ^ |   0 Thanks for sharing. And now I can see why you thought it was so difficult xD
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 It didn't fit in TL for me too.Does the problem require some kind of Fast IO?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I'm not even sure.Even my "Pretest passed" solution (which was O(2n  *  100) in pre-processing and O(1) for each query) took about 1.4s for the worst case(sync_with_stdio switched off by default for better IO).
•  » » » » » » 4 years ago, # ^ |   0 I use scanf and it didn't pass in O(2^(2n) * n) :< Didn't realize k <= 100 though :<
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Probably not. You can usually get away with some other constant optimizations.Can you share submission?
•  » » » » 4 years ago, # ^ |   0 2^(2n) and pretests passed in 1s for me
•  » » 4 years ago, # ^ |   +2 I am too dumb lol. I was fixated on somehow manipulating the trie. But it was just precomp.
•  » » » 4 years ago, # ^ |   0 and I just realized i loop thru the wu array backwards lol.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Wu array? How did you solve D?I can't check your submission for some reason QAQ
•  » » » » » 4 years ago, # ^ |   0 https://pastebin.com/LtC9Nru7here loli fixed the bug here by making string to binary differently
 » 4 years ago, # |   +7 Thank you for the contest! Keep it up!In my opinion, the problems were nice. And I quite like the format where there are even more problems than the usual five. Plenty to choose from.However, there's room for improvement: the legends were not exactly a fit, and the Russian translation was not perfect either.
 » 4 years ago, # |   +11 This is probably a very dumb question but how do you solve C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +11 You should use sqrt-blocks.Here is sample for 17.[17] [13 14 15 16] [9 10 11 12] [5 6 7 8] [1 2 3 4]
•  » » » 4 years ago, # ^ |   0 Well... I implemented that during the contest but it turns out there are a couple of bugs in my implementation (starting from the fact that I printed no spaces between numbers in the "left-over" block). Your 17 example just so happens to point out both of my bugs :P
•  » » 4 years ago, # ^ |   0 What I did was try and divide the array into "blocks". If a block is of length k we will print out n-k+1, n-k+2, ... , n, n-2*k+1, n-2k+2, ... n-k. We see that the sum in this case is k + ceil(n/k). The k is from the LIS (the increasing blocks), and the ceil(n/k) because there may be one extra block, and by choosing the biggest from each block we will get LIS = ceil(n/k). Now, try for each k, and once you find the minimum sum, print the array according to the statement above. Please forgive my grammar, as I was writing this in haste :)
•  » » 4 years ago, # ^ |   0 cut into some blocks(use sqrt)such as 9 , cut into 3 blocks,then 7 8 9 4 5 6 1 2 3,make many increase Sequence.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 You can always partition the permutation of length n to have 2 specific LIS and LDS values where LIS = i where 1<=i<=n and LDS = ceil(n/i). example: n = 9 you can choose i to be 3 and so ceil(n/i) will be 3 and the permutation can be:7 8 9 4 5 6 1 2 3So you can easily get the i that minimizes i + ceil(n/i) and then construct the permutation in this way:if you have a permutation 1, 2, 3, 4, 5 and the best i is 2. Then you can construct the permutation as follows: 5 3 4 1 2another example is how I have constructed the permutation of length 9 earlier.That is if you consider the sorted permutation 1, 2, 3, ...., n and the best i is x. 1, 2, .., x will become the last x values in the optimal permutation. and x+1, x+2, ..., 2x will be the x values before them and so on.
 » 4 years ago, # |   +75 E is only about editing statement of appeared problem.
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # |   -10 That's good!But I think the difficulties between D and E was so big....maybe I'm too weak.orz
 » 4 years ago, # |   +4 I think codeforces servers have lost their power. Maybe for increasing the number of contestants. In the past a few contests were found that were rated, but became unrated!
 » 4 years ago, # |   -45 Was it really necessary to make it unrated? I mean, it was just a 20-minute delay, what seems to be an issue? Everyone was in an equal position.
•  » » 4 years ago, # ^ |   +16 During the delay, no one was able to make a submission. It is unfair to someone who completed coding a problem just before the delay happened, but then have to wait 20 minutes to submit it.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Well, delay time could have been spent on solving another problem. If you managed to do 4 problems in 30 mins, you should also look on E. There were a lot of ways to hold your time advantage.I'm truly disappointed, since this contest was combined, so a lot of Div. 2 programmers lost their chances to try competing with Div. 1 and lift their ratings quickly.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 It was unfair and inconsistent with previous decisions. There were much bigger issues yet rounds were rated as f**k.
•  » » » » 4 years ago, # ^ |   +5 Those should have been unrated as well.
 » 4 years ago, # |   +3 Can E be solved by constructing the convex hulls of the 2 engines and checking that one of these 2 convex hulls can be obtained from the other by only rotations and shifts?
•  » » 4 years ago, # ^ |   +3 Ya.
 » 4 years ago, # |   +31 Statement of H was very bad. It took me more than 15 minutes to understand it.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +16 Many statements were very bad. "English by old people from post-communist countries" tier bad. The whole contest seems like it was made in a hurry just to have it before the authors leave for holidays or something.
•  » » » 4 years ago, # ^ |   +18 It wasn't bad English-wise. The story was very bad, complete mess. Idea of films and their endings and ways of combining them was very confusing. I could go on.
•  » » » » 4 years ago, # ^ |   0 I don't mean just bad grammar, but the kind of lack of understanding of a language that causes the stories to be bad because you can't express yourself well. And I don't mean just bad English, I'm pointing it out as an example; the statements were very hard to parse overall.
 » 4 years ago, # | ← Rev. 2 →   +44 Both FizzyDavid's(41352396) and tqyaaaaaaaang's(41353078) solution passed system tests in problem E.But their output for this input is different:4 40 00 55 05 50 34 07 43 7(I think it should be 'YES')How did all these happen?...(Problemsettings are satisfactory, though...
•  » » 4 years ago, # ^ |   +41 Lol, yeah. FizzyDavid considers just rotations by multiples of 90 degrees which are obviously not sufficient (consider segments from (0,0) to (4, 3) and (3, 4))
•  » » 4 years ago, # ^ |   +27 Sometimes system test is very weak, especially in unrated rounds.
•  » » 4 years ago, # ^ |   +16 Yes. It was my fault.Tests are weaker at the beginning.Then I was asked to generate better test in order to hack:incorrect hull, use only area and length, use only dot product, ... strange solutionsI thought it is strong enough...I forgot this one. Sorry.(Actually, I believe it may pass at first... My fault.)
•  » » » 4 years ago, # ^ |   +3 Will there more tests added? Will all the solutions be rejudged?
•  » » » » 4 years ago, # ^ |   +3 We will add this test. But this won't influence the standings due to the contest rules.
•  » » 4 years ago, # ^ |   +3 BTW: Why no one hacks?
•  » » » 4 years ago, # ^ |   +16 It's useless to hack when it's annonuced to be unrated..
•  » » » 4 years ago, # ^ |   +16 Too many approachable problems :) . I usually turn to hacking when I have no immediate idea of what to do with the next problem, and I believe many others do too. Or when hacked solutions just start to appear, which was not the case today either.
 » 4 years ago, # |   0 Can someone explain the solution of div2b please !!
•  » » 4 years ago, # ^ |   +9 Consider the cases where moving a 1 or a 0 in A will change the OR of elements: moving a 1 to a column where both string A and B had a zero A[i] == '0' && B[i] == '0'. Moving a zero to a column where only A had a one A[i] == '1' && B[i] == '0'. Now, if you follow those 2 cases and look closely, You can see that you can move all the ones (let's denote them by countOnes) from A to the positions where both A[i] and B[i] are zero (let's call those positions validZeros), but, you can only move the zeros from A that have a 1 below them (let's call those moveZeros), and it's only worth to move them where case two happens. Let's call those ones that have a zero below them validOnes. Now, for all ones in A, you can move them to validZeros positions. For all moveZeros in A, you can move them to validOnes positions. Therefore, the expression ends up being: countOnes*validZeros + moveZeros*validOnes
 » 4 years ago, # |   +1 Does anyone have a good proof (or can read the Chinese editorial) for why using sqrt blocks are optimal in C? To be clear, I understand that if you are using a block method, that sqrt blocks would be the best size, but it's not clear to me that using a block method would be optimal.
•  » » 4 years ago, # ^ |   +20
 » 4 years ago, # |   +85 After seeing the F and being not able to think of anything other than brute force(I was hoping some good math in there since it is obviously F).I started watching FC Rottach-Egern — Bayern München which was more interesting than E and F questions.The questions are not bad but estimation of level is very bad.F could be div2 C(at worst D) I guess.
•  » » 4 years ago, # ^ |   -10 E was interesting. It uses interesting concept of convex hull + string matching.
•  » » » 4 years ago, # ^ |   +16 I could barely understand the question(mainly the legend in behind the question) and the examples were barking on my face to match the convex hulls.I liked implementing it without using doubles.But surely it is not worth E.The idea was good but the problem was not good overall at level of E.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +40 No need to use double. Assume we have polygon A1,  A2, ...,  An, then just match sequence (dist(A1,  A2)2,  dist(A1,  A3)2,  dist(A2,  A3)2,  dist(A2,  A4)2, ...).May wrong :)
•  » » » » » 4 years ago, # ^ |   +5 Yes I did something similar.I used side lengths and dot product of adjacent sides to represent angle.
•  » » » » » 4 years ago, # ^ |   0 Wow! Can someone confirm this is correct?
•  » » » » » » 4 years ago, # ^ |   +30 The sequence of pairs (side length, angle) is obviously correct, and if we replace angle with dist(Ai, Ai + 2) it's still correct, as we can restore angle by lengths of triangle sides.
•  » » » » » » » 4 years ago, # ^ |   +8 Aren't there 2 possible angles if we know the sides?
•  » » » » » » » » 4 years ago, # ^ |   +22 Nope. Law of cosines. There are 2 possible cosines (α and  - α), but since the polygons are convex, it doesn't matter. You could always use all sides + area (sine and cosine) to make absolutely sure without having to prove anything, of course.
•  » » » » » » » » » 4 years ago, # ^ |   +8 Thanks, I get it now.
•  » » 4 years ago, # ^ |   +2 F could be div2 C(at worst D) I guess. Div2C? If you want to make a horribly unbalanced round, yeah.Div2D/Div1B is a reasonable difficulty estimate, going by my impression and the number of successful solutions. Here's my idea: 3·108 is just 36 MB in a bitset, so let's optimise by ignoring numbers which aren't 1 or 5 mod 6 and do a classic, but constant-efficient sieve. This is a perfectly fine div1B; if pretests aren't too strong, people who don't test on maxtests can get burned and other people can get hacking chances. (I'm normally not a fan of weakening pretests, since I don't want to keep worrying if there are some weirder tests that make my code fail systests, but if I'm computing something that's known at compile time, I always check if it's good enough on maxtests or just hardcode maximum limits into it.)
•  » » 4 years ago, # ^ |   +11 It hurts me so much that I can't even solve a Div2.C! XD
•  » » » 4 years ago, # ^ |   0 I was under the impression that doing extended seive over blocks works reading the comments. If it works then it surely is not more than Div2D right. I take back my claim of Div2C in case it doesnt work. But extended seive with easy implementation is good enough for Div2C.
 » 4 years ago, # | ← Rev. 4 →   -55 For f**k's sake!There were much bigger shitstorms (queue blocked for more than half of the contest, terrible statements and mistakes in the problems) on cf and rounds were never unrated. I get used to the fact that no matter what, the round will be rated because majority would be happier. For some strange reason this time it was, even though it was only 20 minutes of server unresponsiveness yet problems were available to solve.Wtf cf?Edit. Is it because of money prizes or what? Why to disappoint everyone this time?
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   +98 AhhhhE and F, the two problems which roughly determine the 4-200 section of the standings in this contest are of poor quality.E: disguised polygon congruence, a known problem and not a trivial one. If it were unknown, it could even be an F or a G by difficulty IMHO. Furthermore, as pointed out by others, the tests aren't very strong. They might be strong, but for this kind of problem they need to be stronger. For example, my first submission which makes an ordered triple (length, length, area) for consecutive vertices and then compares these cyclic sequences passes the system tests(as a challenge, try to think of a hack). Although the test which fails this approach is very specific, but I believe it could have been anticipated by the authors and testers.F: the solution that uses to much memory is clear the moment you start thinking about the problem. Whether it passes the time limit is unclear, but it's easy to realize the problem is written in a way that it seems impossible to solve without finding all primes. After that, googling "Sieve of Eratosthenes low memory" and copy pasting gives you the full solution in minutes.
•  » » 4 years ago, # ^ |   +38 For example, my first submission which makes an ordered triple (length, length, area) for consecutive vertices and then compares this cyclic sequences passes the system tests(as a challenge, try to think of a hack). Omgggggg, siiiiick! That hacks my solution and Benq's as well. Hack test4 4 0 0 1 0 4 4 3 4 0 0 1 0 -2 4 -3 4It seems that this round should have been won by some fake blue guy :P
•  » » » 4 years ago, # ^ |   0 But if you use signed area, that is not a problem right?
•  » » » » 4 years ago, # ^ |   0 I use signed area, but even though all areas I compute are positive because I operate on convex polygon. I would get different areas for angles α and  - α, but it sees no difference between α and 180o - α which is the problem here
•  » » » » » 4 years ago, # ^ |   0 Yeah, that hacks my solution as well.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Edit: I saw the hack and get it, reflected ones are considered the same.
•  » » » 4 years ago, # ^ |   +35 Yes, because the cross product gives you the sin(α), so you cannot differentiate α and 180 - α. Putting the dot instead the cross product solves this issue since all angles are up to 180.
•  » » 4 years ago, # ^ |   0 F can also be solved by the usual sieve, using some casework for numbers divisible by 2 and 3.41372869
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Although the test which fails this approach is very specific, but I believe it could have been anticipated by the authors and testers. I did think about it and I like E as a problem because the right encoding of a polygon matters (or, well, should matter) — how to avoid doubles, how to ensure it's unique, then stuff like no reflections = direction on the convex hull matters... however, this round was prepared quite badly.I like F as a concept too, but if it's really easy to find, it shouldn't have been in the contest. Especially not one with prizes.
 » 4 years ago, # |   0 Why have my solution (http://codeforces.com/contest/1017/submission/41366026) got WA on test 20?
•  » » 4 years ago, # ^ |   0 pref[kols][sum] += chis;here the sum can be greater than 100. so just add an if condition
 » 4 years ago, # |   0 is there a difference between using long long as index and using unsigned int as index in bitset (in terms of performance)?4137225741372242
•  » » 4 years ago, # ^ |   0 Depends on which operations. For example, fetching memory: not really, bitwise operations: yes.
•  » » » 4 years ago, # ^ |   0 Thanks :)
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
 » 4 years ago, # |   +23 [Double comment in case people don't check the editorial]For 1017E - Сверхзвуковая ракета, many of the accepted submissions (around one-third?) actually fail on this test case: 4 4 0 0 1 0 1 1 2 1 0 1 1 1 1 0 2 0 I wrote up a detailed explanation of what's going on in this post: https://codeforces.com/blog/entry/61086Can we add this case to the practice version of the problem?
 » 4 years ago, # |   +13 Hope that we can see contests by Magolor again.
•  » » 4 years ago, # ^ |   0 Agree
 » 4 years ago, # | ← Rev. 2 →   0 For problem D, I use O(q × 2n) "solution" and passed it.my code:http://codeforces.com/contest/1017/submission/41379865
 » 4 years ago, # |   -16 The second "guy" 000000 seem to be a group of contestants. Look at the submission times, you can tell that the problems were solved separately by more than one person.
•  » » 4 years ago, # ^ |   +17 He had two submissions at the same time, right after the server came back after the downtime. There is nothing suspicious there.
•  » » 4 years ago, # ^ |   +5 lol, u guys press downvote like the other guy was right and i was wrong. At least you should check what really happended first
•  » » » 4 years ago, # ^ |   0 Maybe YOU "should check what really happended first", before making false accusations, without any real evidence.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +56 okay, sorry for not showing the evidences.you can see he finished A after 2 mins, then he solved C, which took him 4 min to submit at min 6. Then he solve B at min 7, which meant he had 1 minute to read the whole statement and solve B. You can see that he took 1 minute also to fix C's 3rd test, which was him just chaning '2' to '10'. Also you can see he use 4-spaces tab in A and B but 8-spaces tab in C.okay we had been interupted by server's error. assume he solved both D and F in crashing time, ignore his super fast submit speed because maybe we could do it also (2s between F and D), then look at D and F's code. D using C pattern (he declared iterator i at the beginning), define N = 10005, while F using C++ pattern and using const maxn = 4e8. I don't think those were done by only one person.his progess of solving E and G was also strange. sometime he submited E and then immidiately submited G. we can also see the spaces tab difference here.
•  » » » » 4 years ago, # ^ |   0 Lmao rekted
 » 4 years ago, # |   0 Thanks to the contest makes me know such a great people. But also sadly in this way. Wish Taravilse rest in peace.
 » 4 years ago, # |   -24 Is this contest rated??
 » 4 years ago, # |   0 Why am i getting TLE in D ? 41423817
•  » » 4 years ago, # ^ |   0 You can solve each query in O(1) :)
 » 4 years ago, # |   0 i like cs academy
 » 4 years ago, # |   0 Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).