By Anadi, history, 5 months ago,

Hello Codeforces!

We have a pleasure to invite you to Codeforces Round #647 (Div. 1) and Codeforces Round #647 (Div. 2). This round will take place on Jun/04/2020 17:35 (Moscow time). In both divisions, you will have 2.5 hours to solve 6 problems. Three of them will be shared.

The problems for this round were prepared by MicGor, Grzmot, Okrut and me.

We would like to thank everyone who made this round possible:

We hope you will enjoy the problem set! Good luck!

UPD: Score distribution:

• Div 1: $500$ $-$ $1250$ $-$ $2000$ $-$ $2500$ $-$ $3000$ $-$ $3500$
• Div 2: $500$ $-$ $1000$ $-$ $1500$ $-$ $2000$ $-$ $2750$ $-$ $3500$

UPD: Editorial

UPD: Congratulations to the winners!

Div. 1:

Div. 2

Below is a message for you from MikeMirzayanov:

With this round, we want to say thank you to Algo Muse for the significant contribution and support!

Algo Muse is an educational site that conducts online algorithmic contests in pen-and-paper style (no coding). It was originally started to help students prepare for theory qualifiers for graduate admissions. At present, the problems have a broader appeal, though occasionally an odd problem may require knowledge of linear algebra, probability, or group theory. The website is maintained by former students of IIT Bombay. To find out more, visit their website or their twitter account.

• +930

 » 5 months ago, # |   -59 orz orz
 » 5 months ago, # | ← Rev. 2 →   -22 Thank you students from Wroclaw
 » 5 months ago, # |   +317 Where is the round "Sorry, Ivan Belonogov!"?
•  » » 5 months ago, # ^ |   +104 That might be the first ever div1 only contest.
•  » » 5 months ago, # ^ |   +215 Where is round "Sorry, Monogon!"? tbh
•  » » » 5 months ago, # ^ |   +26 Btw ... why are you looking like forced for the profile picture arthurconmy ??...No offense mate ...Just curious !! XD
•  » » » » 5 months ago, # ^ |   +55 1) I like to have the same shirt colour as my handle (hopefully one day you'll see me in a red shirt). Some other users do this, e.g AnandOza (but I think I did it first :p)2) I only really take photos of myself for strava, so I'd just been on a run Spoiler(strava is cool, and I'm not the only CF user there, I_love_Tanya_Romanova is some crazy endurance athlete)
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   +106 I think I first did it on July 12th, 2019 (when I reached purple for the second time).Btw, mine are all the same photo, just edited. (The original shirt is blue & matched my Expert rating when I started out, by coincidence, so after I changed color I had the idea to keep the matching theme.)Thanks for the shoutout! :)
•  » » » » » » 5 months ago, # ^ |   +65 Some people messaged me to ask how I did this. I'm by no means an editing master, but here are the steps I figured out.I used GIMP (free Photoshop equivalent). I used the selection tools to carefully select my shirt without selecting the rest of the picture (this was kind of tedious).Then I simply used the Hue-Saturation tool (https://docs.gimp.org/2.10/en/gimp-tool-hue-saturation.html has an explanation). Instead of adjusting all the colors, I just adjusted the blue (to purple or orange or whatever) by changing the hue and saturation until it looked how I wanted. (The original shirt was blue, so this way it only adjusts the shirt and not any traces of my arm that I accidentally selected.)
 » 5 months ago, # |   +1 hope so,this will be a great round
 » 5 months ago, # |   -10 Hoping for gradual increase in question level from A to D. Rather than a very high increase from A to B and from B to C. Thank You for contest.
•  » » 5 months ago, # ^ |   -138 ![ ]()
•  » » » 5 months ago, # ^ |   +240 laraibkhan is a simple man, he sees the word hope, he posts this shitty meme!
•  » » » » 5 months ago, # ^ |   0 yeah,he loves this meme, enough to post it multiple times.
•  » » » » 5 months ago, # ^ |   -60 ![ ]()
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +20 Kids and cute memes can do no good. You are not safe here.. But remember hope is a good thing.
•  » » » » 5 months ago, # ^ |   +5 You, sir, do justice to the username.
•  » » 5 months ago, # ^ |   -11 totally agree. That's why educational rounds are hell.
 » 5 months ago, # | ← Rev. 2 →   +18 Wow! Polish round! So proud :)Thanks for the round :) :)
•  » » 5 months ago, # ^ |   +152 Ah shit. Here we go again!
•  » » » 5 months ago, # ^ |   +36 Nah that level of spam won't happen here xD
•  » » 5 months ago, # ^ |   0 Pred, I just finished Dororo. Dang it was a good one.
•  » » » 5 months ago, # ^ |   0 Yes, it is awesome :)
 » 5 months ago, # |   +6 In parallel div1 and div2 rounds,Are participants rated above 1900 considered div1 or above 2100? Will this change after the new rating system is applied?
•  » » 5 months ago, # ^ |   +25 The participants rated 1900 and above are considered as div 1 in such rounds.
 » 5 months ago, # |   -12 Hope we enjoy the round...
 » 5 months ago, # |   -6 This will be good round :D
 » 5 months ago, # |   -22 Hoping for a great contest!!(Especially for me xd)
 » 5 months ago, # |   0 Hoping for short and concise problem statements!
 » 5 months ago, # |   +44 My general experience of 2.5hrs round. Statements are long. Large gap in questions levels difficulty.
•  » » 5 months ago, # ^ |   +25 I think the first 4 problems will be on the easier side as Div 2 D will be same as Div 1 A this time. Hopefully no sudden surge in difficulty
•  » » 5 months ago, # ^ |   +112 As a tester of this round, I can say that the problems are diverse and very interesting to solve. I found the problem statements concise enough and really liked the round, so I recommend others to have fun participating in this contest.
 » 5 months ago, # |   -8 I hope statements will be short as the last round!
 » 5 months ago, # | ← Rev. 2 →   +11 Following the trend, any review from the testers?
•  » » 5 months ago, # ^ |   +4 Consider a case if any of the tester wrote problem's are not good will you participate?
•  » » » 5 months ago, # ^ |   +20 An acknowledgement from the testers boosts the confidence of the participants, nothing else ;)
•  » » » » 5 months ago, # ^ |   -27 Yeah but trolling them by writing it had became a trend will stop them to do so. Don't you think??P.S. No offence:)
•  » » » » » 5 months ago, # ^ |   +36 I think it is bad habit. Testers should not public comment before the contest. It adds no value.
 » 5 months ago, # |   -18 I think that contest will be very exciting if you can hack so when testers give as such opportunity
•  » » 5 months ago, # ^ |   +9 Hope the setters provide short statements.
 » 5 months ago, # |   0 Ok so this round if from Poland !So why is Errichto missing ????
•  » » 5 months ago, # ^ |   +1047 I'm surprised too. I thought I'm the only Codeforces user from Poland.
•  » » » 5 months ago, # ^ |   -79 your blogs and videos are very helpful for this community...as there are many boring programming streams which are quite useful...we can learn a lot from that...
•  » » » 5 months ago, # ^ |   +4 Errichto was it too sarcastic or only I can see it.
•  » » » » 5 months ago, # ^ |   +124 only you can see it that's why 435 people upvoted it..
•  » » » » » 5 months ago, # ^ |   +2 Now, you also being sarcastic. Lol!
•  » » » » » » 5 months ago, # ^ |   +56 I am _chandler_
•  » » » » » » » 5 months ago, # ^ |   -32 No offense, I am saurabhshadow
•  » » » » » » » » 5 months ago, # ^ |   -46 ChandleR ChandleR everywhere LOL !!
•  » » » » » » » 5 months ago, # ^ |   +10 hi bing!
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +4 oh my god !
•  » » » » » 5 months ago, # ^ |   +1 Could there "be" any more sarcasm!
•  » » » 5 months ago, # ^ |   -6 don't blame Joey for that Chandler.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -12 .
•  » » » 5 months ago, # ^ |   0 How does this have so many upvotes?
•  » » » » 5 months ago, # ^ |   +13 because he is errichto
•  » » » » » 5 months ago, # ^ |   +1
 » 5 months ago, # |   -172 Another Indian round. Check the writers profile.
•  » » 5 months ago, # ^ |   -20 Delusional
•  » » 5 months ago, # ^ | ← Rev. 2 →   +44 What does it have to do with the quality of the problem set? Furthermore, they're all Polish citizens so I'd rather call it a polish round.
•  » » 5 months ago, # ^ |   -58 Why Downvotes?anadi Anadi Agrawal is an Indian name and his skin is brown too(from the profile picture). So the guy is definately Indian. Nothing wrong with the comment.
•  » » » 5 months ago, # ^ |   +7 In enlightened societies, it is common to attribute no cultural characteristics to people based on names or physical characteristics, because this is generally the motive when characteristics are used as abusive words.
•  » » » » 5 months ago, # ^ |   +18 From what I've observed about the so-called (and usually self-proclaimed in some way) "enlightened" parts of society, it's very much not the case, they just pay lip service to the idea.
•  » » » » 5 months ago, # ^ |   -24 Could you speak in simple words? I cannot understand your point. This is not an English class in school.
•  » » » » » 5 months ago, # ^ |   +3 Sure. He says you're racist.
•  » » » » » » 5 months ago, # ^ |   0 Dude, are you fucking kidding me. You just don't understand the word if you go around calling everyone a racist. SIT DOWN KID!
•  » » » » » » » 5 months ago, # ^ | ← Rev. 6 →   -10 I never went around calling everyone a racist..
•  » » » 5 months ago, # ^ |   -8 I meant it in a positive way, like " Hi , everyone . I noticed something and want to tell you about it." But poeple got me wrong fast. Everyone mistook it, because some who didn't know what I wrote downvoted. Nevermind.
•  » » » » 5 months ago, # ^ |   0 Yeah dude, i know your intentions were pure just like mine. But people like minjoonist and spookywooky dont hesitate to label anybody a racist. It makes me sad! They would just label anyone a racist without even understanding what the comment actually means.
•  » » » » » 5 months ago, # ^ |   0 Yes , exactly.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 No, I just told you what he was trying to say. That is not my own opinion.
•  » » » » » 5 months ago, # ^ |   0 You're actually lying, because you actually wrote comments about disrespecting other nations, especially India. We can see every comment you ever wrote, you know.
•  » » » » » » 5 months ago, # ^ |   0 Please point out the comment where i disrespected India, thanks! I challenge you to point out even one comment of that sort.
•  » » » » » » » 5 months ago, # ^ |   0 https://codeforces.com/blog/entry/61877#comment-458565 https://codeforces.com/blog/entry/61877#comment-458567 https://codeforces.com/blog/entry/62750?#comment-467493 (not sure why you asked that question, but based on your tendencies it seems like you were trying to do so) There'd probably more, but I think your most disrespectful comments actually got erased.
•  » » » » » » » » 4 months ago, # ^ |   0 https://codeforces.com/blog/entry/62750?#comment-467493 I asked this because i was actually curious. (FCB1234 and anadi are the same person FYI)https://codeforces.com/blog/entry/61877#comment-458567 and https://codeforces.com/blog/entry/61877#comment-458565. This was just a joke. Not supposed to be racist at all. It was just fun based on stereotypes.Funny you call me racist and i am an Indian myself. There is a difference between a joke and actually being racist.
•  » » » » » » » » 4 months ago, # ^ |   0 ALso, if the comments get erased, they would still be visible in my profile. So if you see my profile, there would be no erased comments. For example, the first link you listed is deleted, but still visible on my profile.So don't ever dare label me a racist. Its all for hahas. Its just a dank/dark joke
•  » » » » 5 months ago, # ^ |   0 Even if that is so, you should be careful about how you write things. Because we cannot hear your tone in simple text, what you say can have double meanings. Perhaps a better way would have been "Look at the writer's profile. It's an Indian round", etc.
 » 5 months ago, # |   0 What about the score distribution tho'?
•  » » 5 months ago, # ^ |   -14 It will be published later.
 » 5 months ago, # | ← Rev. 5 →   -66
•  » » 5 months ago, # ^ | ← Rev. 3 →   -8 It was a misunderstanding. I apologized him for that.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +5 He changed his post, you can see it's first revision, i misunderstood it(as i'm not good at memes), then i posted that comment, then he sent me a privet massage complaining about my comment and he said he meant that "we are happy to see lots of contests"(and then iv'e realized i was mistaken), then i apologized him and changed my comment. I don't know what is wrong/annoying. I'm pretty sure that its not hurting anyone etc.
•  » » » » 5 months ago, # ^ |   +16 You lost 30 seconds requesting people not to judge you.
•  » » » » » 5 months ago, # ^ |   +1 Its a good habit when you are waiting for system testing, isn't it? :D
•  » » » » » 5 months ago, # ^ |   +8 LOL that is so true
 » 5 months ago, # | ← Rev. 2 →   +2 This website of algo muse has only 3 problems? what is this? is it under construction?
•  » » 5 months ago, # ^ |   +21 Open the past contests page — there are plenty of nice problems (with solutions)
•  » » » 5 months ago, # ^ |   +19 I found it, but it would have been better if all problems queued at the problems page.Anyway, thanks Algo Muse for the significant contribution and support to codeforces.
 » 5 months ago, # |   +13 I think there might be something wrong with the time link. Normally a time link is rendered as the local time for the blog reader but this one isn't.
•  » » 5 months ago, # ^ |   +22 Thank you, fixed it.
 » 5 months ago, # | ← Rev. 2 →   -77 Hoping for no geometry problems ....XD
 » 5 months ago, # |   +5 Master 0ogway!!! you are master here too!!!
 » 5 months ago, # | ← Rev. 2 →   -88 [Deleted]
•  » » 5 months ago, # ^ |   -33 What a meme XDXDXDXDXDXD
 » 5 months ago, # | ← Rev. 3 →   -42 I wish for no long queues, as there is right now. UPD: The queue was there when I wrote this comment.
 » 5 months ago, # | ← Rev. 2 →   +6 Tank you Algo Muse, i really liked the site and problems, I really recommend it for Computing Olympiads as a Computing Olympiads participant. I have a question, how to submit in Algo Muse?
 » 5 months ago, # |   -12 I hope I can solve problem C in div1 /rating++ !!
•  » » 5 months ago, # ^ |   -19 bilibill Hope keeps us moving
 » 5 months ago, # | ← Rev. 3 →   -63
•  » » 5 months ago, # ^ | ← Rev. 4 →   -14 Aha!! Fucking Shit!!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Practice hard Buddy!! It's the key to success.
 » 5 months ago, # | ← Rev. 2 →   -31 Hope I will get good results.（Though often after the contest I cry：“Nooooo~，Why am I sooo noob~”）
•  » » 4 months ago, # ^ |   0 same with me. I cry then I beat some meat from the kitchen. It's all good at the end of the day.
 » 5 months ago, # |   -51
 » 5 months ago, # |   -40 is it rated
•  » » 5 months ago, # ^ |   -36 Seems like your sorry ass never had one.You might have a chance if you don't copy someone else username too.
 » 5 months ago, # |   +4 Thank，Algo ZBW (doge)
 » 5 months ago, # |   +4 Missing this iconic line :- "Scoring distribution will be announced (just before the contest/later)".
 » 5 months ago, # |   +3 Hope to solve c in this round...
 » 5 months ago, # |   +31 Hope I can do well in my first Div.1 :)
 » 5 months ago, # |   -32 [Help]I am unable to register in Div-1 Contest. When I click Register It does nothing.
•  » » 5 months ago, # ^ |   0 Because your rating is too low to participate in Division 1. Participate in Division 2 instead.
•  » » » 5 months ago, # ^ |   0 Thanks!
•  » » 5 months ago, # ^ |   +60 Believe me..it's for your own good.. XD
 » 5 months ago, # | ← Rev. 3 →   -44 Edit-Hoping for more data structure problems?
 » 5 months ago, # |   0 I wish high rating to all contestants and high contribution to writers ;)
 » 5 months ago, # |   +3 Hey, guys!Right after contest ends, we will discuss the problemset live on Algopedia: https://youtu.be/ZPQzYDf5A4YGood luck to all!
•  » » 5 months ago, # ^ |   0 Hacked!
•  » » » 5 months ago, # ^ |   0 GG bruh, I figured out during the livestream that I messed up one case :))
•  » » » » 4 months ago, # ^ |   0 Romeo, I took your advice and started wearing blazers while coding. Now my GF thinks that I am a psycho wearing blazer and shorts in the middle of the night. We broke up. Now I am crying. Y_Y
 » 5 months ago, # |   +5 Thank you, Algo Muse! A very good website indeed. Thank you for your support.
 » 5 months ago, # |   -10 Hope I can solve 3 of 6 successfullyGood luck to you all！ :D
 » 5 months ago, # |   -25 How many shared problems will be?
•  » » 5 months ago, # ^ |   +5 Three problems will be shared (announcement).
 » 5 months ago, # | ← Rev. 2 →   -15 :(
 » 5 months ago, # |   0 Excited to solve the contest,happy coding.
 » 5 months ago, # | ← Rev. 2 →   +40 Why so few registrants(compared with the previous several contests)?
•  » » 5 months ago, # ^ |   +22 May be people are going back to their regular life like before covid-19 in many countries.
•  » » 5 months ago, # ^ |   0 Because of time (?
 » 5 months ago, # | ← Rev. 2 →   -12 Only red and orange coordinators this time... 3rd question might me little more interesting
 » 5 months ago, # |   0 Where are the funny memes, why aren't they here?(. I think it will not be interesting if this blog will be without memes (
•  » » 5 months ago, # ^ |   +13 I don't think memes are a good idea for a programming competition, not all people find them funny.
•  » » » 5 months ago, # ^ |   +10 just before that, there were memes at many blog contests and many of these memes took a lot of plus(i don't think that they were not funny if anybody plussed);
 » 5 months ago, # |   -67 Is this a rated contest or not?
•  » » 5 months ago, # ^ |   +20 None of the contests named as Codeforces Round #XX are rated.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -38 [deleted]
•  » » » » 5 months ago, # ^ |   0 Are you Sheldon Cooper ?
 » 5 months ago, # |   +7 Looking forward to the contest. But I wonder why the number of registrations is less than usual.
•  » » 5 months ago, # ^ |   +10 Lockdown is getting over at many places. So people are getting busy with their daily works. That might be the reason behind less no of registration.
•  » » » 5 months ago, # ^ |   +2 Most probably, Yes.
•  » » 5 months ago, # ^ |   +15 It is just around $20k$ both divisions combined.
 » 5 months ago, # |   -39 tourist gonna make it to the top again today
•  » » 5 months ago, # ^ |   0 Hope, he does so.. :)
 » 5 months ago, # |   -19 Can anyone tell me what does "Algo Muse" mean?
•  » » 5 months ago, # ^ |   0 Algo Muse is an educational site that conducts online algorithmic contests in pen-and-paper style (no coding)!
 » 5 months ago, # |   +66
 » 5 months ago, # |   +106 I'm not sure exactly why, but Div 1C sucked all joy and happiness out of my soul. I haven't hated a problem this much in a while.
•  » » 5 months ago, # ^ |   +20 +++The beauty of a connection of pearls in colors $u$ and $v$ is defined as follows: let $2^k$ be the greatest power of two dividing $u \oplus v$ — exclusive or of $u$ and $v$. Then the beauty equals $k$. If $u = v$, you may assume that beauty is equal to 20."Beauty"
•  » » 5 months ago, # ^ |   +35 I agree with you. The statement was boring. Moreover, the problem was stated quite weirdly and could definitely have been much simpler. Even though I got the solution a while before the end, I chose to sit back and enjoy the other problems rather than waste precious time implementing something that is so irritating.(The other problems were good (Okay, really — B was just some implementation) though.)
•  » » 5 months ago, # ^ |   +6 It's quite standard, yeah. Try all possible answers — take the last $b$ bits, convert it into the domino cycle problem, find an Euler cycle.
 » 5 months ago, # |   +6 why A->C are all the binary related problems?
 » 5 months ago, # |   +20 Am I the only one who thinks that the gap between Div2-D and Div2-E was HUGE ?
•  » » 5 months ago, # ^ |   0 I thought so but look at Div1 submissions (Div1A vs Div1B) :)
•  » » 5 months ago, # ^ |   +23 I think that problem statement for D was way too difficult to understand. That really did bridge up the gap
 » 5 months ago, # | ← Rev. 2 →   +23 Is there a special reason why the limits have to be so high so Python solutions are too slow? I mean at div2D there is no reason to set the limit at 5*10^5 when classic 10^5 or 2*10^5 would work just fine. What kind of solutions are you trying to prevent setting the limits so high?Otherwise a nice contest with interesting problems, but the TLEs at D and E completely frustrated me on this one ...
 » 5 months ago, # |   +35 what a bitforces contest
 » 5 months ago, # |   +59 Calling an arbitrary number in the input $p$ is not a good idea? I think $m$ or $a$ would be a more justified choice.
 » 5 months ago, # |   +90 Statement for Div 2 D was a little unclear in my opinion..
•  » » 5 months ago, # ^ | ← Rev. 2 →   +23 Stupid D... They even changed the statement a bit.
•  » » » 5 months ago, # ^ |   +45 Statements caused me 45 minutes to understand. Foolishness caused my rest 30 minutes.
•  » » 5 months ago, # ^ |   +41 Even after reading the same statement for 1Hr. Can't understand what is going on
 » 5 months ago, # |   +2 "It should have 1 hour contest" -- my feelings after solving A,B,C :P
 » 5 months ago, # |   +49 Anyone wasted time on B ignoring the sum of n over all test cases statement?
•  » » 5 months ago, # ^ |   0 Around half an hour
•  » » 5 months ago, # ^ |   0 me too
•  » » 5 months ago, # ^ |   0 me too
•  » » 5 months ago, # ^ |   0 whole contest...
 » 5 months ago, # |   +73 Participants.
•  » » 5 months ago, # ^ |   -35 So your D failed system test. So prefer investing your time in checking for boundary cases inseting of posting this meme all time. You solved D on 8:56. So you were having enough time to atleast recheck your submissions(if you are unable to move further) but no you prefer showing off. Now enjoy failed system test
•  » » » 5 months ago, # ^ |   +11 OK.
•  » » » 5 months ago, # ^ |   0 Never knew moms were on cf
 » 5 months ago, # |   +7 What would be the rating of div2D
•  » » 5 months ago, # ^ |   +83 For Understanding : 3000 For solving: 1900
•  » » » 5 months ago, # ^ |   +3 It took me out of breath to understand the clumsier statements. And then foolishness took me to search for dfs solutions having an easy greedy one. But, finally mananged to solve a D in a div2 contest.
•  » » » » 5 months ago, # ^ |   +3 Can you please explain your solution ?
•  » » » » » 5 months ago, # ^ |   0 There was a checker whether answer exists or not. Suppose we have node with topic x then for each of its neighbours 1) There must be at least one node must have topic ranging from 1 to x-1. 2) No neighbouring node has value x. If answer exists: Print all blogs which has topic 1 then 2 and so on. Solution Link: 82531854
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 a greedy solution will work.initialise assigned array of size n and default value =0 now the nodes on the basis of required final topicsfor each node from sorted list. if any node adjacent to current if required value is same then conflict and print(-1) else check if the required final topic of this node can be assignedchecking step : if x to be assigned to a node then all the values from 1 to x-1 should appear on the neighbours of this node (this step can be done using a set).
•  » » 5 months ago, # ^ |   +12 Probably 1600 or 1700. Even though the problem statement was confusing the implementation was pretty straightforward.
•  » » 5 months ago, # ^ |   0 I thought maybe its topological sort but got WA on 5th case :(
 » 5 months ago, # |   0 What was test case 9 on D?
 » 5 months ago, # |   0 Solved 5 problems for the first time!I hope the pretests on D were strong. Last time there was a problem like that with large amounts of input, my code passed pretests but not system testing ;.; I made sure my scanner was fast this time but you never know -- it was around 1700 ms on the pretest so might be a bit tight/
•  » » 5 months ago, # ^ |   0 Fingers crossed bro! Same here but 1107 ms. Note: I used customized fast IO.
•  » » 5 months ago, # ^ |   0 Wow, congrats bro.
 » 5 months ago, # |   +8 How to solve Div2E/Div1B?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +22 Sort the $k_i$'s in descending order. Put the largest $k_i$ in the first set, then add the next few $k_i$'s in the second set until the sums are the same. Repeat this process until there are no more $k_i$'s to choose from.The key observation is that when you have $p$ $p^{x}$'s, that's equivalent to having a single $p^{x+1}$. You can keep a list $L$ of all your $k_i$'s and combine the last $p$ elements once $L[m-p+1] = L[m]$ where $m$ is the current length of $L$.My submission
•  » » » 5 months ago, # ^ |   +3 You meant it is equivalent to have p^(x+1) and not (p+1)^x ?
•  » » » » 5 months ago, # ^ |   0 Yes, thanks :)
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I thought of a solution on these lines but was totally clueless since couldn't prove nor my intuition agree to this.Any ideas on the proof that this should work?
•  » » » » » » 5 months ago, # ^ |   0 Consider writing some number $X$ in base $p$. Then, $X = a_0p^0 + a_1p^1 + a_2p^2 + ...$. If any $a_j \ge p$, then we just add $a_j/p$ to $a_{j+1}$ and mod $a_j$ by $p$. At some point, all $a_j$ will be strictly less than $p$.For every $k_i$, we're adding 1 to $a_{k_i}$. Because of the sorting order, this means that we'll always be adding values less than or equal to the largest $k_i$. Each contribution only adds 1 to some number of $a_j$'s where $k_i \le j \le k_{max}$, so we'll never overshoot the first set's sum.
•  » » » 5 months ago, # ^ |   0 I used the same logic but got WA on TC 7. Now I feel so bad. Could've been the first time I solved E.
 » 5 months ago, # |   +8 How to solve E?
 » 5 months ago, # |   +55 What was the point of making div1D a geometry problem? Forcing us to angle sort adds nothing to the problem.
•  » » 5 months ago, # ^ |   -63 It was initially a little bit different, and it just stayed in our heads in that form.
 » 5 months ago, # |   0 Did anyone else spend long hours debugging Div1C because they did not check whether the graph is connected when checking whether Euler cycle exists?
 » 5 months ago, # |   +128 Still got no clue what happened in problem after reading div1A statement for three times.
 » 5 months ago, # | ← Rev. 3 →   +28 I doubted my English Reading Skills after Reading Div2 D.PS :I feel D was easy but difficult to decipher what is asked to do!
•  » » 5 months ago, # ^ |   0 Same lol, I solved it at last but it's too late to submit
 » 5 months ago, # |   0 Idk how people solved C that easily I guess I solved it the hard way
•  » » 5 months ago, # ^ |   0 I just feel : lets try doing this and it worked, then proof by pretests passed!
•  » » 5 months ago, # ^ |   0 what was your logic?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 I don't know how to explain it in English here's my Submission
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Try writing some numbers (till 11 maybe ) in binary, now try to find out contribution from each bit position of all numbers to final answer. There can be at most 63 bits in number and contribution from the ith bit is n/2^i.My code : void solve() throws Exception { int t=ni(); while(t-->0){ long n=nl(); long ans = 0; for(int i=0;i<63;++i){ ans+=(n/(1L<
 » 5 months ago, # |   0 Speedforces for Div2
 » 5 months ago, # |   +33
 » 5 months ago, # |   +96 Mfw my first integer overflow bug after like $10^{9}$ years :PepeHands:
 » 5 months ago, # | ← Rev. 3 →   +1 How to solve D2E?
 » 5 months ago, # | ← Rev. 2 →   0 is D1C/D2F finding the eulerian circuit based on the graph made by splitting the numbers into sets with equivalent last k bits? If so asking for an actual necklace seems kind of pointless.
•  » » 5 months ago, # ^ |   +8 Yes, and that's what makes asking for actual necklace useful. Otherwise you could guess conditions for euler circuit without really understanding solution, and it was an actual coding problem for once before d1 D! (I got stupid tle though...)
•  » » 5 months ago, # ^ |   0 Yes. It is finding an Eulerian circuit.However, the algorithm to actually find the circuit is a separate, and significantly harder algorithm than only checking whether the circuit exists.
•  » » » 5 months ago, # ^ |   0 May someone point me to resources for Graph Algorithms? I reduced it to the fact that we needed to find Eulerian circuit but did not know how to.
•  » » » » 5 months ago, # ^ |   0 I think it's covered in pllk's Competitive Programmer's Handbook
 » 5 months ago, # |   -8 Can someone please help me figure out my solution for Div2E fails hidden tests? 82562768
 » 5 months ago, # |   0 How can I test my solution before the system test's done?
 » 5 months ago, # | ← Rev. 2 →   +69 Am i the only one that wasn't able to understand exactly what 2D was asking?
•  » » 5 months ago, # ^ |   +16 same here buddy... couldn't understand shit
•  » » 5 months ago, # ^ |   +3 Finally, I knew the meaning of D but havn't got time to solve it. Even got to know a wrong meaning of D took me about half an hour.
•  » » 5 months ago, # ^ |   +3 same
•  » » 5 months ago, # ^ |   +7 Sorry, probably we should just put the formal statement there.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -34 no problem
•  » » » » 5 months ago, # ^ |   +37 any other suggestions, Sir ? The community will be blessed.
•  » » 5 months ago, # ^ |   +14 Even an example was not friendly enough to understand what question was asking.
•  » » 5 months ago, # ^ |   +3 & i thought that i was the only who was not able to understand this problem and cursing myself that my english is so bad. Believe me it took almost an hour to properly understand what the hell is this statement saying. Also i didn't read the line that references are bidirectional.
 » 5 months ago, # |   +108 Div 1 C's statement could have been written better. The word "connection" was used to refer to both the connection between two pearls in a necklace part and a connection formed by glue. The statement also alternates between saying the glue merges two pearls into one and saying the glue forms a connection between two pearls. IMO it shouldn't be necessary to look at the sample in order to understand the problem. They should just said we have to form a necklace by gluing together pairs of pearls, and the beauty is the greatest beauty of each glue connection. This way it's clear that only the glue connections are counted.
 » 5 months ago, # |   +25 DIV2 D is just like an English comprerhension which I always do to get pass the English level exam.BTW, it's so frustrated to konw in the last few minutes before the contest is over that the points are only referenced with its neighbors not the whole graph which they can get to. Havnt got much time to solve the new realized D. Ratings down again :(
 » 5 months ago, # |   +81 Imagine competing from a train and waiting till you exit a tunnel so you could submit.
•  » » 5 months ago, # ^ |   +6 You are lucky you even got internet connection. I once tried to do that and it sucked so bad.
•  » » » 5 months ago, # ^ |   +8 4G on phone, the coverage isn't perfect but it's decent. There's supposed to be free wifi in the train, but it doesn't work... unsurprisingly.
•  » » » » 5 months ago, # ^ |   0 Is there really so many tunnels in the route where you were travelling??Which route were you in that tunnels were so frequent that it was affecting submissions??No offense
•  » » » » » 5 months ago, # ^ |   +10 Bruh Slovakia is mostly mountains. Trains go along rivers when they can, but sometimes it's just a mix of tunnels and thin valleys between mountains where no internet exists.
•  » » » » » » 5 months ago, # ^ |   +1 Can you justify the third line of your template :)
•  » » 5 months ago, # ^ |   +9 Imagine not to eat anything for about 12 hours and taking part in a contest in the last 2 hours. :(
 » 5 months ago, # | ← Rev. 2 →   0 Am i only one who solved A ,with bits ? (took me 40+ minutes)
•  » » 5 months ago, # ^ |   0 I should have followed the normal approach,wasted a lot of time
 » 5 months ago, # |   -6 spend over 1 hr on that B and finally got brute force accepted XDD!!
•  » » 5 months ago, # ^ |   0 yeah, the only observation needed was that taking a number k greater than 1023 will make the xor with $a_i$ > 1023, and hence there is no chance to get the original array.
•  » » 5 months ago, # ^ |   0 Actually I was trying to come up with faster solution and then I saw leaderboard submissions for B were shooting like anything. So I thought maybe brute force will pass.. :D
•  » » » 5 months ago, # ^ |   0 tho C and D were easy so i was saved
 » 5 months ago, # | ← Rev. 2 →   +4 Nice contest, i really liked the problemset. Thank you all who worked hard to make this nice contest.I'm looking for the editorial :D.
 » 5 months ago, # |   +22 Was Div1C pretest 13 anything special? I kept getting TLE. Edge case or a matter of optimiziation?
•  » » 5 months ago, # ^ |   +70 Whenever there is Euler cycle problem on CF there is always some high-rated coder that is surprised cause he got TLE. Such surprised coders include people like Yuhao or subscriber iirc. I can almost surely tell you without looking at your code that it has some bug making it work in sth like O(nm).
•  » » » 5 months ago, # ^ |   0 Yea that's likely it -- the euler cycle code in my TCR didn't compile so I wrote a new one from scratch. Asking for problems :'-)
•  » » » 5 months ago, # ^ |   +20 The DFS implementation is best. It's obvious that it only visits each edge once because we pop_back edges and that it visits the whole graph because it's DFS. When it doesn't work, it needs to have such a stupid bug that it doesn't give right answers almost ever. Whenever I was able to write it in such a way that I'd believe that it works, it was always correct.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I didn't actually read your solution, but did you find out whether the Euler cycle code was the problem? I TLE'd on 13 as well and it turned out I needed to fix constant factor optimization (later TLE'd on 14 and 17 as well), but my solution didn't use Euler cycle code and had really high constant factor so perhaps that's why.
•  » » » 5 months ago, # ^ |   +13 Yes it was as Swistakk suggested, the complexity was actually $O(nm)$. After fixing my euler cycle code it ran in half a second, so the timelimit seems fine to me. 82567726
 » 5 months ago, # |   +92 "The magic glue allows Megan to merge two pearls (possibly from the same necklace part) into one."The sentence above is from C. I looked over and over again at the statement and samples to find out what does it mean to merge two pearls into one. Could anyone help?
•  » » 5 months ago, # ^ |   0 Me too, he meant to connect them. ( to then form a necklace at the end )
 » 5 months ago, # |   +42 Div1C statement should be: "Given edges, numbers. Write Euler cycle. Hate answer recovery".
 » 5 months ago, # |   +44 took me hours to understand 2D, I really hope it was more friendly and easy to read.
•  » » 5 months ago, # ^ |   +3 Can you explain your solution ?
•  » » » 5 months ago, # ^ |   0 I would love to, but still, it was last minutes implementation. I still worried if it can pass the system test or not.
•  » » » 5 months ago, # ^ |   0 Just use greedy technique start filling nodes in increasing value order 1->2->3.....so on. U will understand in better way if u will do some paper work.
•  » » » 5 months ago, # ^ | ← Rev. 4 →   0 turn out i got an accepted. So here's my implementation.For each vertex, i find if it was possible to make this vertex have its topic. For vertex u that desired to be in topic tu, i check if the neighbors (adjacent vertexes) have every topic between 1 and tu − 1(inclusive). If vertex u is desired for topic 5, I check if the neighbors have at least a vertex with a topic between 1 and 4(inclusive). If there are no neighbors with topic x for 1 ≤ x ≤ 4, the answer should be "-1". If a vertex has topic 1 i just ignore it, because there is no topic below '1'.It's also impossible to find a valid answer if a vertex has an adjacent vertex that has a same topic. To find the permutation i used Dijkstra that sort vertexes by their topic(ascending) using a set. First, i push vertex with topic 1, next when accessing u if there is an adjacent vertex that has topic tu + 1, i also pushed the vertex into the set. Lastly when i accessed a vertex i push that one in vector to print the answer later. If i cannot visit all vertex then there is no answer.I tried to explain as best as i could sorry for my bad english.Edit: fixed some error.
•  » » 5 months ago, # ^ |   0 same here
•  » » 5 months ago, # ^ | ← Rev. 2 →   +19 A friend of mine asked me to rephrase the question, so they could understand it better.Maybe this could help others too.There are N nodes with M bidirectional edges connecting them, each node has no "value" currently. You can do an operation to a node, which is as follows: Define S as the set which contains all values of its neighboring nodes (that have values set to them), then take the smallest positive integer that is not in that set.Edit : If set S is empty, the smallest positive integer would be 1.Given the final values of all nodes, determine the order to do these operations to the nodes (each node can only be applied with an operation once) or if it is impossible.
•  » » » 5 months ago, # ^ |   +14 What if the set is empty ? Btw great explanation, this is how problem statements should be.
•  » » » » 5 months ago, # ^ |   +19 If the set is empty, then we should take the smallest positive integer that is not in the set, which is 1.
•  » » » » 5 months ago, # ^ |   +3 Thanks for the feedback, I fixed it.
 » 5 months ago, # |   0 Where did i mess up in B: 82560946?
•  » » 5 months ago, # ^ |   0 Can you please explain your approach I am not able to get what you are doing with this code ?
•  » » » 5 months ago, # ^ |   +3 Brute force from 1 to 2050. And then checking if the resultant array after xor-ing has same elements as original array.
•  » » » » 5 months ago, # ^ |   0 I think you messed up in frequency count in one place you are setting 1 for all the entries and when inside the loop you are using ++ which may be the cause ! You should have used Freq[i]++ in the first loop itself
•  » » » » » 5 months ago, # ^ |   0 I did that in my previous submission. Only difference is that i also handled the case for n = 1 in that. So, idk. :(
•  » » 5 months ago, # ^ |   0 You also need to check how many a number appear in the desired set, not only if it appears in the set or not.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 If I understand your code correctly, you should have checked f[x[j]] == freq[x[j]] instead of f[x[j]] == 1 && freq[x[j]] == 1. My approach was to sort the XOR-ed array and compare it with the original one element-by-element: 82500274Edit: turns out you can even use the == operator for vector, which makes it even easier: 82567200
•  » » » 5 months ago, # ^ |   0 According to the statement, every integer in the set is unique so it must occur only once right?
•  » » » » 5 months ago, # ^ |   0 Oops, right. Then I don't know either :-/
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 .
 » 5 months ago, # |   0 How to solve div2-D?
•  » » 5 months ago, # ^ |   0 My solving: for each target number from least to biggest we trying to put this number to the vertices and check (using set and its size), is it smallest possible number and is it possible to put it to the current vertice. Here is submissionSorry for my english.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 a greedy solution will work.initialise assigned array of size n and default value =0now the nodes on the basis of required final topics for each node from sorted list. if any node adjacent to current if required value is same then conflict and print(-1) else check if the required final topic of this node can be assigned checking step : if x to be assigned to a node then all the values from 1 to x-1 should appear on the neighbours of this node (this step can be done using a set). 
•  » » 5 months ago, # ^ |   0 Pick topic in increasing order and check if you can assign it to its respective blog(say curr). What to check : In the adjacency list are the blogs referenced to curr. See what topics are assigned to these blogs. Find the smallest positive topic(say temp) not assigned to these blogs Spoiler[You can find it in O(blogs)]. Read thisIf temp == topic assign topic to curr and continue. Else ans is not possible. Sorry if my language is unclear, for reference you can see my submission
 » 5 months ago, # |   0 Ah! Submitted div2-D at the last minute. But server was busy. Several minutes later I saw that it did not get submitted.
 » 5 months ago, # |   +3 For C : Why does "<<" results in overflow for finding power of a number? My solution failed for "1<<(i+1)" but worked for "pow(2,i+1)" // after contest :(
•  » » 5 months ago, # ^ |   +16 It should be 1LL << i + 1.
•  » » » 5 months ago, # ^ |   0 Thanks, I get it. This stupid mistake cost me C.
 » 5 months ago, # |   +12 can somebody please explain div 2-D statement.
 » 5 months ago, # |   0 Does D2C answer fit in long long? i got wa on pretest 4 and then thought answer might not fit in ll, but time was over then.
•  » » 5 months ago, # ^ |   0 I wasn't sure either, but it seems like it does: 82505887
 » 5 months ago, # |   +195 Statement of C was terrible. But not in the "broken English" way, because English was fine, but it used a lot of confusing expression. Merging/gluing/chain/necklace parts etc. it was all very confusing. It took me about 10 minutes to understand the statement and 10 seconds to come up with the solution once I understood it.
 » 5 months ago, # |   +7 Statement for Div2D was pretty hard to comprehend & difficulty gap between Div2D & Div2E pretty huge, but besides that I really enjoyed the contest!
 » 5 months ago, # |   +28 Skipped div2C for div2D and ruined the contest. I am still not able to understand what question D is asking.
•  » » 5 months ago, # ^ |   0 Sigh. Had over 1 hour to solve D, but just couldn't understand what it was asking for. Still don't..
 » 5 months ago, # |   0 What's wrong with this Div2 D / Div 1 A?https://codeforces.com/contest/1362/submission/82556780
•  » » 5 months ago, # ^ |   0 me too on pretest 5
•  » » 5 months ago, # ^ |   0 it is the case when like we have to put 5 on the current node and its adjacent nodes contain 1 2 3 3.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Could you provide a concrete input/output example?Here: 5 4 1 2 1 3 1 4 1 5 5 1 2 2 3 Isn't the answer supposed to be -1?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 yup actually i also once got wrong ans on TC5 and then i found my algo is not working on that type of cases that i proposed earlier
•  » » » » » 5 months ago, # ^ |   0 Yeah, thanks. I can't find a small case for which it fails.
 » 5 months ago, # |   0 For the first time, I was on the verge on solving E during contest. My logic was to first sort the numbers in reverse order. I'll always add the first number to the result. Then I maintain two variables rem and currency. rem denotes the number of elements equal to currency required to make the result zero. In each iteration, if rem is greater than zero, I subtract the element from the result. Otherwise, I add the element to the result and set rem to 1. I make sure to update both rem and currency` as required while I loop through the array. I could get 7 testcases to pass. Could you find the flaw in the code or the logic? 82557476
 » 5 months ago, # |   0 I don't know how but I get RTE for div2D/div1A. My algorithm is quite straight forward, but somehow get RTE when trying to sort g[u]: the list of adjacent nodes for node u in the increasing order of t[].Can anyone help?. Here is my submission
 » 5 months ago, # |   +14 Lol didn't notice that sum of n over all test cases will not exceed 1024. :P
•  » » 5 months ago, # ^ |   0 XD i spend over 1 hr on that tho i finally got that!! i was lucky XDD
 » 5 months ago, # |   -6 The questions were fun to solve. It should be called Codeforces Round #647 — The Bitmask.
 » 5 months ago, # |   +35 ![ ]()
•  » » 5 months ago, # ^ |   +3 I never knew what OEIS was !! LOL thanks for such an awesome resource
•  » » 5 months ago, # ^ |   0 What does OEIS means? I solved it by observation.
•  » » » 5 months ago, # ^ |   +55 Observation Enthusiast Intelligence Solving!
•  » » » » 5 months ago, # ^ |   0 o_o
•  » » » » 5 months ago, # ^ |   0 Omg, I'm not that cool
•  » » » 5 months ago, # ^ |   +10
•  » » 5 months ago, # ^ |   0 Could you please explain how C can be solved with the help of OEIS? What must I search for in OEIS?
•  » » » 5 months ago, # ^ |   +3 Type the furst few terms of the sequence separated by commas
•  » » » » 5 months ago, # ^ |   0 Thank you
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Just search 1 2 1 3 on OEIS and you will get the formula- 2*n-countsetbits(2*n).
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 That is what actually I did but I took more time to solve C. I missed Master for 3!!!
 » 5 months ago, # |   +2 Free Fall!!! I hope just don't die :(
 » 5 months ago, # | ← Rev. 2 →   +4 I was done with Solution of B. P00R ME
•  » » 5 months ago, # ^ |   0