Hello Codeforces!
mesanu and I are very glad to invite you to Codeforces Round 726 (Div. 2) which will take place on 18.06.2021 17:35 (Московское время). The round will be rated for participants with a rating lower than 2100. Division 1 participants are also welcomed to take part in the competition but it will be unrated for them.
The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.
You will be given 6 problems and 2 hours to solve them.
We would like to thank the following people:
1-gon for amazing coordination of our round!
antontrygubO_o for testing, translating statements and providing useful ideas!
Maksim1744, Ari, qpwoeirut, magnus.hegdahl, PurpleCrayon, Brodicico, Omkar, DenjellBoone, Arsenie, Lost_Arrow, Etherite, asrinivasan007, nishuz, cringeworthyplayz, Nika_Tamliani, Vpurice for testing and providing invaluable feedback!
- MikeMirzayanov for great Codeforces and Polygon platforms!
You, for participating!
The scoring distribution is: 500 — 750 — 1000 — 1500 — (1250+1750) — 2000.
UPD: Editorial
As a coordinator...
omg orz! monogon taking over cf!
Eventually I will fire Mike so I can be the real top contributor. (Don't tell him I said that)
monogonforces orz
As a follower of Monogon, I am obligated to upvote this comment.
At this rate, that day isn't far when...
In the future, if you're gonna need an icon just contact me. I'll do it for
freejust a few upvotes.Should I resume share or okay this?
Also,
ORZ 1-gonforces
Congrats for the successful steal of Anton's Job.
whatever man just take my upvote :/
in this contest i had solved problem A in first 8 mins and i was checking for the results and it was showing "in queue" so i thought to submit it on m1.codeforces so that it get tested fast but now i have seen that both of my solution got passed but the system have rewarded me the marks for the second one which i have submitted 2mins after and also it has given me -50 . can you plzz say something or do something on this plzzzz first time in 6 months i was able to solve 4 prblms in div 2
According to the official rules, only the last submission with pretests passed is considered for system testing. When your submission was in queue you should've just waited and moved on to read the other problems.
As a tester, I tested.
Just take my upvote
Yea we can see your name in tester's list,why say it again?
Yes, but how do you know what he did as a tester?
You must have tested problems. Right?
``oz
Well tested!! Strong tests were included in system tests.
I had the same fate, my friend. just changing s to s+s corrected it
newbie sens
As a participant, I hope to become purple in this round. Wish me luck !
All the best, as a participant I hope to get my confidence back
As a guy , I just want to be happy
I dont want to be hor*y anymore. I just want to be happy.
Good Luck! I hope you become purple after this round but I sincerely hope that it's not coming at my ratings' expense.
Seems the opposite happened lol, you got rating at my ratings' expense :O. Anyways, good show.
As a tester, i'm proud of these guys.
Just take my upvote
Probably copying previous comments does not help. People who plan on doing this can probably take note. Hehe
5 months later, I'm still annoyed that you didn't take kostia244's suggestions for your new handle :(
:(
The biggest scam of 2021
I_Love_SlavicG
When the author gets lesser upvotes than the setters.
Did all the testers downvote this? I guess it doesn't matter since Monogon will soon rule Codeforces.
As a tester, SlavicG ORZ
inspirational
It really motivated me SlavicG
what about
tenkei
RunTimeTerror Motivation overflow
tenkei retired
He already gave us so much motivation and showed us everything is possible if we try honestly and embrace hard work. Hope he enjoy his retirement. We will miss him. Orz.
Score distribution suggests that the contest is All-Killable
So blues are writing div2s now? whats next? greendians writing div1?
Chup chapri. Dont write these useless messages.
keyboard_warrior Another bluedian defending your blue buddies? Hope even you get to write a contest next.
(edit: fixed some grammar mistakes)
What about purples/blues(not me) who have really good problem ideas and not able to propose a contest because of the rating barrier and end up in submitting them in less kown websites or just moving on with dissatisfaction.
make unofficial round.
I have a dream, that one day authors may be judged by the quality of their problems, rather than the color of their handle.
As a tester, I can say that the problems are nice, and I recommend participating :D
THIS IS SPARTAAAAA
Well, if you look at their number of solved problems you can easily say they solved enough problems to make their own problems. Also some red coders tested/coordinated it so there is no reason to not make a round. And those "greendians" are better than an unrated person with -53 contribution.
mad?
And what is your rating, mister alt user?
As a tester, I couldn't help much with review of problems except in the initial div3 phase. The round is well balanced and may positive delta come your way :blobheart:
All the best to all the participants,
may there be a positive delta... The scoring distribution is quite interesting.
Moldova power!
As a tester, I highly advise you to read all the problems!
I often see this comment whenever we have a problem which is divided into two( easy & hard) versions . Let me guess E1 is a bit easy than D :) and one more thing we have to do a bit more reading :)
I got it right , E1 was easier than D :)
Don't they all suggest the same thing. I think the trick to acing the contest might be to not read all the problems and not get depressed to try the problems.
These rules changed?
I guess they can be count as a writer in the past because they made 2 unoffical div 4 contests and those rounds had a good amount of participants.
No disrespect, but they are a bunch of some easy problems. So how do they count?
they said this meant to be a div3 round,so those problems were enough to give them a chance to write a round.
To reds, a Div. 2 is a bunch of easy problems. To oranges, a Div. 3 is a bunch of easy problems. So how do they count?
Honestly, I think the current rules were just a way to limit the amount of contest proposals without disenfranchising anybody. So if you were lucky enough to get something in before the new requirements, then you basically get grandfathered in.
Div 2 is not rated for oranges and above. Div 3 is not rated for blues and above. But this round is rated til 2100.
And since it was reviewed, coordinated, and tested by a bunch of people high rated, it should be reason enough to believe that the contest will have good enough problems for it to be rated for participants with rating upto 2100.
Probably, still I'm also somewhat dubious about the ability of people to come up with the problem and solution ~500-1000 points above their own rating, and the hardest problem of the round should be at least that difficult
No offence, it's just peculiar
Rating doesn't measure your overall problem solving skills.
A more accurate explanation is probably that it is quite possible to make a problem that is 1000 points above your rating by making a problem from the solution, instead of actually solving a problem you came up with. And, even for problems that you came up with, you have a lot more time to try to solve them than when in a contest, and you also probably have more chances to solve a hard problem(the participants can't notice all of the hard problems that you didn't solve when problemsetting).
Btw, all rounds have coordinators, but not all of them are equally good, so it doesn't really mean anything, just saying
Well, I didn't want to drag this on, but let's do it.
What is a good round / contest? one where you can solve 3 or 4 problems? you feel good after the contest, that maybe you solved every problem that you read during contest? Sorry to disappoint you that not every round can be good for you.
Tbh, have you ever even thought about what it takes to prepare a round, or the effort put in by coordinators / testers. All you see is the "Codeforces Round #XYZ" blog on CF. Although, I have never authored a round myself, I want to make problems for a while, but I can't even think about them. Forget about preparation of statements, constraints, test cases, and many other things that I might not even know about right now. Even though some rounds are not well recieved by contestants, it doesn't trash all the effort that was put into it, nor does it mean that problems are shit. Hell,the problems were accepted by anton, and even as a joke, it is popularly known how high a bar he has set.
Nah
Rly, do not assume that the other person is stupid. Whether my performance is good or bad has nothing to do with the round being good or bad. Say, LATOKEN round was quite good even though I got -50
Model good round is a round with good problems, balanced problems, diversed topics, good problem statements and good editorials. Also without long queues and other technical issues but that is out of control of coordinators.
It's all nice and everything. Yet again, some rounds are better than the others despite all the hard work of the authors you mentioned
Have you realized that the first 5 requirements you stated are completely subjective? Sorry, this website doesn't cater to each and every one of your individual needs. The round is good, it was tested by a wide variety of colours, it was coordinated by reds and approved by Mike, I'm not sure what else you could ask for.
Well put, I couldn't have said it better.
They're not so much subjective as you're trying to make it sound
Say if the statement is long and confusing for a lot of people, it is a bad statement and there is little subjective about it
If one problem has difficulty 1000 and the next one is 2200, it is unbalanced round
Etc
Also I don't quite understand what you're arguing about, Do you disagree that some rounds are better than the others? Because that is pretty much the sole point of my messages here
As the round has neither started nor you are a tester, then how can you say anything about a round when you literally don't know anything about the round
I don't know if you read the testing part, but the round has testers from almost every color from pupil to LGM.
So, it would be better if u shut up now and give your opinions after the round has ended.
There is a comments section in editorial also
Lets just end this thread by a well known standard result : Quality of contest depends on your rank in that contest
QED
What actually happened was some combination of Mike liking the problems but not thinking it was Div 3, and having Anton and Monogon coordinate.
They wrote an unofficial div4 contest on gym before, so it isn't a violation of the rules really. They had experience in problemsetting and messaged me (who started coordinating after that blog) about it, as it says in the last paragraph.
As a tester, I can certify this is a great round with interesting and clear problems. Best of luck to all who are participating!
Both the problemsetters have a highest rating of expert. So how did they propose this round, as you have to be a master to write one?
You can suggest problems if you are an expert. I don't know if it's any different than proposing contests.
As a participant I hope to get past C this round
I wish I could be expert. People how to get expert batch within a short time? Is it their outcome of lot of practice, How can I get expert batch? Please suggest me. (Sorry for unnecessary comment. But I need to know to develop my problem solving skill)
Literally just solve questions that are challenging enough, so basically problems that are rated +200 ish from ur current rating and try to understand and apply new concepts u encounter from editorials n blogs then u should be set.
I didn't knew that Blues can also host contest at codeforces.
Blue power exists. :)
are the problem statement short mainly first 2 as i am unable to do after that in last rounds hope that i will be able to solve a,b,c this time.
As a tester I think that reading all problems in 2 hours is very well doable.
So we can assume there can not be much more than 1000 words in each statement. Very reassuring
Yeah but tbh I've never found a contest where I wasn't able to read all problems. Reading them is not taking a large amount of time compared to solving them, regardless of the number of words
If Monogon can write a good 3500, which is 900 higher than his rating, then can't SlavicG write a good 2600?
2600 is the upper end of div2 difficulty. I think this will be an excellent round!
I have no idea who Zoroland_ is, and how he/she copied my code for A,B,C problems. It maybe because i used idone in public settings during this contest. I will stop using idone at all after this.
Motivational speech: The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.
In other words, if you perform badly then you're even worse than you thought.
Might be another speedforces coming up!!
Ah I see, the tables have turned now!
Thanks, and I hope the statement will be short and clear.
omg finally ssense ans slavic round, cant wait to participate!
Hope to solve problem C this time.
I wish I was never born
Ban radewoosh,he is racist.
OMG! What happen to Radewoosh?
Anyone noticed that when you move your cursor to testers' handles, you can see text "Tester" or "orz Tester"?
I see 1-gon >> yoyo master.
This is how it works-
<a class="rated-user user-red" href="/profile/1-gon" title="monogorz">1-gon</a>
and without actually tagging the person-
<a href="https://mirror.codeforces.com/profile/1-gon" title="master yoyo yoyo master master monogon monogon master 1-gon orz orz orz testing feature orz" style = "color:red; font-weight:700;">monogon</a>
Result: monogon
I hope 1-gon didn't recieve a notification for this.I didn't get a notification
Thanks! You never disappoint me, my lord. And you are fast.
As a commenter , I wish +2 :) SlavicG
I'm also in desperate need of +2
I think 1-gon is gonna takeover codeforces completely !
This is gonna be my first contest. Wish me luck guys :)
All the best bro! Mistakenly I downvoted your comment so the best I could do is wish you luck!!
As a participant, "As a + something" jokes are not funny anymore...
That's not true. "Anymore" implies there was a time when they were funny.
So you're testing if they will keep upvoting those I guess
I want to be a tester. But I don't know any of the problem setters, and I don't just want to be friends for benefits just to become a tester. Is there any hope?
Score distribution says the total score of E is 3000, whereas the score of F is 2000. Does this mean E2 is harder than F? Interesting.
Not necessarily, it could also mean that the 2 subtasks of E aren't related, like 1092D1 - Великая Вовина Стена (Версия 1) and 1092D2 - Великая Вовина Стена (Версия 2)
Oh, that makes sence.
The day is not far when MikeMirzayanov will sit and rest and 1-gon and other GMs and LGMs will take over Codeforces ...
The person wrote this notice got lots of contribution :)
when you give monogon contribution, he repays you with contribution as well
I hope that all those who work hard will get good rating
SlavicG Guys just have a look at his profile .... Respect ++ man :)
also the cool profile pic !
.
Im so proud of you guys for making this round !!! Way to hyped for tomorrow :yayy:
It's coinciding with WTC Finals ToT
Did cf change their rule? I thought yellow was necessary to set problems!
I think either D or E is going to be an interesting game problem.
Well done myself!!
Anyone here who wants to get a prediction of their future cf rating?? ASk me!! (or better, I should write a blog abt it :D)
What about mine
Around 1450 after this contest and then you're gonna reach expert in a month or so.
Can you please predict my future?
:D
thanks for div3)
I am curious to know 'who invented orz ?' tag that person :o
Answer: orz's parents.
And if you want to know about them just ask orz. Maybe he'll ask them to join codeforces (just like SecondThread asked his mom) and then you can tag them. ✌️
answer is better than expected :p
Hello! I would like to propose the next Div. 1 please. I know I am unrated and have not given any contests but please do not judge me by my rating (or the lack of it lol) and give me a chance to write problems for an official contest. Thank you.
Tagging Monogon for better reach.
You should either get the required rating to propose it, or demonstrate that you have sufficient problemsetting experience.
expecting my first codeforces contest!
i hope i can solve atlest 1 problem todaY all right i solved a and almost b.thank you for this contest author.boosted my confidence
Hi All, My rating is 1309, Am I not allowed to appear in this contest.
no
Long Queue?
Queueforces :(
I have submitted problem A 4 minutes ago.It's still in queue..
waiting for my submissions to deque :)
In problem A is each appended number also limited by $$$10^4$$$ or any non-negative numbers are okay?
In Problem B, can Anton entre the same room twice?
(According to the Visualization, he can't, but the problem didn't say it.)
@SlavicG
There is ask a question section where all problems are shown...Ask there
wa2forces...
I think this round should be unrated.
The reasons:
queue forces.
F is similar problem ,it was solved 200+! (include Low level players (like me).).
lol what
The same problem should be banned from such kind of contest!Strongly support this proposal.
actually it should be the other way around
How? Its pretty intuitive that the optimal string you use in E is going to be a repetition of prefixes, so just try all of them, felt as easy as A-C at least in my opinion.
D is to realize the "good" and "bad" states — if you just throw out some prime factorizations on paper you'll realize that as long as you have an even power of 2, or at least 1 "2" and another number, it's a good state and Alice wins. (if i get fst, rip)
Else bob.
Anyways for E, im bad at cpp so I used java and had a bunch of stupid bugs
Finally, I think C is the hardest problems :P
Yes, and I brute first 1000 values of D and solved it the same way. But it actually took time to do that. At least for me E1 felt far more obvious.
C would actually be tricky if they didn't give away both the cases in the samples lol. In terms of difficulty I'd say:
B < A < C < E1 < D < E2 < F
geniosity orz, thinks B is easier than A
My solution to B was just printing "1 1 n m", sure it took me a tad bit longer than A, but even I found it easier :P
How did you solve E2 , can you just give a basic idea
I gave the rough idea in this comment
Can u please explain how u even brute forced D,I tried but i couldn't.
Let's call a position good if the played playing at that position win.
dp[i]=1 // if position i is good base case dp[0]=dp[1]=dp[2]=dp[3]=0; because if some player lands into these positions he, don't have any divisor to subtract.
now, loop for all i's in the range 4 to 1000
suppose currently i=12. check for all divisors of i which we can subtract and the new number we get after subtracting is:
new_no = i-divisor_that_we_subtracted.
These new numbers that we get after subtracting are the position we can send the other player to. if any of the new positions is bad, we will send the other player to that position and he will lose. So, dp[i]=1 if any of dp[i-divisor(i)]=0;
now to check for any n in range 1-1000
if dp[n]=1 // alice wins
else bob wins because alice is starting the game
how did you brute force 1000 values? logic?
refer this
Thank you
I still don't know how you're supposed to reach the solution of D, I just brute forced for small values and observed the general and edge case (and then proceeded to submit only the edge case, not the general one and get confused when it got WA)
I think the general idea is: plot out some initial values, make a conjecture, then try to prove your conjecture.
Conjecture: For any $$$n \gt 0$$$, the first player has a winning move iff $$$n$$$ is even and not an odd power of 2.
Proof by strong induction. The base case $$$n = 1$$$ is obvious. For the inductive step, let $$$n \gt 1$$$ and suppose the claim holds for all $$$m \lt n$$$. We can show the claim is true for $$$n$$$ by case analysis:
Case 1: $$$n$$$ is an odd prime. Then there are no moves and the claim holds.
Case 2: $$$n$$$ is an odd composite. In this case all divisors of $$$n$$$ are odd. Suppose the player plays some divisor $$$a$$$, and let $$$b = n / a$$$. Then the new value is $$$m = n - a = a \cdot (b-1)$$$. Since $$$a$$$ and $$$b$$$ are odd, $$$m$$$ is even but not a power of 2, so by our inductive hypothesis $$$m$$$ is a winning value. So $$$n$$$ has no winning move and the claim holds.
Case 3: $$$n$$$ is an even number, but not a power of 2. Then $$$n$$$ has an odd proper divisor $$$a$$$. Let $$$b = n / a$$$ Then $$$b$$$ must be even so $$$m = n - a = a \cdot (b-1)$$$ is odd, and by our inductive hypothesis a losing value. So $$$a$$$ is a winning move for $$$n$$$ and the claim holds.
Case 4: $$$n = 2$$$. $$$n$$$ is an odd power of 2$ and there are no moves, so the claim holds.
Case 5: $$$n = 2^k$$$ for some $$$k \gt 1$$$. Then any valid move is of the form $$$a = 2^i$$$ for some $$$1 \le i \lt k$$$. Let $$$j = k - i$$$ and let $$$b = n / a = 2^j$$$.
If $$$j = 1$$$ then $$$m = n - a = 2^{k-1}$$$, which by our inductive hypothesis is a losing value when $$$k-1$$$ is odd.
If $$$j \gt 1$$$ then $$$m = n - a = a \cdot (b-1)$$$ is even, but not a power of 2, so by our inductive hypothesis this is a winning value and $$$a$$$ is a losing move.
So when $$$n$$$ is an even power of 2 then $$$a = 2^{k-1}$$$ is a winning move, otherwise there is no winning move, and the claim holds. This completes the induction.
That's obvious coz
D:1500andE1:1250i was solving e1 and e2 for an hour)
lot's of FST's coming :(
Weak pretest in E1 — my AC code fails on n=8,k=8 [dcdadcdb]
FST coming :(
What is the answer of this test case?
dcdadcdaCan you explain, how?
Remove the last 4 characters (
dcdb) using operation 1 four times. Concat the rest of the string (dcda) twice using operation 2.Yeah, my bad! I am getting
dcdadcdaWhat's the logic for D? I just observed the pattern from a brute-force solution and got an AC without any logic.
Due to induction. For numbers > 9 and not power of 2, you can see that it if it's even then Alice will win else bob. If even number has odd factor, then we can subtract odd factor from it and resultant number will be odd and use answer of previous numbers.
rananjay23 Can you explain a little bit more the logic of D?
I started writing down numbers from 1 to 21 and found following : Bob wins for 1,2,3,5,7,8,9,11,13,15,17,19,21 Alice wins for 4,6,10,12,14,16,18,20
For even n, if it's not power of 2, then there is some odd divisor say o>1. Hence n-o is odd and we know result of it . Example : n=22, then 22-11=11 and we know who wins if n is odd and less than 21.
Similar reason you can find for odd numbers > 21.
For even numbers with power of 2, It's always alternate i.e for 8 bob will win, for 16 Alice, for 32 Bob. Here also explain (just subtract divisors and see) in similar way.
I wrote out a proof here: https://mirror.codeforces.com/blog/entry/91835?#comment-805791
The pretests for E1 are trash!
F is a easy version of https://www.luogu.com.cn/problem/P6185
Line graph version of F also appeared very recently in https://atcoder.jp/contests/arc119/tasks/arc119_c
I feel like the operation of adding x to two adjacent cells also appeared on many other CF problems before. They are almost always solved by two coloring.
Nice Round. Thanks for this :)
Not good for me. Solved E1 after 4 WA's just because of min/max string silly mistake. Rank dropped from 500 in first half to 1400 till end. And left with no time to try E2
Moral:- Don't submit again and again by changing small part just erase whole solution do that again. Hopefully that silly mistake will be resolved.
B failed in system testing..
Reason — 1 "=" sign
My bad
The problems are cute, but don't you think this is closer to Div2.5 than Div2? My first full solve of a Div2 and its around what I would have got for a fairly fast n — 1 problems in a Div2 normally.
Yess, the authors have mentioned in the above blog:
The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.
which is probably why it felt easier than the rest :)
Found the OEIS sequence for D in the last 3 minutes. Completed my code 10 seconds after the contest got over due to a stupid mistake.
Now I feel sad.
Wait same, but I got when $$$\omega(n)^{\phi(n)} \equiv 1 \pmod{n}$$$, which is apparantally wrong.
I got this one
OEIS
That one doesn't seem to be the answer though. I'm not sure but I get that the answer is
Odd -> Bob win
Even we have two cases
2^k with odd k -> Bob win
Otherwise -> Alice win
This passes the pretest but I need to wait for the system test for confirmation.
Odd -> Bob win?
What about n=9? (Given as an example in the problem). Also, 25. Or are those just a special cases?
n = 9 is not in the example.
Also, check this! https://mirror.codeforces.com/blog/entry/91835?#comment-805566
whoops... guess my brute forcer was borked.
n=9 was in an explanation and it was Bob's turn to move, and he lost. So n=9, Alice's turn, she'll lose.
I didn't get A for most of the contest because I'm an idiot, but this was a fun contest!
For E, what you do is take some prefix and concatenate it until it's at least length $$$k$$$. In E1, you can brute force every prefix. In E2, is the approach some kind of z-function thing?
Weak pretests for E1. :( . whereas good pretests for E2 :( .
Test case on which your E1 might fail
12 30
dbdbdadbdbdb
Correct Output
dbdbdadbdbdadbdbdadbdbdadbdbda
Was E2 = E1 + suffix array for the reversed string?
I thought to do that, but then I passed pretests by greedy...
And now it failed. lmao.
I used rolling hash values in combination with binary search to find out which part of the subsegment of the string is different from the prefix string.
Not really, its a simple greedy.
Clearly as we proceed from the starting of the string (after the first character) its optimal to take any $$$s_i \lt s_0$$$ since it will lead to a lexicographically smaller result than appending the string which will add $$$s_0$$$ again at that point.
But what about if $$$s_i = s_0$$$? Then we have to check further characters. We can see that it will produce a better answer if in the first position where $$$s_{i + k} \ne s_{k}$$$, we have $$$s_{i + k} \lt s_{k}$$$.
We can maintain this by just keeping a counter for this k when we reach an equal element and resetting it when we get a smaller character (or breaking if its a larger character). Additionally we have to be careful to store this temporary string during the equal part somewhere else and only add it once we reach this k-th position.
Code — 119871715
"We can see that it will produce a better answer if in the first position where si+k≠sk, we have si+k<sk"
What about the prefixes which are ending between i and i+k? Should we not check for them as well and figure out the best prefix in this window? What's the reason behind claiming that repeating (i+k)th prefix is the best option?
https://oj.uz/problem/view/BOI13_pipes
I often take Virtual Practice on CF and am used to facing a lot of hack tests. So since I saw the small number of the pretests, I have been very worried to be hacked!
How to prove for D?
I think in most case the number will be (odd->)even->odd....->odd.
But when $$$n=2^k$$$ it is special.
yeah, in particular when $$$n$$$ is odd, Bob has a symmetry strat (always pick the same divisor to subtract that Alice does, and things work out bc of parity)
I wrote out a proof here: https://mirror.codeforces.com/blog/entry/91835?#comment-805791
I solved E (E1+E2) using 2 Pointer approach. 119902053 Edit :- Got WA on Test 93, Weak Pretests :(
why didn't you just
`n=min(n,k);`instead of`if(k<=n)do(k);`else do(n);A lot of plagiarism happened in Round; Many posted solutions on youtube. Better to make round Unrated.
give link
After seeing this comment, I searched and look what I found https://www.youtube.com/watch?v=e9i8c6JKmXs here you go :)
Went through the linked video, the guy is an absolute legend
Then every round will be unrated :(
Missed E2 by 1 sec :(
How to solve D ?
i actually wrote a recursive solution and then i could see the pattern of even odd.
Next i just validated for even odd. Found that for power of two that are odd , answer is false.
Hope that helps
Research again ) Nice approach.
meet a new cheater This is how kedos123 bypasses Plagiarism testing.
I am watching him from so many contest , He has done this today and in previous contest, and I am sure he must have done it multiple times before as well. People like Master_Jiraya are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .
todays submission[submission:119865102] 119855748 saw his submission time vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++; vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++; vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;
Biggest template I have ever seen
Looks like he took the template of every LGM (including Benq, he has a huge template) and mashed it into one.
What's the idea behind E2? Can it be solved using Z function?
Rolling hash with binary search got me pass the pretests
I used same idea for E1 and E2. I just checked for the character which exceeds any character in the prefix.
Was the TL for E2 really tight? My O(N) soln kept giving TLE on case 12.
https://mirror.codeforces.com/contest/1537/submission/119909827
Try this input: 50 100 zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfeda
Can E2 be solved without suffix array??
I solved it without suffix array. Waiting for the system test.
Can you please explain your solution?
I took a random string. Let's say-"pabccepabcdf" I ran a loop over the string length. At the instant, where the character is greater than the 1st character ("p" in this case), I printed the string till the last character. At the moment, the character is equal to the 1st character, I checked further characters, if any of them is greater than the corresponding character in the prefix of string, I printed the string till the point I found a matching character for the first character.
For example:- In the example, I have taken, the moment I found the 2nd p, I started checking the further characters with the corresponding character in the prefix. "a" with "a", "b" with "b" and so on. I found that in the d in pabcd is greater than the corresponding c in "pabcc". So, I stored the prefix "pabcc" and printed it required number of times.
UPD: It passed. Submission
So overall you figured out that "pabcce" is a better prefix than "pabccepabcd" and then you broke the loop.
But what about the prefixes in between this matching window? "pabccep", "pabccepa", "pabccepab", "pabccepabc" Why are you not comparing with these as well? to figure out the best prefix in this window
"pabcce" is lexicographically smaller than "pabccep".
In this case, yes. But you are not comparing these prefixes in your solution in general(you are just ignoring them). I guess there is a way to prove that all these prefixes will not lead to a better result as compared to the current prefix.
Yes, it can be proved that those will not lead to a better result. I can't give you formal proof but I will try as much as I can.
It is sure that there isn't a character greater than "p", else we would have used
breakand printed the loop with prefix just before that point. So, those prefixes must have a second occurrence of "p". The character just before "p" will be surely smaller than "p". So, that prefix will be lexicographically smallerProblem D have some ideas in common with a problem which was part of the recently first round of the Tournament of Towns Mathematical Olympiad
Moreover! Problem D was Problem 6 Argentian TST Cono Sur Mathematical Olympiad 2019
D is very similar to MIT PRIMES 2019 G5
Even the names are the same...
AE1BE2DC would have been a nice ordering (for me, at least).
I think that's weird, isn't it?
A,C,B,E1,E2,D :')
Ah! That hurts.
In B, we just had to print 1 1 n m :)
Oh, I checked for (1,1), (1,m), (n,1) and (n,m) :'(
Sometimes Java is worse.
problem C . I used LinkedList. Costs me TLE . like seriously dumb Changed to ArrayList and AC . lol
Problem D . Create a set of long for checking powers. Got WA — because i was comparing int with the long values in set Took me hell lot of time to bebug what went wrong
Good problems. Sadly i coudnt perform well :(
E is a standard application for Z-array.
i tried using lps as in KMP, by i guess was missing some cases.
Try to append z character n times in the given string and then apply the same thing. This worked for me but I used Z algo.
My Sol. for B is (1 1 n m) But i see large codes of ppl?
It's correct,
how? can you please explain?
The maximum number of steps would be 2*[(n-1) + (m-1)] (first testcase was a hint). No matter what the starting position is, If the yo-yo's are at (1,1) and (n,m), You will always get maximum number of steps.
Proof-
There are only 2 ways
1. (i,j)->(n,m)->(1,1)->(i,j)
2. (i,j)->(n,m)->(i,j)->(1,1)->(i,j)
Calculate the number of steps for these, you will always get maximum number of steps.
How did you think of or get 2*[(n-1) + (m-1)]. Sorry to ask but i am a newbie.Also thanks so much for the solution. I get it.
During the contest, I thought of the following problem-
In a n*m grid we have to go from point A to B and then come back to A. Maximum number of steps would be 2*[(n-1) + (m-1)] for A=(1,1) and B=(n,m). This is very clear I guess.
Now if I throw in a point C in between, you can see (1,1)-C-(n,m)-(1,1) will always return in 2*[(n-1) + (m-1)] steps. I then verified the claim against sample test cases.
same as my solution! it also can be n,1 and 1 , m it will also produce same answer.
After bricking C and getting it in the last 4 seconds, read D. These alice and bob problems always get on my nerves. Any suggestions on how to improve on game theory?
Lol same, im not too good in game theory but here i just brute-forced and coded the pattern
can you please share your core on brute force -><- I tried writing it but i'm not getting the expected output. Edit: got it :)
In problem C, what should the answer be for the test case below
Given =
1 1 3 3 6 6Shouldn't the answer be
3 6 1 6 1 3, coz the absolute diff b/w first and last is min=0and also the difficulty level is31 3 3 6 6 1
My bad, i didn't count the equality.
It becomes tricky if the author changes the condition from
h[i] <= h[i+1]toh[i] < h[i+1].Then for the test case i mentioned, your sequence will give
difficulty = 2whereas minedifficulty = 3. Am i sounding naive ??Yeah, I made the same mistake. I was trying to solve the h[i]<=h[i+1] problem.
3 6 6 1 1 3or1 3 3 6 6 1, etc give more difficulty (note that difficult sequence was supposed be non-decreasing and not strictly increasing)My solution for D.If n is odd, Alice will have to subtract some odd divisor of it, so landing on an even number, bob can subtract the same number again and keeps doing this, so bob wins, as he always starts at an even number other than 2. Special case 2^k, Alice can subtract n/2, not allowing bob to copy. If Alice doesn't subtract n/2, a new number will have an odd divisor allowing bob to subtract a random odd divisor and get the odd number scenario, so Alice is forced to subtract n/2 every time, so odd powers of 2 bob wins, even powers of 2 Alice wins.
PS: posted before editorial
Why is my solution is still in the queue while other's solution with high submission time got evaluated?
Yeah same here bro
not just you,I think will be okay after full system test
Did not solve D, but this is my post contest explanation.
For powers of two there is only one way the interaction can progress.
Otherwise
"If the first number is even, Alice can stay in even numbers".
Why would Alice want to stay on even numbers? How do you know what numbers would be beneficial?
Why does game theory exist :(
Make this round unrated! Really long queues and horrible protests for E1, E2
If you are FSTing E (or worried of FST), try the following case:
The correct answer is
baba.It is okay with me if I FST one problem. But when I FST 2 problem variants from the same mistake, it is actually sad :/
while(s.size()<k) s = s+s;
n = s.size();
adding this will pass all testcases
if solution failed in pretests than may be i came to this edition
suffices
What does fst means?
Failed System Test
This blog had > +700 before the system testing LOL
E1 and E2 could've had better pretests. My solution failed system testing after passing 40+ pretests
fst in two contests in a row. fml.
greedy forces lol
What a nightmare system testing that was xD !!
I missed z character in z algo :XD
WA on testcase 93 : https://mirror.codeforces.com/contest/1537/submission/119898534
AC : https://mirror.codeforces.com/contest/1537/submission/119915549
Which z algo are you referring to?
Read this : https://cp-algorithms.com/string/z-function.html
Thanks for the great problems. Really nice round.
I think round should be unrated because i have negative delta
It was a joke. I have +23
Nice job guys xD .. But problem was good, no doubt !!
link
Was tester's solution wrong? https://www.youtube.com/watch?v=seaskdKf2sI
can you guys check why I have wrong answer on test 2 problem D https://www.ideone.com/6MA7rt
Case 1 8
So relatable !!
i feel stupid now
To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Can someone please explain why I got a -20 delta in today's round despite submission for problem-A getting AC ?
Here is my submission: 119905644
MikeMirzayanov sir, please look into this.
UPD: Issue resolved.
https://mirror.codeforces.com/blog/entry/20762
Please go through this link. If you perform worse than your expected performance, you will lose your rating. If you perform better, your rating will increase. Your rating just doesn't keep increasing.
E1 & E2 can be passed using a greedy approach as well. U can have a look at mine sol which has a time complexity of O(N).
Has anyone managed to pass E2 using binary search and hashing. I know in that 2s TL it won't pass as it will be nlog(n) and is giving TLE. But now I saw binary search in the tags. So just curious to know has anyone passed using binary search.
Not so sure but it seems like the idea for F is somewhat kinda old.
https://mirror.codeforces.com/blog/entry/91835?#comment-805524
I spent most of the 2 hours solving the wrong problem in C. I thought you had to climb to gain difficulty. And the rest of the contest didn't look so hard...
Problem F is nice.
Tried to cover all the observations in my solution video :) Explanation Link
Great Explanation , Kindly upload video for E2
https://mirror.codeforces.com/blog/entry/91381?#comment-805796
He explains E2 in a very simpler way i think. :)
I have to say that pretest and finaltest in problem E is too weak and I have seen a stronger problem F somewhere else.
Hi everyone!! I am really new to codeforces... But I wanted to know that does cheating occurs in every codeforces round?.... Yesterday, I saw after the contest, that answers to problems A, B, C were posted on YouTube before the contest started.... This is so sad on the cheaters part as well as codeforces that the questions of the contest are leaked out before the beginning of the contest.
Please answer SlavicG mesanu
cheating
leaked questions
MikeMirzayanov , please do something .. Don't let the questions get leaked before contest.
I find it hard to believe the tasks were leaked before the contest. Can you provide some links?
mesanu https://www.youtube.com/watch?v=WdlsTRQ5n4Y
His ideon code was created 16 hours ago. Even with error that puts it in the timeframe of the contest, not before.
wow... so you mean to say he solved all 5 quesions just within 15 minutes of the beginning of the contest and uploaded 5 you tube solutions , with links to the code within 15 minutes..?? does it make any mesanu
I also want to point out that there was a guy guessing the day before the contest that problem D or E would be on game theory.
It bugged me because i don't recall the same person in any other contest guessing the problems. Maybe he does and I just didn't see it before.
Game theory is a popular topic and considering we had at least one game theory problem in our last 2 rounds, it's not that out bizarre that someone guessed it.
Some one please help in Problem F2, or what are the prerequisite for it?
Does anyone know the reason for a 45+min long queue in non-contest time now?
You can tell the answer to this test 1 5 4 4 5 5 5 in task C?
4 5 5 5 5 1 4is one.Can somebody tell me in problem D.Deleting Divisors?
if I take n=12 then Alice will do 12-6=6 (as 6 is a divisor of 12), now n=6 and this is bob's chance now bob will do n=6-3=3 now the chance is of Alice and n=3 so Alice will not be able to win then bob's wins the match but the test cases are showing that Alice wins the match for n=12Why would Alice choose 6? Players play optimally so Alice can choose to substract 3 from 12 making n = 9 which is losing for Bob.
Codeforces Round #726 (Div. 2) — (×)
Former Problem Round — (√)
wow very strong pretests on E2
Attention!
Your solution 119862059 for the problem 1537F significantly coincides with solutions All_Forward/119856937, royo_sea/119862059. 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.ml/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.
A code from 2020-03-17 ： https://www.luogu.com.cn/blog/AC-Evil/solution-p6185