### dreamoon_love_AA's blog

By dreamoon_love_AA, history, 6 months ago,

Hello, everyone! Codeforces Round #631 will be held at Apr/03/2020 17:35 (Moscow time).

The problems are almost from me(dreamoon_love_AA), except one problem of which the idea is from drazil and developed by me. Also we want to thank 300iq for helping me prepare the round, isaf27, tmt514, rowdark, yp155136, wangyenjen, n_dao107 and zj713300 for testing this round, and MikeMirzayanov for Codeforces and Polygon.

This is my third time organizing a problemset for a Codeforces round (my previous rounds: Codeforces Round #292, Codeforces Round #320).

Good luck and have fun!

UPD: Below is a message for you from MikeMirzayanov:

About two weeks ago, we completed the crowdfunding campaign dedicated to the 10th anniversary of Codeforces. Community help inspires and provides resources for the development and operation of the platform. Thanks! With this round, we want to say thank you to Denis aramis Shitov, for his significant contribution and support. It is valuable, important and very nice when people from the community lend a helping hand and congratulate. Thank you, Denis!

UPD2: Also thanks to Shik for testing the round!

UPD3: Score distribution:

• Div2: 500 1000 1500 1750 2500
• Div1: 500 750 1500 2000 2500

UPD5:

I won't say sorry that the pretests are not strong. Because I don't think the pretests must be strong in every contest.

But I still want to give congratulations to the winners:

div1:

div2:

Among these winners, I want to especially congratulate Um_nik. I am quite excited when I see him solve all problems.

• +656

 » 6 months ago, # |   +13 It's going to be a great round. Really Excited :)
•  » » 6 months ago, # ^ |   +140 But, be careful of test 1
•  » » » 6 months ago, # ^ |   +20 This is not problem Generally, the test 1 is example in question and you will not get penalty even if you make a mistake on test 1.
•  » » » » 6 months ago, # ^ |   +169 Joke has gone above your head.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +54 Yes but please everyone check their code answers on samples otherwise it will make the queue too long and reduces the quality of contest.
•  » » » » » 6 months ago, # ^ |   +11 Indeed you are quite right
•  » » 6 months ago, # ^ |   +12 I see you know what meme is good
•  » » 6 months ago, # ^ |   0 i wish god will save us from queue because there is lot of registration during quarantine.
•  » » » 6 months ago, # ^ |   +4 But not all of them show up in contest.
•  » » 6 months ago, # ^ |   0 ohh really?
•  » » 6 months ago, # ^ |   -63 Bitch,dreamoon is just rubbish and his contest is as rubbish as him.
•  » » » 6 months ago, # ^ |   0 Don't judge the quality of contests if you haven't taken them.
 » 6 months ago, # |   +15 How many problems?
•  » » 6 months ago, # ^ |   +11 Usually, it is a 6 Problem and 2 Hour round.
•  » » 6 months ago, # ^ |   +140 I think there will be 5 problems for both division.
•  » » » 6 months ago, # ^ |   +11 Thus this round must be relatively hard...unsatisfactory results ending up usually
•  » » » » 6 months ago, # ^ |   +42 But when I still studied in university, 5 problems round is more often than 6 problems. So I determine use 5 problems.
•  » » » » » 6 months ago, # ^ |   -31 Wow! It's actually very exciting to see you back! And the problems are definitely gonna be extremely high-quality and hard to solve as well. Don't think it's wise to take part in such a round, cause oftentimes I failed to get my rating higher(sad face Anyway, wish the round a complete success!
•  » » » » » » 6 months ago, # ^ |   -12 Maybe it's just a round without div.1 A So it will be extremely hard.
•  » » » » » » » 6 months ago, # ^ |   0 definitely true LOL
•  » » » » » » » » 2 months ago, # ^ |   0 So why I am downvoted? Just by predicting so accurately?
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   -10 Let's see
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   -30 U are really good manager[user:dreamoon_love_AA] ,Managing love and coding same time.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   -8 .
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -22 You mean for each division?
•  » » » » 6 months ago, # ^ |   0 What was wrong with the question — for both divisions there were 10 problems. :)
 » 6 months ago, # |   +21 wow Setting Problem After such a long time
 » 6 months ago, # |   -39 You have one of the most interesting rating graphs on codeforces!! dreamoon_love_AAPlease explain the trend!!
•  » » 6 months ago, # ^ |   -25 Yes you are right
•  » » » 6 months ago, # ^ |   +18 Yes you are right that I am right
•  » » » » 6 months ago, # ^ |   +6 Yes you are definitely right that i am right that you are right.
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   -116 .
 » 6 months ago, # | ← Rev. 2 →   +32 I hope problem statements will also be short and sweet just like the announcement :)
 » 6 months ago, # |   +181 Didnt invited sorry_dreamoon?
•  » » 6 months ago, # ^ |   -63 RIP English XD.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -8 XD XD Even if that was not a joke, what's XD about it? XD XD
•  » » » » 6 months ago, # ^ |   -39 see from the side
•  » » » » » 6 months ago, # ^ |   +5 RIP English
•  » » » » » » 6 months ago, # ^ |   0 Care to elaborate??
•  » » 6 months ago, # ^ |   -11 Do you know there's a user called dreamoon_is_rubbish?
•  » » » 6 months ago, # ^ |   0 (S)He doesnt exists for me. Idk about others.
•  » » » 6 months ago, # ^ |   0 I think your name is not friendly to him/kk
•  » » » 6 months ago, # ^ |   0 Do you know there's a user called dizzy_izzy?
 » 6 months ago, # | ← Rev. 2 →   -21 I wish the time could be earlier,I am not able to be there.o(╥﹏╥)o
•  » » 6 months ago, # ^ |   -35 RIP English XD.
•  » » » 6 months ago, # ^ |   -29 lol your name -sister of contestfucker xdxd
•  » » » » 6 months ago, # ^ |   0 yeah babyy, thass how i roll
 » 6 months ago, # |   +7 Hope, everybody is going to enjoy the contest. :)
 » 6 months ago, # | ← Rev. 2 →   +57 It will be interesting to see whether tourist can regain his throne in this contest!!!!
•  » » 6 months ago, # ^ |   +21 He can't. The contest is in ~35 hours.
•  » » » 6 months ago, # ^ |   +11 edited!! :p :p
•  » » » 6 months ago, # ^ |   0 I didn't get you. What is the meaning of " The contest is in ~35 hours " ?
•  » » » » 6 months ago, # ^ |   +10 Nvm dude, you don't really want to spend your time on it
•  » » 6 months ago, # ^ |   +30 Mifafaovo is hiding in his hole xD
•  » » » 6 months ago, # ^ |   +5 Hope he didn't catch the virus.
 » 6 months ago, # |   -67 it better be virus themed questions
 » 6 months ago, # |   0 I am excited for the contest , in this quarantine time it is just annoying and boring without cp contests and football matches .
 » 6 months ago, # |   0 can anyone suggest how to practice so that I am able to complete more than 2 problems in a contest?
•  » » 6 months ago, # ^ |   +6 there is no secret to it. just solve more tasks
•  » » » 6 months ago, # ^ |   0 what kind of tasks?
•  » » » 6 months ago, # ^ |   0 I am afraid bro I am not improving
•  » » » » 6 months ago, # ^ |   +1 I practiced with USACO or COCI problems. they give editorals.
•  » » 6 months ago, # ^ |   0 Solve problems which are a little harder than your comfort zone. Like you can easily solve 1000 rating problems, then try to solve 1100-1200 rating problems. And don't spend more than 30 minutes on a problem if you think you are stuck see the tutorial, understand, and solve it.And of course practice a lot. I am following this approach and it's helping me. happy coding.
•  » » » 6 months ago, # ^ |   +3 Actually you can spend more than 30 minutes on a problem. You can spend as much time as you wish until you have some progress on it. Trust my words ;)
 » 6 months ago, # |   +6 Problem setting tab shows you have arranged 3 contests before. Round 272,292 and 320. Then it should be your 4th contest. Why are you not considering round 292?
•  » » 6 months ago, # ^ |   +1 If you click the link of Round 272 provided in this blog, it opens up the page for Round 292.
•  » » » 6 months ago, # ^ |   0 That's another mysterious information.
•  » » » 6 months ago, # ^ |   +26 I fix now...
•  » » 6 months ago, # ^ |   +23 Actually, I don't consider round 272 as const organized by me. It's the problemset of round 272 is not chosen by me. I just only provided the hardest problem to my friend.
 » 6 months ago, # |   +4 Wow! This announcement is great! I think this round is going to be a great round.
 » 6 months ago, # |   +86 dreamoon_love_AA here I come!!!
•  » » 6 months ago, # ^ |   0 WHO ARE YOU? How dare you impersonate dreamoon?!/jk
•  » » » 6 months ago, # ^ |   -24 Actually they're the same person
•  » » » » 6 months ago, # ^ |   +27 Actually we are not the same person
•  » » » » » 6 months ago, # ^ |   -11 here I come too!
•  » » » 6 months ago, # ^ |   -21 fuck you
•  » » 6 months ago, # ^ |   +79 Here we go again, one more I and l scenario.
•  » » 6 months ago, # ^ |   +70 So here is the difference -.-
•  » » 6 months ago, # ^ |   +21 I'm too surprised to see dreamoon_Iove_AA here!!!
•  » » 6 months ago, # ^ |   0 It took me 10 minutes to figure out the difference in the usernames.
 » 6 months ago, # | ← Rev. 2 →   +114
 » 6 months ago, # |   +2 Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
 » 6 months ago, # |   +12 this is good ...."Knowing Is Not Enough; We Must Apply. Wishing Is Not Enough; We Must Do.".......B)[user:hajer qandeel]
 » 6 months ago, # |   +34 tourist vs MiFaFaOvO. Who will win ?
•  » » 6 months ago, # ^ |   +32
•  » » 6 months ago, # ^ |   -21
•  » » 6 months ago, # ^ |   -25 I think MiFaFaOVO will win
•  » » 6 months ago, # ^ |   -21 World First MiFaFaOVO!// dlstxdy
•  » » 6 months ago, # ^ |   0 what I think it would be exciting to watch as codejam would start in a day , tourist will try to get his throne back . lets see.who wins?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +7 I guess you will have to wait a little longer. Mifafaovo won't come out of his hole xD
 » 6 months ago, # |   0 Excited! Looking forward to your problems.
 » 6 months ago, # | ← Rev. 2 →   -39 .
•  » » 6 months ago, # ^ |   0 ...
 » 6 months ago, # |   +40 Who is Denis Aramis Shitov????
•  » » 6 months ago, # ^ |   +98 He is a friend of Codeforces. Please, re-read the blog post.
 » 6 months ago, # | ← Rev. 4 →   -52 I am not begging for followers(friends) on codeforces.Edit: I did not even edit my original comment uh.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +5 Why are you begging for followers(friends) on codeforces?Edit: Why would you even edit your original comment uh?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -31 comment and its reply swapped XD
 » 6 months ago, # |   +3 Feeling excited. Codeforces making this lockdown time easy to pass by holding the contests for programmers.
 » 6 months ago, # |   +31 Let us see if this round can get 25000 registrations
 » 6 months ago, # |   +10 All the best to everyone who will participate in this round. I hope to become a specialist after this contest.
 » 6 months ago, # | ← Rev. 2 →   +15 Thank You Denis Aramis Shitov
 » 6 months ago, # |   +9 tourist vs. MiFaFaOvO It will be exiting!
•  » » 6 months ago, # ^ |   0 after contest -> MiFaFaOvO
 » 6 months ago, # |   +39 Thank you mr. Denis Aramis Shitov
 » 6 months ago, # |   -8
 » 6 months ago, # |   +16 I hope I can do well in this round
•  » » 6 months ago, # ^ |   -13 %%%
•  » » 6 months ago, # ^ | ← Rev. 4 →   -8 I hope we can all achieve good results！
•  » » 6 months ago, # ^ |   -15 %%%
•  » » 6 months ago, # ^ |   -14 %%%
•  » » 6 months ago, # ^ |   -18 %%%
 » 6 months ago, # |   -37 is it rated?
•  » » 6 months ago, # ^ |   +20 yes it is rated
•  » » 6 months ago, # ^ |   +22 Of course,It will be rated.
 » 6 months ago, # |   -6 Time is not good for me!
 » 6 months ago, # |   +13 Thanks !!! We need competitions like this more and more .I wish everybody good luck.
 » 6 months ago, # |   0 Wow！It seems good！
•  » » 6 months ago, # ^ |   0 I hope I'll get good grades in it.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Everybody hopes so.
 » 6 months ago, # |   0 Will it be a Mathforces Round?
•  » » 6 months ago, # ^ |   +2 I think it won't.
 » 6 months ago, # |   -11 I hope its going to be an interesting round
 » 6 months ago, # |   +21 Looking forward to seeing concise and crap free problem statements.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 ¯\_(ツ)_/¯
 » 6 months ago, # |   +29 Thank you Mr.Denis Aramis Shitov.
 » 6 months ago, # |   -10 umm..what we know so far is that there will be at least 2 problems
 » 6 months ago, # | ← Rev. 2 →   -28 .
•  » » 6 months ago, # ^ |   +26 Read Announcement carefully before asking...
•  » » » 6 months ago, # ^ |   0 Trying to play MikeMirzayanov.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -28 oh really? Priyank
 » 6 months ago, # |   +27 thank you Denis aramis Shitov and to all other contributors.
 » 6 months ago, # |   +21 Thanks, Danis and other contributors. Because of you, we have problems to solve for free.
 » 6 months ago, # |   +10 Friendly reminder: watch out for FST.
 » 6 months ago, # |   +17 What's the score for each problem?
 » 6 months ago, # |   +33 dreamoon_love_AA and I_love_codeforces ♥♥♥
•  » » 6 months ago, # ^ |   -20 fuck it
 » 6 months ago, # |   +15 May God bless us from queue.... All the best guys!!!!!!!!!
 » 6 months ago, # |   +3 Hope I will turn blue after this contest.
 » 6 months ago, # |   +5 Hope this contest does not have long queues like the last rated contest
 » 6 months ago, # |   +19 When the problem scroring will be posted?
 » 6 months ago, # |   +14 I think , this contest will be very intersting
•  » » 6 months ago, # ^ |   +1 gl hf
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 thanks)) and to you
 » 6 months ago, # |   0 good luck for every one)
 » 6 months ago, # |   +12 Why hasn't the score distribution been published yet?
 » 6 months ago, # |   +3 hoping to do well in it and get some +ve rating . let's see how it goes .
 » 6 months ago, # |   0 Please post the score distribution of the problems.
 » 6 months ago, # |   -11 I think will be 500-1000-1250-1500-2000
•  » » 6 months ago, # ^ |   +4 500-1000-1500-1750-2500
 » 6 months ago, # |   0 Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
 » 6 months ago, # |   +6 Is it rated ?
•  » » 6 months ago, # ^ |   -31 Unfortunately, it's not rated(
•  » » » 6 months ago, # ^ |   0 Really?
•  » » » 6 months ago, # ^ |   0 QAQ
•  » » » » 6 months ago, # ^ |   0 QAQ? Is it really not rated?
•  » » » » » 6 months ago, # ^ |   0 Sarcasm
•  » » » » » » 6 months ago, # ^ |   0 Malicious disinformation.
 » 6 months ago, # |   0 Enjoy the contest
 » 6 months ago, # |   +16 site seems fast today
 » 6 months ago, # |   0 lets do well guys ..best of luck..
 » 6 months ago, # |   +129 noExplanantionsForSamplesForces
•  » » 6 months ago, # ^ |   +3 orz
 » 6 months ago, # |   -7 Did anyone else too missed the contest because they binge watched Money Heist ? :/ Guess I'm gonna give a virtual one now !
•  » » 6 months ago, # ^ |   +12 Lucky you...
 » 6 months ago, # | ← Rev. 2 →   +56 Is this the second april fools round?
 » 6 months ago, # |   +86
•  » » 6 months ago, # ^ |   +93 The authors likely spent some time writing the statement. Why do you think they can come up with a better explanation now in a shorter time? Besides that, it is much harder to understand your question than to understand the statement. $x$ is a number that is given to you in the input, what more do you want?
•  » » » 6 months ago, # ^ |   -87 If they didn't say anything it would be better than this answer
•  » » » » 6 months ago, # ^ |   +82 No, I think it's an excellent answer. It lets you know the answer is written in the statement, the statement is clear (in the author's opinion) and you do not need any more information. As opposed to "oops, we left this part out" and "yes indeed, it's unclear, we will edit". Not answering creates a lot of uncertainity. "No comment" is also a reasonable answer, but I think CF wants to be friendlier than that in easy problems.
•  » » » » » 6 months ago, # ^ |   -19 Not gonna lie you're right it's just a joke I don't why I can't understand it even though alot of people solved it
•  » » 6 months ago, # ^ |   +35 Lolwut, do you really think this is a reasonable question? This is definitely the appropriate answer given that thousands of people didn't have a problem with it.
 » 6 months ago, # |   +5 Is this round bit hard!!!OR only i feel so?
•  » » 6 months ago, # ^ |   -20 Pretty tought one :(
 » 6 months ago, # |   -24 The comment removed because of Codeforces rules violation
 » 6 months ago, # |   -19 The comment removed because of Codeforces rules violation
 » 6 months ago, # |   +126 Great contest, I hate it.
•  » » 6 months ago, # ^ |   -6 I hate this contest! one of my worst performances so far could not even solve B!
•  » » » 6 months ago, # ^ |   +22 Yeah, I also only solved 2. But the questions were really nice. I am waiting to see where I went stupid in my C and editorial for D.
•  » » » » 6 months ago, # ^ |   0 how to find efficiently(better than O(k)) that all the number between 1 to k exist or not in a array of size k??
•  » » » » » 6 months ago, # ^ |   0 keep a count of the unique elements, as well as the maximum seen so far. Check if those are equal.
•  » » » » » 6 months ago, # ^ |   0 I used a set, if set.size() == max(set) then its a valid permutationand keep in mind to not add already added element
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   -11 C made my heart go up and down.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3
•  » » » » » 5 months ago, # ^ |   0 C for Cheater!
•  » » » » 6 months ago, # ^ |   0 I thought problem B was harder than problem C but in fact more people solved problem B. The fact that I know number of solutions of B must be of the count 0, 1 and 2 actually makes the problem harder.
 » 6 months ago, # |   -11 The worst contest i had seen!
 » 6 months ago, # |   +44 How to solve Div.1 C?
•  » » 6 months ago, # ^ |   -11 Difficulty Ladder exploded?
•  » » 6 months ago, # ^ | ← Rev. 4 →   -31 Sorry, I read it as Div2 C. My bad.
•  » » 6 months ago, # ^ |   +10 I think greedily taking from the top layer that won't break your heap works (break your heap meaning having a 0 too high up).
•  » » 6 months ago, # ^ |   +1 Shitty greedy algorithm. Sort elements in decreasing order and erase if you can
•  » » » 6 months ago, # ^ |   +9 yes the algorithm is shitty because your solution failed at test case 66 hahahahahha
•  » » » » 6 months ago, # ^ |   +8 You can check my submission, if you don't believe lessmeaning
•  » » » 6 months ago, # ^ |   0 Agreed
 » 6 months ago, # |   +314 :)
 » 6 months ago, # |   +8 i devoted more than 1 and half hout to problem B and ended up getting wrong answer . It just screwed up . But still enjoyed it.
 » 6 months ago, # | ← Rev. 2 →   +70 I can't blame authors for my mistake but I think it wasn't obvious from the statement of problem div2C that queries must be performed in given order
•  » » 6 months ago, # ^ | ← Rev. 2 →   +14 What? I sorted the queries by length and wasted 1.5 hours and about 10 wrong submissions. I debugged on almost 50 test cases.
•  » » 6 months ago, # ^ |   +11 I spent about an hour trying to solve and I still didn't know this was the case until I read your comment
•  » » 6 months ago, # ^ |   +11 Glad to see I wasn't the only one. Took a long time to figure out, though I place all blame on me and none on the author. I have a bad habit of rushing the reading of the longer questions.
•  » » 6 months ago, # ^ |   +6 I think many have done this, and I feel coloring according to our own order is slightly more difficult question, I think I correctly solved that version, but the real question is very much easier and straightforward!
 » 6 months ago, # |   +24 Anyone has an idea for pretest 6 of div2C?
•  » » 6 months ago, # ^ |   +29 It contains large values for each $l_i$. Using ints and adding them up will cause overflow, leading to WA.
•  » » » 6 months ago, # ^ |   +10 omg why :'( you're right
 » 6 months ago, # |   0 It's not as crowded as recent contests but main page still can't load properly :(
 » 6 months ago, # |   0 i don't get it, seems like most struggled in this round , why would there be such a huge difference in div 2 rounds ?
 » 6 months ago, # |   +3 was it a normal DIV2 contest?
 » 6 months ago, # |   0 The moment when you get runtime error in Div. 1 C in the last 5 mins....
 » 6 months ago, # |   +3 How to solve Div1B?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 SpoilerEach element has to have a higher bit on than the previous one, so try to build some DP with that
•  » » 6 months ago, # ^ |   +4 The main observation is that the numbers in your array must have strictly increasing MSBs (you can prove this by induction). From there, you can iteratively calculate the number of arrays with MSB at most $2^i$ for each $i$, and it's a slight modification once you have to do the MSB of $d$.
•  » » 6 months ago, # ^ |   +7 Sequence is ok iff msb($a_i$)
•  » » 6 months ago, # ^ | ← Rev. 2 →   +42 An array that satisfies the given constraints mandates that the MSB of an element is greater than it's previous. No two elements can have the same MSB. Let $A[i]$ be the number of elements that MSB at $i$th position that are less than $d$.The answer is : $( (1+A[0])*(1+A[1]). . .*(1+A[32])) - 1$.We choose one number from each MSB bucket. We subtract the case where we choose 0 elements. We also take modulo $m$ at each multiplication step.
•  » » » 6 months ago, # ^ |   +3 nice
 » 6 months ago, # |   +109 Problem B(Div1) D(Div2):You can't find this in OEISMe: 1 Hour trying to find it in OEIS
•  » » 6 months ago, # ^ |   -18
•  » » » 6 months ago, # ^ |   +5 This one is not the correct one.
•  » » » » 6 months ago, # ^ |   -13 orz ntf
 » 6 months ago, # |   +15 VeryLongCodeWithoutBugForces
 » 6 months ago, # |   +1 Anyone got an idea for Div2D ? Thanks :)
•  » » 6 months ago, # ^ |   +7 Main idea: We can find an array b for a given array a iff, for all i, a[i] has a larger leading bit than a[i-1].
 » 6 months ago, # |   +18 Super balanced contest. Apart from that, ABD seem pretty nice, C could be but getting to right implementation can be tough and the constraint $2^20$ seems too tight.
•  » » 6 months ago, # ^ |   +10 After being unable to correctly implement my idea for a while, I realized it seems equivalent to a greedy which subsequently passed.Apply f on the topmost node such that after applying f there is no 0 in depth <= g. Very easy $O(nlogn)$ implementation for $n=2^h$.Hopefully correct.
•  » » » 6 months ago, # ^ |   -8 Probably correct. I simulated that in a much more complicated way (and forgot that $G$ isn't $H-1$ because the sample doesn't contain that), but your example supports my point that a lot of this problem's difficulty is getting bogged down in ugly implementation.
•  » » » » 6 months ago, # ^ |   0 Yeah, my code got extremely messy exactly due to $G$ not being $H-1$ as well. I didn't enjoy the problem either, but I guess it's still nice that a short correct code exists.
•  » » » » » 6 months ago, # ^ |   0 Solution 75417750 Contest submission 75411025
•  » » » 6 months ago, # ^ |   +2 Proof: Consider the first time we make an operation not on the root, but on the path that making an operation on the root would modify. But making an operation on the root would be strictly better, as then all vertices would contain a smaller number. Also, applying that operation immediately after the last operation on the root instead of where it was originally done doesn't change anything.Thus, we can first greedily apply operations to the root, then independently solve all branches of the path operating on the root would modify.
•  » » 6 months ago, # ^ | ← Rev. 4 →   -8 Actually my solution was super simple to code. I guess there are many ways to think about this problem, because mine solution is significantly different than one described by EnchomIts code is here: https://ideone.com/1XiSlu
•  » » 6 months ago, # ^ |   +55 Personally I don't think that it's ok when D1B level problem becomes D1D level because you have to restore the answer.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 Well, restoration of the answer in my solution is for (int i = n; i >= 1; i--) { if (!taken[i]) { cout<
 » 6 months ago, # |   +8 Div1 D solution? Seems really hard. Seen a ton of similar problems but none of the usual techniques worked. Probably missing an observation of why some greedy part is correct.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +10 Number of operations we have to make is$1 + \max(\lceil\frac{\text{# of adjacent pairs of same character}}{2}\rceil, \max_{c \in \Sigma} (\text{# of adjacent pairs of character c}))$As each operation decreases both quantities by at most one.Greedy that works is always choosing the color with most adjacent pairs, then selecting some interval starting or ending with an adjacent pair of that color, and not both starting and ending with an adjacent pair of that color.Implementing this greedy in $O(n^2)$ is easy, but I couldn't implement it fast enough to not TLE :(
•  » » 6 months ago, # ^ |   +25 find all occurrences 'aa' for all characters. Lets say if these type of occurrences is maximum for character a currently, then delete substrings of type aa....bb or bb....aa till it is possible to do so. This process ends when there are occurrences 'aa' for only one type of a character. Though the implementation was a bit too frustrating for me.
•  » » 6 months ago, # ^ |   +18 You can reduce it to the following problem: You are given a string and in every step you can remove two consecutive letters if they are different or an arbitrary single letter and you want to make it empty in the smallest possible number of steps.Answer to that problem is max((length+1)/2, max frequency of a single letter)Reduction from original problem is that for every pair of consecutive equal letter, you put that letter into that string in reduced problem. It can be easily seen that operations of removing beautiful string in original problem is allowed operation in that reduced problem, so they are equivalent.
•  » » » 6 months ago, # ^ |   0 Thanks. I made the reduction but for some reason the answer wasn't obvious to me. Quite disappointed that this is the solution to be honest.
•  » » » 6 months ago, # ^ |   0 And how to solve the problem after reduction? I found $\mathcal{O}(n^2)$ solution, but it shouldn't fit in TL if $n \approx 10^5$.
•  » » » » 6 months ago, # ^ |   +10 Oh well, that is a bit tedious task. In each step you determine the letter with biggest frequency (in O(26) cause I keep them explicitly) and we want to remove one of its occurences with some other one. Then you iterate over all other letters (another additive O(26), but beware, it's amortized!, because of reasons that will be clear later) and check whether there is any place where these two letter currently touch. In order to perform a single check you keep two-dimensional array (with size 26x26) of vectors of pairs that tell you where are currently neighbouring occurences of these pairs of letters. When you decide to remove some pair you need to remove 3 pairs and add 1. However removing is a bit inconvenient, so I do that lazily. That is, I do nothing in that moment of removing that pair and whenever I see some candidate for a neighbouring pair in one of these 26x26 vectors, I check whether this pair is still valid (that is, both letter are still alive) — if it is then I use it, if it isn't then I remove it. In order to know what new pairs of neighbouring letters are created I use my own bidirectional list. In order to restore indices in current string (based on global ones that I use everywhere) I use another bidirectional list for alive original positions and Fenwick tree.I hope my code can be of some help: https://codeforces.com/contest/1329/submission/75411250
•  » » » » » 6 months ago, # ^ |   0 Oh, I got it, thanks!
•  » » » » » » 6 months ago, # ^ |   -18 Welcome
 » 6 months ago, # | ← Rev. 2 →   +1 How to solve Div 2 D ? I tried to do kind of cheating using Berlekamp-Massey algorithm to extrapolate the sequence manually but didn't work out. Also if anyone got AC using BM algorithm please post your solution link.
 » 6 months ago, # |   +2 How to solve div2 B? My submission gives TL on pretest 2.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 maybe you used memset in each test case
•  » » » 6 months ago, # ^ |   +1 yeah, is it wrong?
•  » » » » 6 months ago, # ^ |   +8 you have 10^4 test in each test case and you used memset on a array size 2e5 so it become n^2
•  » » » » » 6 months ago, # ^ |   -6 Using memset for size n won't give tle as sum of n over all testcase always less than 200000. And all a_i is also less than n.
•  » » » » » 6 months ago, # ^ |   0 for clearing the arrays in independent testcases its better to use fill function . this will take the time of size n given in the input . It doesn't lead to tle since sum of n over all testcases is <=2e5.
•  » » » » 6 months ago, # ^ |   0 I also used memset in each test case... 4 times (whoops? :)) )... and I passed all the pretests, so that shouldn't be the problem.
•  » » » » » 6 months ago, # ^ |   0 you just pass the pretests :))) but if you pass the protests that means memset is not the problem
•  » » » » » 6 months ago, # ^ |   0 If you use memset for size n then will never give tle but if you use memset for size 20000 in each case then you will surely get tle.
•  » » » » » » 6 months ago, # ^ |   0 I used size 200000 each time. So... I guess a sweet TLE is awaiting me? :)): ...
•  » » » » » » » 6 months ago, # ^ |   0 I hope as 10^9 iteration is very large to complete in 2 seconds.
•  » » » » » » » » 6 months ago, # ^ |   0 Nope, AC ¯\_(ツ)_/¯
•  » » 6 months ago, # ^ | ← Rev. 8 →   +1 You can use a multiset and a set Create a multiset and a set that will be used as the prefix Create another multiset and a set that will be used as the suffix Iterate through the input array add the current value to the multiset prefix and the set prefix too And remove the value from the multiset suffix and from the set suffix if the multiset doesn't contain the current value again Now to check if a state is valid the multiset prefix size should be the same with the set prefix size and the largest element in the multiset prefix should be equal to the size of the multiset prefix check same for the suffix(multiset and set) If valid add i and n — i — 1 to the result Code#include using namespace std; void solve() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } multiset m; // suffix multiset set t; // suffix set for (int i = 0; i < n; i++) { m.insert(a[i]), t.insert(a[i]); } vector> res; multiset s; // prefix multiset set d; // prefix set for (int i = 0; i < n; i++) { s.insert(a[i]), d.insert(a[i]); m.erase(m.lower_bound(a[i])); if (m.find(a[i]) == m.end()) t.erase(a[i]); // erase from set if no longer in multiset if (*s.rbegin() == s.size() && s.size() == d.size()) { // we've found match if (*m.rbegin() == m.size() && t.size() == m.size()) { res.push_back({i + 1, n - i - 1}); } } } cout << res.size() << '\n'; for (auto p : res) { cout << p.first << ' ' << p.second << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; while (q--) { solve(); } return 0; } 
•  » » » 6 months ago, # ^ |   +1 Thanks a lot, I had a same algorithm but with memset, so I got TL(
•  » » » 6 months ago, # ^ |   0 you could use a vector and sort it then go throw it and check if each element is equal to its index+1
•  » » 6 months ago, # ^ | ← Rev. 4 →   +2 Traverse the array until you get 1st repeated element. When you get that break the array into two array at the point where you get 1st repeated value. Then simply check if two array is permutation or not.Repeat the process starting from back.
 » 6 months ago, # |   -13 In problem B, it was clearly written that two permutations are of non zero length, but this surely wasnt the case.
•  » » 6 months ago, # ^ |   +3 No, both permutaion length was >0
•  » » 6 months ago, # ^ |   0 are you sure about it?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 But they are of non zero length. a problem with the statement was the constraints saying both l1 and l2 <= n , not only their sums.still , they are of non zero length , maybe you adding that to your code only fixed another bug.
•  » » » 6 months ago, # ^ |   0 Possibly, but adding an empty permutation somehow passed that testcase.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 then unfortunately you probably will fail the main tests. this test is clearly wrong for you:121 2it should output: 0while yours probably from what your saying will output: 12 0
•  » » » » » 6 months ago, # ^ |   0 1 2 1 2 answer for this should be 1 2 2 why it is wrong?
•  » » » » » » 6 months ago, # ^ |   0 my bad , i am not sure why the comments here don't end lines like intended , fixed now.
•  » » 6 months ago, # ^ |   0 And Poor me, couldn't figure out if l1=l2 they are considered as same permutation in an hour
 » 6 months ago, # |   +38 I read div1A statement and for some reason, I thought "well, it's optimal to sort the values in decreasing order", but i never read that I wasn't allowed to change the order in which I use the array values. I realized about this when there were 10 minutes remaining of the contest. So sad to lose rating for that silly mistake. Goodbye div1, it was nice to meet you :(
•  » » 6 months ago, # ^ |   +18 If you're truly worthy you'll get it back soon :)
•  » » 6 months ago, # ^ |   0 I did the same, and then after 30 minutes I realized that the queries should be done in order :/
•  » » 6 months ago, # ^ |   0 Same here
 » 6 months ago, # |   0 How to do problem B div2?
•  » » 6 months ago, # ^ |   0 First try checking valid sequence like all elements are 1 to n-1 , atleast there is one element with count 2. After that you can check till particular index if max=index and min=1 and sum=sum of permutation till index than insert in ans Same way for reverse array Take common elements
•  » » » 6 months ago, # ^ |   0 Thanks!
•  » » » 6 months ago, # ^ |   0 Hey can you tell me why this fails ? link Thank you!
•  » » » » 6 months ago, # ^ |   0 Because you are checking validity of permutation using sum of first x numbers. According to your code, both the below testcase will be considered valid permutation because their sum is equal to the sum of the first 5 elements. Sum({1 2 3 4 5}) = 15 [Valid] Sum({1 3 3 4 4}) = 15 [Not Valid]
•  » » » » » 6 months ago, # ^ |   0 I submit 3 wrong submissions while contest due to this, but finally Igot the point where I am stucking
 » 6 months ago, # |   0 Never noticed that the input is not a permutation in problem C, so sad......
 » 6 months ago, # |   0 What are the solutions for Div2C and Div2D?
 » 6 months ago, # |   +7 How to solve Div2 C ?
•  » » 6 months ago, # ^ |   +1 You are given m segments of different colors and you can slide these segments in a row of size n. The maximum length we can get by spreading these segments is equal to the lengths of all the segments(i.e without any overlapping), let denote it by sum. So if sum is less than n, it is not possible to cover the whole row. Now if sum >= n we have to compress it to fit in the row size of n. We have to overlap some units of the cells(possibly zero) such that all the colors are visible. The number of units cells to be overlapped is simply sum-n. So start placing the segments from start of the row and after leaving sufficient units of cell place next segment(trying to overlap as much as possible but less than required length), and keep doing this for all the segments maintaining the required number of cells to be overlapped. And if at any iteration the end of segment goes out of the window of size n, in that case answer is not possible. My solution with above approach
•  » » » 6 months ago, # ^ |   0 thanks brother it really helped...
 » 6 months ago, # |   0 Does it take some time for problems to appear in the Problem Set after a contest is over? I think I finally found out what I was doing wrong in my Div2B code after an hour smh.
 » 6 months ago, # |   +4 1A(2C):hacker's paradise
 » 6 months ago, # | ← Rev. 2 →   +42 Tried hacking O(M^2) solution on A (http://codeforces.com/contest/1329/submission/75404901) with ~2.5B operations. Passed in 1.45s (facepalm).
•  » » 6 months ago, # ^ |   -8 It looks like the optimizer changes while(ans[i] + a[i] - 1 < lst) ans[i]++; to ans[i] = lst - a[i] + 1 ?
•  » » » 6 months ago, # ^ |   +8 No, since if it did, the code would run much faster than 1.45 seconds. It's just that the operations are very simple and the processor manages to execute them in time.
 » 6 months ago, # | ← Rev. 3 →   0 In problem c (div2) i tried following approach : first sort in descending order and then choose 'p' value such that first position of the current coloured segment does not coincides with first position of last coloured segment.my submission : link .can someone tell the mistake in approach ?
•  » » 6 months ago, # ^ |   +12 You can't change the order
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I sorted back according to the indices so that order remains .
•  » » » » 6 months ago, # ^ |   0 Colors are painted in the order of input, so you can't firstly paint one with largest $l_i$, then second largest etc.
•  » » » » » 6 months ago, # ^ |   +1 Thanks , you are right . Because changing the order will cause some colour disappear when we reorder them to print . I removed sort lines from my code and it got accepted . submission
•  » » 6 months ago, # ^ |   0 the order of coloring will remain as given.
 » 6 months ago, # | ← Rev. 2 →   0 How to solve Div1B/Div2D?
•  » » 6 months ago, # ^ |   +38 Use the observation that the required sequence is essentially a sequence of numbers such that the most significant bit is in increasing order. So, the max length of this sequence is at most 30.
•  » » » 6 months ago, # ^ |   -35 Oh god, I got that observation before, but I just stopped thinking and doubting the problem statement which says it can't be found in OEIS, lol. I started spend too much time seeing similar pattern in OEIS and looking for how to code it. I should've just trusted the problem statement, what a nice lesson learned.
•  » » » » 6 months ago, # ^ |   +63 Or you know, don't use OEIS to solve problems.
 » 6 months ago, # |   +40 Wow, that's a pretty bad contest if I've ever seen one. Speedforces for a lot of blues, who will now undeservingly be candidate masters.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -7 Get your head out of your *ss mate
•  » » 6 months ago, # ^ |   0 Well, I believe it gets balanced by upcoming contests.
 » 6 months ago, # |   0 Can anyone tell what could be the pretest 2 for DIV2 B...
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Try your code for this input: input1101 2 3 4 5 4 3 2 1 6
•  » » » 6 months ago, # ^ |   0 I am getting 14 6
•  » » » » 6 months ago, # ^ |   0 It failed on mine :( I got:22 84 6which is definitely wrong because I forgot checking if all numbers from 1-m exist. Took me an hour to notice it RIP
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 both l1 and l2 permutation of same number
•  » » 6 months ago, # ^ |   0 1 1 1 Answer is 1 1 1
•  » » » 6 months ago, # ^ |   0 it was written in the problem statement that a[i]
•  » » 6 months ago, # ^ |   0 Try this input to your code Input181 1 1 7 7 1 1 1
 » 6 months ago, # |   0 WOW div2D/div1B is quite tricky. You can find the sequence on OEIS this sequence but only those few numbers in front of the sequence is right for this problem. So tricky/QAQ
 » 6 months ago, # |   0 I spent an entire hour on C not realizing that all lengths must be FULLY painted (when at length 3, you cannot start painting at the next to last position for example). Even though it was very clearly mentioned in the statement. I'm mad at myself.
 » 6 months ago,