### Theo830's blog

By Theo830, 4 weeks ago,

Γεια σου (Hello), Codeforces!

Dremix10 and I are glad to invite you to the first Cypriot round Codeforces Round #747 (Div. 2) which will take place on Oct/08/2021 18:05 (Moscow time). Note the unusual start time of the round. As usual, this round will be rated for participants with rating lower than 2100.

Problems were created and prepared by Dremix10 and me. We tried to make them interesting, with short and clear statements. We hope that you will enjoy them!

I would like to thank:

You will be given $6$ problems (and one subtask) and $2$ hours and $15$ minutes to solve them. Scoring distribution will be announced later.

Good luck and have fun!

UPD1:

Score Distribution: $500-1000-1500-1750-(1000-1500)-2750$

UPD2:

Editorial

UPD3:

Div2:

Div1 + 2:

• +586

 » 3 weeks ago, # |   +5 Hoping for a good contest :)
•  » » 3 weeks ago, # ^ |   +8 will see :):
•  » » » 3 weeks ago, # ^ |   +12 A good one for me , i have done 4 problems :)
•  » » » » 3 weeks ago, # ^ |   0 that's awesome brother :)
 » 3 weeks ago, # | ← Rev. 3 →   +26 nvm, added in the blog.
•  » » 3 weeks ago, # ^ |   -36 Usual — 150 min
•  » » 3 weeks ago, # ^ |   -11 And also notice the unusual duration of this contest (usual time + 15min)
•  » » 3 weeks ago, # ^ |   +5 Ahh Thank you so much M0riarty.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 If you'd just added this to your original comment everyone would know what you are talking about without going back through the revision history.
 » 3 weeks ago, # | ← Rev. 2 →   +35 As a tester, I found problems are new and clear.UPD: Problem D found copied. I take my words back.
•  » » 3 weeks ago, # ^ |   +5 How do you know they are new? Have you checked all the problems that have ever been published?
•  » » 3 weeks ago, # ^ |   +7 Not very new after all.
•  » » 3 weeks ago, # ^ |   +19
•  » » » 3 weeks ago, # ^ |   +7 None of the testers found it while testing :(
•  » » » » 3 weeks ago, # ^ |   0 And those who were downvoting my comment above should now be ashamed of themselves. :)
•  » » 3 weeks ago, # ^ |   +4
 » 3 weeks ago, # |   +64 As a tester, I hope you will enjoy the problems as much as I did :)
•  » » 3 weeks ago, # ^ |   0 As a Participant I'll tell my feedback after the contest!
•  » » » 3 weeks ago, # ^ |   0 Till then, your feedback wouldn't be much useful, I think.
•  » » » » 3 weeks ago, # ^ |   0 As a blog reader, I thought let's continue the comment series
 » 3 weeks ago, # |   +45 As a tester, enjoy!
 » 3 weeks ago, # |   -8 I don't know Theo830 in actuality, but I understand he is a really hardworking person!
 » 3 weeks ago, # |   +273 Roses are red Energy is produced by nuclear fusion The contest is great As a tester, I want contribution
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +9 Well, let's hope all the problem statements are not quatrains like this one.
 » 3 weeks ago, # |   +4 does one subtask means that one problem will be divided to easy and hard versions ?
•  » » 3 weeks ago, # ^ |   0 That's right.
•  » » » 3 weeks ago, # ^ |   0 thanks
 » 3 weeks ago, # |   +19 I wish this round will be my last round in grey :)
•  » » 3 weeks ago, # ^ |   +1 Your graph indicates that you're a hard-worker. I wish you the best of luck.
•  » » » 3 weeks ago, # ^ |   0 Thanks bro you made my day :)
•  » » 3 weeks ago, # ^ |   0 the same ^_^
•  » » 3 weeks ago, # ^ |   0 I wish this round will be my last round in Green :)
•  » » » 3 weeks ago, # ^ |   0 I wish this round will be my last round of Cyan ;)
•  » » » 3 weeks ago, # ^ |   0 Same
•  » » 3 weeks ago, # ^ |   0 :))
 » 3 weeks ago, # |   +1 Will probably get of of grey.
 » 3 weeks ago, # |   -28 Hey please help me out with this problem.
•  » » 3 weeks ago, # ^ |   0 ab + bc + ca = ((a + b + c)^2 — (a^2 + b^2 + c^2))/2;2 segment trees.
•  » » » 3 weeks ago, # ^ |   0 I didn't know segment tree yet...I will study and do it....I was applying fenwick tree but getting tle.. thanks a lott...
 » 3 weeks ago, # |   0 I will be impatiently waiting for the start of the round!
 » 3 weeks ago, # |   +70 As a first feedback giver, I can say that Theo830 worked really hard to make an interesting and enjoyable round for you guys!
 » 3 weeks ago, # |   0 " with short and clear statements. " Thanks :)
 » 3 weeks ago, # |   +4 Why is it such a strange time
 » 3 weeks ago, # | ← Rev. 2 →   0 +1
 » 3 weeks ago, # |   0 Hello everyone! Good luck to everyone on the contest!)
 » 3 weeks ago, # |   0 Hoping for a good contest.
•  » » 3 weeks ago, # ^ |   +1 ))
 » 3 weeks ago, # |   +6 I don't like subtask.
•  » » 3 weeks ago, # ^ |   +30 Meanwhile testers:
 » 3 weeks ago, # |   -12 let's play
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 thanks
 » 3 weeks ago, # |   +5 I hope it will be my last contest in grey ^_\, wish me luck.
•  » » 3 weeks ago, # ^ |   +20 Bhest aaf lack
•  » » » 3 weeks ago, # ^ |   0 thanks you too bro
•  » » 3 weeks ago, # ^ |   +13 Are you planning to retire after this round? XD
 » 3 weeks ago, # |   0 Hoping to enjoy an interesting contest!!!!
 » 3 weeks ago, # |   0 I hope this round will be my last round in grey (:
 » 3 weeks ago, # |   +1 18:05 in blog is just Moscow time right?
•  » » 3 weeks ago, # ^ |   +11 Fixed, thanks for pointing out.
 » 3 weeks ago, # |   0 WoHOOOO, contest after a long time!
 » 3 weeks ago, # |   +3 lighthearted meme
•  » » 3 weeks ago, # ^ |   +20 I just want to add that "this round will be my last round in grey" is more ambitious than "I will become pupil after this round". :)
•  » » 3 weeks ago, # ^ |   +32 Why are all of your memes light-hearted?
•  » » » 3 weeks ago, # ^ |   +9
 » 3 weeks ago, # |   0 Hope to score, even a little
 » 3 weeks ago, # |   +4 What do you mean by first Cypriot round ?
•  » » 3 weeks ago, # ^ |   +15 Both setters are from Cyprus. And as they mentioned, this is the first ever fully Cypriot round.
 » 3 weeks ago, # |   0 Good luck too all
 » 3 weeks ago, # |   0 Long queue! I hope it gets resolved asap.
 » 3 weeks ago, # |   +7 Hope the long queue will be ended before the contest...Best of luck to everyone!!!
•  » » 3 weeks ago, # ^ |   -9 I never found such things happen to atcoder
 » 3 weeks ago, # |   0 Moving on from Green tonight...
 » 3 weeks ago, # |   0 Wish today I will get break up with GREY
 » 3 weeks ago, # |   0 system is testing so slow :( hope it won't cause unrated round
•  » » 3 weeks ago, # ^ |   0 May be it will be postponed
•  » » 3 weeks ago, # ^ |   +2 No it's not? The system testing is excellent in terms of speed.
 » 3 weeks ago, # | ← Rev. 2 →   0 This is so weird. I couldn't be able to solve any problems of the past 3 contest =(
•  » » 3 weeks ago, # ^ |   +8 That's because of your bad profile picture.
 » 3 weeks ago, # |   0 I AM NOT ABLE TO SUBMIT IT SAYS AM NOT REGISTERED
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 You should register before the contest begins next time or 10 minutes after it starts, sadly you can't compete now but you can solve the problems after the contest ends!
 » 3 weeks ago, # |   +22 Three lessons I've learned today: I am stupid who can't solve any problem with counting E2 is much harder than F tourist is god
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +21 4) don't tell spoilers.
 » 3 weeks ago, # |   -7 speedforces. D was nice though.
 » 3 weeks ago, # |   +3 I solved A in 1hr 5 mins I don't know how can I miss that silly thing and ended up solving B,C and E1 so never give up till last.
 » 3 weeks ago, # | ← Rev. 2 →   +4 for 1.45 h I couldn't solve any problem then in the last 30 min, I solved problem A and C so cool even if I lose points this is good problems I ever seen in div2 problems well done ^_^
 » 3 weeks ago, # |   +1 How to solve C?
•  » » 3 weeks ago, # ^ |   +6 If all the characters in the given string are c then the answer is 0. Else just use brute force whether the answer can be 1. If the answer cannot be 1 then the answer will be 2 as we can always select n and then n-1.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If nothing to change then answer is 0. If only the last character is to be changed, the answer is 1 2 or 1 3 depending on wether n is odd or even. If some character/character**s** other than the last are to be changed, then the answer is 1 N. If both 2) and 3) then answer is 2 N 2 or 2 N 3 (if N is odd then 2 N 2, else 2 N 3). This failed on pretest 2. Can you explain whats wrong with this? Unable to view pretest 2 right now.
•  » » » » 3 weeks ago, # ^ |   0 N can be divisible by both 2 and 3 :)
•  » » » » » 3 weeks ago, # ^ |   0 so for example6 a baabbb
•  » » » » 3 weeks ago, # ^ |   0 Here is my solution. https://codeforces.com/contest/1594/submission/131189048If you pick your any of the number in the latter half of array, all other elements can be replaced as 2*element index will be greater than n.You have to consider cases when the last 2 elements are not the correct ones but there exists some index in the later half of the array with the correct character. That index can be chosen to replace all the remaining elements in 1 operation instead of 2 operations.Take some examples and go through the solution. If you still can't figure it out, post your question. Cheers!
•  » » » » 3 weeks ago, # ^ |   0 8 a aaaaababYou say the result is 2 3 but its actually 7
 » 3 weeks ago, # |   +11 sus (pun intended)
•  » » 3 weeks ago, # ^ |   0 And here I was, shocked, bamboozled, confused whether I am crazy, hallucinating, or just sleepy when I saw blue Indian kids solve D in like 5 mins or so. To whoever authored this problem, if it was a weird coincidence, then oh well, shit happens. Otherwise, fuck you.
•  » » » 3 weeks ago, # ^ |   +18 We would have never used a problem that we knew already existed and was created by someone else, we started creating this round 15 months ago and wanted to make it the best possible. A coincidence indeed, unfortunate for all of us and we are really sorry about it.
•  » » 3 weeks ago, # ^ |   +35 We are really sorry for this, we were not aware that this problem already existed and the idea -we thought- was ours and came from scratch inpsired by the game "among us".
•  » » » 3 weeks ago, # ^ |   -40 Hello yes, to me seems like a notorious coincidence that both ur problem and the one where it matches were exact the same and also based on among us.
•  » » » » 3 weeks ago, # ^ |   +38 We would never use a problem that we knew already existed, we gain nothing by doing that as we spent more than 15 months on this round and wanted to make it as best as possible. We are really sorry.
•  » » » » 3 weeks ago, # ^ |   +41 Among us was a very popular game when I created that problem and the games of people that always say the truth or always lie are also really popular. You can definitely think whatever you want but do you really think that we copied the problem and said that it was ours? It is very sad to read comments like this. We tried our best to make a contest with short and clear statements and solutions that weren't very long. Again, we are really sorry for what happened (especially to the_hyp0cr1t3 the author of the original problem). If we will do another contest in the future we will be more careful about these things.
•  » » » » 3 weeks ago, # ^ |   +4 Its not as unlikely as you might think, the INOI version was just a direct formalization of how an average emergency meeting goes in the game that the_hyp0cr1t3 came up with when a few of us were attempting to set problems after we had just played it.Its a very natural formulation and the min / max decision is a 50-50 choice anyway. The only other natural thing you can do with it is check if exactly $k$ imposters are possible and that's just boring addition of knapsack which also requires reducing constraints.
•  » » » 3 weeks ago, # ^ |   0 No worries, it happens :) I enjoyed solving the problems and I think the contest is very good!
•  » » » 3 weeks ago, # ^ |   -14 Choose better testers next time. :(
•  » » » » 3 weeks ago, # ^ |   +16 Testers are not to blame, they did their job as best as they could and their feedback was very helpful. We will make sure that nothing similar to what happened today will happen again in a round authored by us, we apologise.
•  » » » » » 3 weeks ago, # ^ |   +4 the suckers can suck, it was a great problem set that was amusing and fun to solve, to say the least.
 » 3 weeks ago, # |   +37 Ironic how Problem D is an imposter. I had authored and created the same problem a while ago on codechef for INOI haha :3
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 there is an imposter among us!!!! P.S. It happens and has been fairly explained by comments above
 » 3 weeks ago, # |   +57 Problem D is same as INOI 2021 Among Us
•  » » 3 weeks ago, # ^ |   +1 What was the intended solution? I was trying DSU's. I had the idea, but couldn't come up with an implementation.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Yes DSU works. The solution I submitted used DSU. Basically it's Online Bipartite except for the fact that "Online" is never used. So you can basically do it with simple DFS/BFS as well.
•  » » » 3 weeks ago, # ^ |   +3 I think a variation of bipartite color assignment could also work.
•  » » » » 3 weeks ago, # ^ |   +3 This was the expected soln for the INOI version of the problem iirc, just try to colour the nodes, propogating the same colour for edges of type 1 and the opposite colour for edges of type 2.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 Let's say the edge weight of i,j is 1 if i says that j is an imposter or j says that i is an imposter, similarly 0 for non-imposter relationship. You can just color them. col[i] = 1 means i is imposter, else col[i] = 0. For every edge (i,j) col[i]^col[j] = edge weight. Now, this becomes similar to a bipartite graph problem with the maximum number of white nodes.
 » 3 weeks ago, # |   -11 F is such a troll problem. Also why so tight TL in E2? I had to optimize constant to make it pass.. or maybe I have wrong solution :)
•  » » 3 weeks ago, # ^ |   0 I replaced unordere_map/unordered_set with map/set and reduced the running time from TLE to 124ms.. not sure if some of the test cases were deliberately designed to make c++ unordere_map/unordered_set fail.
•  » » » 3 weeks ago, # ^ |   0 Yes,right.I meet the same situation.It took my almost an hour to consider why I got TLE during contest.
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I was a little disappointed actually. there is nothing wrong in our code or our algorithms. there is even nothing wrong in STL -- STL was implemented for solving practical problems in the industry, instead of for dealing with some nitpicking testing data deliberately placing obstacles.
 » 3 weeks ago, # |   +32 E2 was beautiful.
•  » » 3 weeks ago, # ^ |   +20 I really liked how authors were lenient on time and constraints as well.
 » 3 weeks ago, # |   0 Was E1 dp or just a math formula ?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   -33 math formula
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 I used DP. But I think basically it's a math formula. $dp[1] = 6$ $dp[x] = dp[x-1] \times 4^{2^{(x-1)}}$
•  » » » 3 weeks ago, # ^ |   0 I like how I used exact same formula and get WA 7 times
•  » » » » 3 weeks ago, # ^ |   0 You have to take mod as well, as it grows at a very large speed. Also, don't forget to cast number to long long if you are using binary shift in C/C++.Here is my solution: https://codeforces.com/contest/1594/submission/131216469
•  » » » » » 3 weeks ago, # ^ |   0 Yeah I forgot to cast it and it cost me 2 WAs
•  » » » » » » 3 weeks ago, # ^ |   0 Same. Costed 2 WAs for this stupid thing.
•  » » » » » 3 weeks ago, # ^ |   0 yeah, I found out 1<<60 is too hard for c++ and it just crashes lolme on this task: ¯_(ツ)_/¯
•  » » » » » » 3 weeks ago, # ^ |   0 1 is int with 32 bits only, try to shift 1LL
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 check out my solution, no shift is neededhttps://codeforces.com/contest/1594/submission/131212167
•  » » 3 weeks ago, # ^ |   +5 It was neither. It was basically just computing $3 \cdot 2^{2^{k+1}-3} \bmod {10^9+7}$ fast.
•  » » » 3 weeks ago, # ^ |   +3 was figuring out this formula really that trivial ? ;v
•  » » » » 3 weeks ago, # ^ |   0 Kind of :) I used this formula: 6*4^(2^k — 2)Basically the same formula but used as derived from visualizing all combinations on the tree.Here is the solution: https://codeforces.com/contest/1594/submission/131216469
•  » » 3 weeks ago, # ^ |   +8 It was simple combinatorics. You can color the root in any one of the 6 colors, all the subsequent nodes can be colored in any 4 of the remaining colors. So the answer is simply 6 * 4 ^ (number of nodes — 2).
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 i solved it using a basic loopans *= 4^(2^i) where i from 2 to k then multiply the answer by 6
 » 3 weeks ago, # |   +12 D is a great problem .. :+) and Yahhhhhhhhhhhhhhhhhh specialist again :+)
 » 3 weeks ago, # |   -9 Since contest is over, plot reveal! Problem D was most likely copied from INOI 2021 P2 (I say most likely since this might be the original problem from an unknown source and both of these could be copied)
•  » » 3 weeks ago, # ^ |   +10 We did not copy the problem nor were we aware that it already existed. We are sorry for this, our only inpsiration was the game "Among us" and the rest were our ideas.
•  » » » 3 weeks ago, # ^ |   0 This could be true...
•  » » » » 3 weeks ago, # ^ |   +15 We gain nothing by using a known problem, that only hurts us. We are sorry for not knowing that a very similar problem already existed and we are just as disappointed as you are.
•  » » » » » 3 weeks ago, # ^ |   +1 No no, I actually believe you. Considering how "Among Us" works it is quite natural to see things this way.
 » 3 weeks ago, # |   +9 Great and interesting problems today. Enjoyed giving the contest.Kudos to Theo830 and Dremix10 for the great round and all the testers as well.
 » 3 weeks ago, # | ← Rev. 2 →   -88 D, a problem with 1750 points was a repeated problemE1 was also the same as a CSES problem.I knew neither. Thank you, I'll enjoy my -100 delta
•  » » 3 weeks ago, # ^ |   0 could u link this CSES problem?
•  » » » 3 weeks ago, # ^ |   0 I believe he is talking about this problemhttps://cses.fi/problemset/task/1712but it wasn't required here because k is small
•  » » 3 weeks ago, # ^ |   +3 I rage quit when I saw my "friends" solve D in 5-7 mins, and I went on scratching my head on that problem for like an hour or so, without any solutions.
•  » » 3 weeks ago, # ^ |   +19 I'm not sure about the CSES problem you're referring to. If it's https://cses.fi/problemset/task/1712, then I guess you missed the fact that $2^{60}$ can easily be stored in a long long, and you can do straightforward modular exponentation to that value. The main part was to find the formula (although short).
•  » » 3 weeks ago, # ^ |   +36 So you can only solve problem you've known before? Sound like you got the delta you deserve.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -15 No, I prefer non-repeated problems(ad-hoc if possible), as with repeated problems rankings get kinda skewed, giving an unfair advantage.Edit: Also I know the more you solve the more you have this advantage, but I think we all can agree it sucks if a problem is straight-up repeated, intentionally or unintentionally
•  » » » » 3 weeks ago, # ^ |   +10 Yeah, it was unfortunate that this situation happened. However, saying that you couldn't solve a problem because it was repeated just doesn't make any sense.
•  » » » » » 3 weeks ago, # ^ |   -8 Oh well I wasn't blaming that fact for bricking the problem, I just suck.I was blaming that fact for ruining my bad delta even further, which I think is reasonable.
•  » » » 3 weeks ago, # ^ |   0 It is not an issue, that you can't solve the problem.The issue is when 1K other people knew this problem before and were able to submit it fast. People who didn't know the problem and solved it slow or didn't solve it at all are heavily affected.
•  » » » » 3 weeks ago, # ^ |   0 It is not an issue, that you can't solve the problem. It IS an issue when you couldn't solve a problem yet still managed to complain about its originality. I was specifically replying to that comment and I didn't find myself saying that reusing a problem was okay. So what are you trying to say here, again?
•  » » » » » 2 weeks ago, # ^ | ← Rev. 3 →   +3 Complaining about the originality of the problem is a legitimate issue, no matter being able to solve it or not. You were affected in both cases by the fact that others knew it beforehand.I am also not sure, what are you trying to say. This is obvious, that there were 2 groups of people — those who knew the problem and were submitting like crazy and those who were struggling. If you found yourself in the second one, you were heavily affected. There is already tons of cheating for the original tasks. If there was a repeated task of level D, you could expect a massive amount of submissions, especially when you are not breaking any rules by reusing the existing online code. You could copy and paste the solution and you can't even be banned for this.What is also funny, is you can see (in the comments) that some people wanted to brag about solving D. They copy-paste the existing code (without understanding the idea) and then just provide the URL to their accepted solution, explaining that details are too hard to describe in English, so just read the code :)
•  » » » » » » 2 weeks ago, # ^ |   0 Ok, I think I figured out what are you saying. You claim that by the fact that you didn't solve the problem, it means that you didn't know it (not necessarily true), so you shouldn't complain about its originality (because for you it was still the original problem).I think it is just trolling as he wasn't complaining about the quality of the tasks or the problem-solving experience. He complained about the personal outcome of the whole story.
•  » » » » » » 2 weeks ago, # ^ |   +9 With respect, I think you're putting too much thoughts into this issue. Unfortunate things are sometimes bound to happen, we just have to deal with them and move on. It's an online contest after all, can you imagine how people reacted when it happened in an official competition like IOI?
 » 3 weeks ago, # |   -18 I thought how the hell so many people solved D.Looking at the comments, I'm getting why...
 » 3 weeks ago, # |   +8 Is D a graph problem?
•  » » 3 weeks ago, # ^ |   0 Yes and union find set is used to solve D
•  » » » 3 weeks ago, # ^ |   0 Can you please explain how to approach it?
•  » » » » 3 weeks ago, # ^ |   0 I tried but have found that it's quite hard to explain T_T. A hint is that if one says that someone is a crewmate, then they must be either crewmates or imposters.Thus you can use union find set to deal with the problem, at last coloring a bi-graph is needed.Elaborating the detail is far beyond me — my poor English but you can have a look at my code here
•  » » » 3 weeks ago, # ^ |   +1 Yeah but I mean D is quite easy for it's place. It is a free ~1750 points to anyone who has seen enough applications of DFS, BFS.
 » 3 weeks ago, # |   +8 Can someone explain E1?
•  » » 3 weeks ago, # ^ |   +11 It was simple combinatorics. You can color the root in any one of the 6 colors, all the subsequent nodes can be colored in any 4 of the remaining colors. So the answer is simply 6 * 4 ^ (number of nodes — 2).
•  » » » 3 weeks ago, # ^ |   0 Got bricked after not being able to solve B, thanks for the explanation!
 » 3 weeks ago, # |   +8 tks bro :3, the problems are pretty good. But E1 < C :3. I tried to solve problem C but it was not AC. Maybe give me for idea to solve problem C.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 the minimum number of operations $m$ can be only 0, 1, or 2.the upper bound is 2 because we can always choose $x_1=n$ and $x_2=n-1$ to make all characters in $s$ equal to $c$. $n-1$ can't divide $n$ since the problem guarantees $n\geq 3$if originally each character in $s$ equals $c$, $m=0$if originally $s_n = c$, $m=1$ (choose $x_1=n$)if originally $s_n \neq c$, we find the last position $p\in [1, n]$ s.t. $s_p=c$, then if $p>\lfloor {\frac{n}{2}} \rfloor$, $m=1$ (choose $x_1=p$), else $m=2$
•  » » 3 weeks ago, # ^ |   0 E1 is rated 1000 C is rated 1500E1 was supposed to be < C
 » 3 weeks ago, # |   +8 Was so close to becoming a Specialist but wasted much time on B and couldn't solve it, should have gone to E1. Nevertheless, I enjoyed the problems.
 » 3 weeks ago, # |   +8 How to solve C ?
•  » » 3 weeks ago, # ^ |   0 Its too easy :) But I was thinking about B... Didn't notice C. When I started to code it became too late :) Just think of this ; If s[n-1] ==c then obviously it is possible to replace all the remaining character with c with one go.... As N (length of string) won't divide any index then the answer will be 1 in this case ( if all the characters are already the given character then answer will be 0 ) But if s[n-1]!=c then check from n/2 to n if there is any i for which s[i]==c then the minimum steps required will be 1. And that index should be the value of x. Just take a pen and paper and think of it. But if you don't get any index i for which s[i]==c ranging from n/2 to n then obviously minimum steps required will be 2 and values of x will be n-1 and n
 » 3 weeks ago, # | ← Rev. 2 →   +52 Hmm... Isn't problem D a very old and classic problem? IMO it's not very suitable to be used in formal contests (maybe it can be used in an educational round?) Problem E2 and F are nice, thanks for the problems XD
•  » » 3 weeks ago, # ^ |   +27 We were not aware of that and are really sorry about it.We will make sure that nothing similar happens again.Thank you for your kind words, we tried our best and are glad you liked them!
 » 3 weeks ago, # |   +8 Math riddles that i failed miserably.
 » 3 weeks ago, # |   +18 Problems A-E1 were more boring than usual, but E2 was nice. Sadly I finished E2 just after round was over :pensive:.
•  » » 3 weeks ago, # ^ |   0 Same :pensiveclownwobble:
 » 3 weeks ago, # |   +8 any one could help explain the method used to solve problem B ?, thanks in advance .
•  » » 3 weeks ago, # ^ |   +1 Consider the number base n. Each good number is a number that has all digits equal to 0 or 1 in base n. Well, to find the kth of those, realize you can generate all numbers with only 0 or 1 value digits by just counting in base 2 and looking at binary representation, since binary is different masks of 0 and 1. This means you can just look at the number k in binary, and for each 1 in the binary corresponding to 2^x, you add to the result n^x.
•  » » 3 weeks ago, # ^ |   0 u must convert k to a bit mask firstly for example k = 4 , so k = 1 0 0and loop on every index, if the bit number i is a set, add pow(n , i) to the result
 » 3 weeks ago, # |   +11 A, B and C are quite creative problems!but I think D is quite a classic problem E1 is a simple combinatorics but I can't solve E2 and F T_T
 » 3 weeks ago, # |   0 The problems were good.
 » 3 weeks ago, # | ← Rev. 2 →   -9 Link to codechef version of D Only minor changes
 » 3 weeks ago, # |   0 Good contest !
 » 3 weeks ago, # |   +5 Almost solved problem B but C looked easier than B to me. But I was too late to notice it. As soon as I coded C the contest already came to an end .... :) May be missed a chance for increasing rating :)
 » 3 weeks ago, # |   -8 In c problem ,I was trying to find the nearest prime number<=n and then if the character at that position matches the given character c , then answer would be 1 , the number would be that prime number , else the answer would be 2 as one to change the character at the prime number position and the other for rest of characters in string. My this approaching is failing on same cases which I am not able to figure out, can anyone please help me by providing such case. code:-https://codeforces.com/contest/1594/submission/131209103Thanks in advance.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I was also doing the same but turns out that's not required and neither correct, u just need to check for i from (n/2 + 1) to n if there is any character equals to c then ans {i} otherwise m has to be atleast 2 and that can be done using {n,n-1}
•  » » 3 weeks ago, # ^ |   0 7 a abbbbab you can choose x = 6
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +1 The optimal index is not necessarily prime.. Any index i such that for j in 1 to N, if j is divisible by i, then s[i] is equal to C will give an answer of 1. If such an index does not exist, simply use the last 2 indices, and ans will be 2. Can be brute forced ( NlogN )
•  » » 3 weeks ago, # ^ |   0 one counterexample is:7 aaabbbabin this case you should choose $x=6$, which is not a prime
 » 3 weeks ago, # |   0 This was a great contest!The questions are quite unique with division-2 difficulty.The solutions are also very diverse ඞ.I also recorded a video during the contest that talks about solving problems A~E1 with explanations.Please watch it if you are interested.
 » 3 weeks ago, # |   0 In the problem D, I have used the following approach, for every node I first I assume the node to be a imposter and then do a dfs and then count the number of imposters found in this scenario. Then I assume the node to be a crewmate and then do a dfs and count the number of imposters. I set the value of the visited nodes to be corresponding to the case in which maximum imposters were found( i.e. whether on assuming the node to be imposter or assuming it to be crewmate). Can someone tell me where am I going wrong. Submission: 131237230
•  » » 3 weeks ago, # ^ |   0 I am not sure, but from the judge, there is a wrong answer on the case: 3 2 1 3 imposter 2 3 crewmate where you should print "2" instead of "1".
•  » » » 3 weeks ago, # ^ |   0 Thanx
 » 3 weeks ago, # |   0 Thanks for the contest,I think making n as 100000 would have been better for E1 considering it's position My solution will work n = 100000 too https://codeforces.com/contest/1594/submission/131200149
 » 3 weeks ago, # |   +32 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 One of my solutions still shows pretest passed after system testing. On resubmitting the solution after system tests it is accepted. link is attached belowSolution : My solution Link to blog : Blog entry
•  » » 3 weeks ago, # ^ |   0 Please try to do this every time unless really not feasible... coz it helps us in ways.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Hi Mike, can you help me with this? my submission on problem B was considered plagiarism, but our submissions coincided just because the solution to pB is quite simple, and contains only one simple bit manipulation procedure.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 -1
 » 3 weeks ago, # |   +9 I think author have some love with long long and % 1000000007 (::)
•  » » 3 weeks ago, # ^ |   0 This is actually true about long long xD
 » 3 weeks ago, # |   0 Can anyone tell what's wrong with my submission ? 131208294I am simply making the crewmates into a single node and then use bfs to find if the graph is bipartite and the biggest bipartite possible. I can't see the full test case so I can't test. It seems that I am printing some extra -1 's.
 » 3 weeks ago, # |   0 MikeMirzayanov My submission for problem C passed the pretests but even after the system testing it's neither showing wrong answer nor accepted..instead it's still pretests passed...While submitting the exact same solution after the contest was over got accepted.Please look into the problem and update my rating accordingly.
•  » » 3 weeks ago, # ^ |   0 Strange verdict was fixed. Rating will be updated in some time.
•  » » » 3 weeks ago, # ^ |   0 My rating didn't change :(
•  » » » 3 weeks ago, # ^ |   +3 :( still same
•  » » » 2 weeks ago, # ^ |   0 I faced a similar issue please update my rating also!!
 » 3 weeks ago, # |   0 Just a doubt The answer for this test case in problem 'C' is not '6 5'. Why? ----TEST CASE------ 1 6 v fxblgs ------------------- After choosing x=6 s becomes vvvvvs and choosing x=5 s becomes vvvvvv but the answer is wrong. But why?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 It is correct bro.
•  » » 3 weeks ago, # ^ |   0 Why do you think that it's wrong?
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 By mistake
 » 3 weeks ago, # |   0 Can somebody help me with C ! I thinking like this if I check the last character is equal to the given character or not , if it is than we will choose n as x since n won't divide any number from 1 to n-1, and if last character or the string is not same x than there would 2 operations n and any prime number less n ? I don't know why this approach is not working? Any help is sincerely appreciated since I'm a newbie and if I sound dumb please pardon me ! :(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 In some cases it is possible to convert the string using only one operation even if the last character of the string is not x. For Example: Spoiler4 a acaa SpoilerYou can choose the third character (1 based indexing)
•  » » 3 weeks ago, # ^ |   0 Spoiler4 c ccdcd here, last character is not equal to given character c, and to get 1 operation, you can chose x=2, since the unequal characters are at 3 and 5.also, why prime less than n? a prime can still have multiples that are at postion in string where character in string!=character given, but you still need to change that character in string, but it can't be done since it is a multiple of n.
 » 3 weeks ago, # |   0 alternative DSU based solution for problem D. https://codeforces.com/contest/1594/submission/131244090
•  » » 2 weeks ago, # ^ |   0 Can you explain your approach?
 » 3 weeks ago, # |   0 My submission for D passed the pretests but got TLE on the system judge. However, resubmitting the exact same code after the contest gets AC. Is this normal or a glitch? code: https://codeforces.com/contest/1594/submission/131212208 PS. Thank you for the contest.
 » 3 weeks ago, # |   +22 Is it just me or does anybody realise that problem B has a rick roll in it? (Yeltsa Kcir is Rick Astley reversed) XD
•  » » 3 weeks ago, # ^ |   0 Are you saying he's not related to Boris Yeltsin?
 » 3 weeks ago, # |   +3 The Contest was entertaining. I enjoyed the whole 2hr 15 min.Thank You :)
 » 2 weeks ago, # |   -8 Regarding this message i got from codeforces- "Attention!Your solution 131199954 for the problem 1594C significantly coincides with solutions CrocHold/131199954, contestiscontest/131199998, checker_1234/131200079, tourist___________1/131200332, tu-rex/131200598, testcase321/131200841, nas.2.op/131203694, susamogusbob/131204347. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."The comment that i'm supposed to post here- The solution is ridiculously obvious to figure out, kindly undo and remove any related penalties levied on this account. Finding numbers that have only 1 multiple in the range is super obvious. The largest ones. that's all i have to say in my defense ...peace!
 » 11 days ago, # |   0 I just realized that "Yeltsa Kcir" is Rick Astley backwards....I have been unknowingly Rick Rolled, screw me
 » 25 hours ago, # |   0 It would be nice to have only positive rating changes in codeforces for all level coders, so people doesn't bother to stop coding if they are so much rating phobic.