Γεια σου (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:
adedalic for amazing coordination of this round.
Dremix10 for giving the first feedback about every problem I created.
Markadiusz, cfalas, wxhtzdy, ijxjdjd, YouKn0wWho, PurpleCrayon, flamestorm, Shinchan01, rgnerdplayer, awoo, Hyperbolic, Nots0fast, UnstoppableChillMachine for testing the problems and providing useful feedback.
MikeMirzayanov for Codeforces and Polygon platforms.
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:
UPD3:
Div2:
Div1 + 2:
Hoping for a good contest :)
will see :):
A good one for me , i have done 4 problems :)
nvm, added in the blog.
Usual — 150 min
And also notice the unusual duration of this contest (usual time + 15min)
Ahh Thank you so much YPK.
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.
As a tester, I found problems are new and clear.
UPD: Problem D found copied. I take my words back.
How do you know they are new? Have you checked all the problems that have ever been published?
Not very new after all.
Exact same problem as D
None of the testers found it while testing :(
I won't believe your words anymore
As a tester, I hope you will enjoy the problems as much as I did :)
As a Participant I'll tell my feedback after the contest!
Till then, your feedback wouldn't be much useful, I think.
As a tester, enjoy!
Roses are red
Energy is produced by nuclear fusion
The contest is great
As a tester, I want contribution
Well, let's hope all the problem statements are not quatrains like this one.
does one subtask means that one problem will be divided to easy and hard versions ?
That's right.
I wish this round will be my last round in grey :)
Your graph indicates that you're a hard-worker. I wish you the best of luck.
Thanks bro you made my day :)
I wish this round will be my last round in Green :)
I wish this round will be my last round of Cyan ;)
Same
Will probably get of of grey.
I will be impatiently waiting for the start of the round!
As a first feedback giver, I can say that Theo830 worked really hard to make an interesting and enjoyable round for you guys!
Why is it such a strange time
Hello everyone! Good luck to everyone on the contest!)
Hoping for a good contest.
))
I don't like subtask.
Meanwhile problem-setters:
I hope it will be my last contest in grey ^_\, wish me luck.
Bhest aaf lack
Are you planning to retire after this round? XD
18:05 in blog is just Moscow time right?
Fixed, thanks for pointing out.
WoHOOOO, contest after a long time!
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". :)
Why are all of your memes light-hearted?
not true
What do you mean by first Cypriot round ?
Both setters are from Cyprus. And as they mentioned, this is the first ever fully Cypriot round.
Hope the long queue will be ended before the contest...
Best of luck to everyone!!!
Moving on from Green tonight...
system is testing so slow :( hope it won't cause unrated round
May be it will be postponed
No it's not? The system testing is excellent in terms of speed.
This is so weird. I couldn't be able to solve any problems of the past 3 contest =(
That's because of your bad profile picture.
I AM NOT ABLE TO SUBMIT IT SAYS AM NOT REGISTERED
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!
Three lessons I've learned today:
4) don't tell spoilers.
speedforces. D was nice though.
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.
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 ^_^
How to solve C?
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.
1 2or1 3depending on wether n is odd or even.1 N.2 N 2or2 N 3(if N is odd then2 N 2, else2 N 3).This failed on pretest 2. Can you explain whats wrong with this? Unable to view pretest 2 right now.
N can be divisible by both 2 and 3 :)
so for example
6 a baabbb
Here is my solution. https://mirror.codeforces.com/contest/1594/submission/131189048
If 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!
8 a aaaaabab
You say the result is 2 3 but its actually 7
Problem D: https://www.codechef.com/INOIPRAC/problems/AMONGUS2
sus (pun intended)
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.
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.
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".
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.
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.
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.
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.
No worries, it happens :) I enjoyed solving the problems and I think the contest is very good!
Choose better testers next time. :(
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.
the suckers can suck, it was a great problem set that was amusing and fun to solve, to say the least.
Ironic how Problem D is an imposter. I had authored and created the same problem a while ago on codechef for INOI haha :3
Problem D is same as INOI 2021 Among Us
What was the intended solution? I was trying DSU's. I had the idea, but couldn't come up with an implementation.
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.
I think a variation of bipartite color assignment could also work.
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.
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.
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 :)
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.
Yes,right.I meet the same situation.It took my almost an hour to consider why I got TLE during contest.
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.
E2 was beautiful.
I really liked how authors were lenient on time and constraints as well.
Was E1 dp or just a math formula ?
I used DP. But I think basically it's a math formula.
I like how I used exact same formula and get WA 7 times
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://mirror.codeforces.com/contest/1594/submission/131216469
Yeah I forgot to cast it and it cost me 2 WAs
Same. Costed 2 WAs for this stupid thing.
yeah, I found out 1<<60 is too hard for c++ and it just crashes lol
https://mirror.codeforces.com/contest/1594/submission/131233276 vs https://mirror.codeforces.com/contest/1594/submission/131232996
me on this task: ¯_(ツ)_/¯
1 is int with 32 bits only, try to shift 1LL
check out my solution, no shift is needed
https://mirror.codeforces.com/contest/1594/submission/131212167
It was neither. It was basically just computing $$$3 \cdot 2^{2^{k+1}-3} \bmod {10^9+7}$$$ fast.
was figuring out this formula really that trivial ? ;v
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://mirror.codeforces.com/contest/1594/submission/131216469
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).
i solved it using a basic loop
ans *= 4^(2^i) where i from 2 to k then multiply the answer by 6
D is a great problem .. :+) and Yahhhhhhhhhhhhhhhhhh specialist again :+)
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)
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.
This could be true...
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.
No no, I actually believe you. Considering how "Among Us" works it is quite natural to see things this way.
Great and interesting problems today. Enjoyed giving the contest.Kudos to Theo830 and Dremix10 for the great round and all the testers as well.
D, a problem with 1750 points was a repeated problem
E1 was also the same as a CSES problem.
I knew neither. Thank you, I'll enjoy my -100 delta
could u link this CSES problem?
I believe he is talking about this problem
https://cses.fi/problemset/task/1712
but it wasn't required here because k is small
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.
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).
So you can only solve problem you've known before? Sound like you got the delta you deserve.
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
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.
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.
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.
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?
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 :)
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.
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?
I thought how the hell so many people solved D.
Looking at the comments, I'm getting why...
Is D a graph problem?
Yes and union find set is used to solve D
Can you please explain how to approach it?
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
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.
Can someone explain E1?
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).
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.
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 \gt \lfloor {\frac{n}{2}} \rfloor$$$, $$$m=1$$$ (choose $$$x_1=p$$$), else $$$m=2$$$
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.
How to solve C ?
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
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!
Math riddles that i failed miserably.
Problems A-E1 were more boring than usual, but E2 was nice. Sadly I finished E2 just after round was over :pensive:.
Same :pensiveclownwobble:
any one could help explain the method used to solve problem B ?, thanks in advance .
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.
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
Good contest !
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 :)
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://mirror.codeforces.com/contest/1594/submission/131209103
Thanks in advance.
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}
7 a abbbbab you can choose x = 6
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 )
one counterexample is:
7 a
aabbbab
in this case you should choose $$$x=6$$$, which is not a prime
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.
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
I am not sure, but from the judge, there is a wrong answer on the case:
where you should print "2" instead of "1".
Thanx
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://mirror.codeforces.com/contest/1594/submission/131200149
To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
One of my solutions still shows pretest passed after system testing. On resubmitting the solution after system tests it is accepted. link is attached below
Solution : My solution
Link to blog : Blog entry
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.
I think author have some love with long long and % 1000000007 (::)
This is actually true about long long xD
Can anyone tell what's wrong with my submission ? 131208294
I 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.
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.
Strange verdict was fixed. Rating will be updated in some time.
:( still same
I faced a similar issue please update my rating also!!
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?
Why do you think that it's wrong?
By mistake
alternative DSU based solution for problem D. https://mirror.codeforces.com/contest/1594/submission/131244090
Can you explain your approach?
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://mirror.codeforces.com/contest/1594/submission/131212208
PS. Thank you for the contest.
Is it just me or does anybody realise that problem B has a rick roll in it? (Yeltsa Kcir is Rick Astley reversed) XD
The Contest was entertaining. I enjoyed the whole 2hr 15 min.
Thank You :)
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://mirror.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!