Hello, Codeforces!
Imakf and I are glad to invite you to Codeforces Round #808 (Div. 1) and Codeforces Round #808 (Div. 2), which will take place on Jul/16/2022 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours to solve them all.
We would like to thank:
- Monogon for his 1-year cute coordination and very helpful discussion.
- KAN for the great help with round preparation.
- Wolam for his discussing the problems with us, which helps us to find the solution.
- smg23333 for donating his csgo time to test the problems in advance.
- AliShahali1382, SecondThread, wxhtzdy, taran_1407, Retired_cherry, antontrygubO_o, Tlatoani, errorgorn, hg333, kassutta, timreizin, Taday, Qiulyqwq, dorijanlendvaj, arvindr9, gamegame, EmptySoulist, prabowo, Yakumo_Ran, star_xingchen_c, generic_placeholder_name, 74TrAkToR and Ari for testing the round and their invaluable feedbacks.
- MikeMirzayanov for amazing platform Codeforces and Polygon.
- geranazavr555, KAN, myav and unreal.eugene for translating the statements into Russian.
Score distribution will be announced before the round.
Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)
UPD1: Score distribution is
Div 2: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$
Div 1: $$$500 - 750 - 1250 - 1750 - 2500 - 3250$$$
UPD2: Editorial
UPD3: Congratulations to the winners!
Div 1
Div. 2
1-gon 可爱 1-gon cute.
Hope everyone enjoy the round.
Imakf is very cute.(:
Imakf is very cute :)
Imakf is very cute.(:
I hope that today's tasks will be interesting and good. Let's try to solve more problems. Good luck!
Good luck!
I really like the Codeforces competition. Hope you like it too. After all, this is a great opportunity to test your knowledge and experience. This will help increase our Knowledge. I hope this competition will be great for everyone!
Problem C was amazing, just look at the number of ACs, 2k managed to solve out of 13k, good contest!!!
We should have more of these.
Expert, I'm coming. EDIT : it came true
Specialist, I'm coming.
Newbie, I'm coming
Unrated, I'm already there :D
dreams do become true:)
candidate master, I'm coming.
Can't wait to see PinkieRabbit's performance!
Good. Very nice. Let's see Paul Allen's performance
Can't wait to see PinkieRabbit's performance!
I bet it will -154.
Can't wait to see 300iq's performance!
now PinkieRabbit go back to GM.
Thank you for the great round!I can't wait to try my best to solve the problems!
And hope seniors can enjoy their university lives in the future!
As a tester and a fan of cute Imakf, love the round so much!
Hope everyone enjoy it!
As a tester, I disagree with this part of the announcement:
Historically, that almost certainly means us testers made a mistake or there's a CF meltdown and the round becomes unrated.
As a contestant, I don't believe testers anymore.
In the last round, I passed three questions and I hope I can reach 1200 points in this round.
Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)
hope so (XD)
Hopefully I don't lose expert.
Same! I also just recently got it, we are living on the edge here. Good luck!
yeah you too man.
Well, that definitely didn't go very well... I'm lucky I won't drop to Pupil after this round.
Guess these will be my last words as an expert in the foreseeable future :/
Same man, I think I've got a valid sol for C (after the contest!) I got seriously unlucky lol.
I feel you. It's funny we fell down to very close ratings too. Better luck to us on #809 I guess. The journey back to expert begins!
yes imao. Time to start upsolving!
Hopefully I don't lose CM
Another one bites the dust...
Respect smg23333!!!!
Wish you all wouldn't gain negative ratings in this round!
So this is unrated?
One of my curious questions： How to become a Codeforces Round tester? Sounds interesting
You have to get invited by the writers
I can't wait to see jiangly's performance!
I can't wait to see tourist's performance!
tourist will be 1st on scoreboard
In yesterday's contest it took me almost 2 hours to solve C. And then I looked at the scoreboard. tourist solved C in just 2 mins.
Man how!!! Is he not human???
jiangly will take the first place!
Today is my birthday. Hope this contest is as special as my birthday
All the best to you and to everyone else!!
happy birthday dude
respect++ for smg23333
It says it is theoretically possible that no one gets negative rating.
Someone knows how?
The scoreboard has participants with non-increasing order of rating.
He will reach 4000 before I reach 2000 XD
before seeing tourist reaching 3979
yes
wana to be a Specialist ... ovo ...
Deleted
Deleted
Is there a way to find out if a specific user is registered for a contest (before the contest begins)?
Add the user to your friends' list, and see all your registered friends. I don't know a better solution lol
Yes, thanks, I didn't know about the registrants page!
let's see how bad I'm going to do after solving only 100 problems this year and the last submission was more than 2 months ago and the only algorithm i still remember is implentation
Edit: Well I started with C and it was a bad plan
Is this div.0?
I've checked the title of this contest for 3 times, I think this is div.1 but the problems are more like div.0.
"Wish you all wouldn't gain negative ratings in this round!" Wow!! I think all will gain negative ratings in this round XDXD
Me for sure negative.
Sed
It just feels bad when i am a second year CS university student and can't solve A.
oh, I thought I'm the only one who can't solve A problem, it's hard as """"
God, I felt so useless when I took that much time to solve A with solid proof, until I saw comments. Feeling so idle in this contest :)
How'd you solve it?
That's cheating, my friend. Texting during the contest about problem solutions.
Can't solve 2C. Lower rating :(
me too :|
Binary searching for the answer almost seems like a cheat to be honest.
me too :(
Капец, C легче A. Люди, как такое возможно?????
I don't know why my codes for A,B are WA
One of my worst contests ever! I will never join Chinese contests again.
The contest is not balanced. The last Div2 round was very balanced but this contest is just a fast coding contest with some sh!t.
It doesn't mean all Chinese contests are like this one.
I hope so.
What are you saying. If you solve the problems normally, the round will be cool. The problem is not in the round, but in you. It's not speedforce. I agree, maybe we need to swap A and B, but no more!!!
Why do you think so? I also think this round is not good enough(Exactly last round too),but it is absolutely not a fast coding contest.
From Newbie to Pupil to Specialist to Pupil to Newbie. What a Journey :)
Lol, see mine
Dont give me that Hope :P Hope my graph goes like your April 2022 Graph
Hope my graph goes like my April 2022 graph :(
There is a big gap between B and C
exactly. The contest is not balanced
I am that point when there is nothing left to think about A, B, C
I aspire to be the one, one-day! orz
Every time a problem with '0' and '1' appears in a contest,
I can say same thing for me, but with $$$l$$$ and $$$r$$$, even though I solved B today.
Also when there is bitwise XOR or something like that
I can feel what Doremy is going through :(
Can someone give me a hint for Div2D?
Note that there are always a lot of duplicates in the array
Thanks
The process converges very quickly to all zeros because the number of distinct differences is $$$O(\sqrt{M})$$$ where $$$M$$$ is the largest element in the current iteration.
Thanks
pigeonhole principle
A) Prove by AC, somehow works. Spent 20 mins on it, thought about rage-quitting without making submissions because it seemed like I won't be able to solve even A or B :lol:
B) Until the very end of the round I was convinved all elements also have to be distinct, so had no idea how to approach it and solved it only at the very end
C) Prove by AC, no idea why it work and whether it really works or problem just has bad pretests
D) A bit of reasoning lead to solution convincing enough. Quite a cute problem. Logic seemes easier than A/B/C
Can you please explain your reasoning for D. Thanks
It is pretty much above
Note there cannot be many unique values in the array
Think how to avoid useless computations, repeating values don't add much new. They add zeroes and further zeroes again produce zeroes
So you just keep track of the number zeroes and observe how the process quickly converges on all the other values
Well, that's the idea.
Same lol for B
D1B editorial. Also it's my only authored problem lol.
"Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)", That's when we should have known that the contest would have been a disaster.
For Div1C, is this wrong or does my implementation just suck?
Let T be the MST of the graph. Since edge weights are not repeated T is the only MST.
Then a root R is good if and only if for all edges (u, v), at least one of the following hold:
(u, v) is in T
When T is rooted at R, u is an ancestor of v or v is an ancestor of u.
Your idea is correct.
Pretty brutal contest. Very humbling, can't wait for the editorial.
Whats wrong with my code? am using PB_dS with reverse traversing and putting max value + 1 every time i check more than q
I did smth similar with seg tree but got 2 WA's, smh.
Take a look at Ticket 15819 from CF Stress for a counter example.
Div 2 A is trash
You are absolutely right.
С too
it just use a small trick, i think it's interesting
Just because you didn't solve it?
POV: no one can feel my pain The pain: 8 wrong submissions in B
maybe u were thinking like me to put diff values in diff places :( 1 wrong submisson
In Global Round 21 I did 12 WA on test 2 submissions.
Problem C is just like my friend. His name is Long. \
How can I pass problem 3？
Dear authors, shouldn't it be said in B that numbers can be equal? I love you very much, kissing you for the great time!
or at least give a sample case where numbers are equal
Exactly!
Well, it is our fault in a sense that we don't read statements properly. But yeah, they could make it clearer.
Solved B only at the very end because of it
I got 2 WAs in problem B because of this :')
I did not solve the problem because I thought the numbers should be distinct. But that is my fault since it was not stated that they should be distinct. Even the examples did not have any equal numbers to make it clear.
No more algorithm-reading problems plz No more algorithm-reading problems plz No more algorithm-reading problems plz
Ouch, the power outage plus the problems were the final nail in the coffin for me.
Sorry to say but A, B and D are one of the worst problems I ever solved. C was pretty good though.
It could have been much better if the authors asked just to output the number of solved contests, because then a DP approach with segment tree/SQRT-decomposition on top of it could work without greedy approach.
Can you elaborate on the DP approach?
Yes, of course. Let
dp[i][q]be the maximum number of tested contests if we consider only first $$$i$$$ contests and after testing or skipping $$$i$$$th we have IQ exactly $$$q$$$.At first, let's solve in $$$O(n^2)$$$.
for each
i:$$$a_i \le q$$$. for each
q,dp[i + 1][q] = dp[i][q] + 1.$$$a_i \gt q$$$. for each
q,dp[i + 1][q] = dp[i][q],dp[i + 1][q - 1] max= dp[i][q] + 1.Let's note that in the second case
dp[i][q] + 1is always no less thandp[i + 1][q - 1], so we can replacemax=with=.Okay. Now let's maintain the difference array of
dp[i]:diff[j] = dp[i][j] - dp[i][j - 1].When we increase
i, we simply need to1) add 1 to
diff[a[i]], substract 1 from the last element ofdiff(this is the case $$$a_i \le q$$$2) set the prefix ending with
a[i]to 1 (case $$$a_i \gt q$$$)This could be done using a segment tree or SQRT-decomposition.
Because
qcannot decrease more than $$$N$$$ times, we can keep just $$$N$$$ values of diff.But I don't see a way how to recover the answer...
You can record the pos of the dp-ans,and then output answers according to this.
Could you please elaborate on that?
I've explained my solution here.
Will,my dp solution is diff from yours XD
Could you please explain yours?
OK I just realized my solution may be not dp(although it is from dp sol), sorry :(
I just do it from n to i.
make c[i]=(a[i]>q)
Notice that if c[i]=1 and i is picked,then all of c[i]=1 in i+1 to n must be picked. (When I didnt notice this I use simply dp to do it)
set dp[i] as the best answer when you deal with i to n,and c[i]=1,and dp[i] can be claced by dp[nxt[i]] (nxt means the next 1's pos)
Here we can use BIT or priority_queue to solve. Actually it is not dp eventually (I came up with it according to O(nq) dp sol).
div2c was binary search ?
it can be done linearly with reverse order
it's a greedy
what's wrong with this approach of Div2 C. Any counter testcase? It gives WA on TC 3
upd: got it
6 3
4 4 3 3 2 2
Did you guys use prime factors to solve problem B? Bruteforce just got a TLE
Used simple math for O(1)
You don't need any prime factors or anything like that. My idea was: the last element should be divisible by $$$n$$$, the second last should be divisible by $$$n-1$$$ and so on because $$$gcd(i, a[i])$$$ is always $$$i$$$ in that case. All $$$i$$$ are different so it is the correct solution.
Yep. i got the same idea. But i was traversing [l, r] round and round to get the proper a_i which fulfills gcd(i, a_i) = i. And got a TLE
$$$gcd(i,a_{i})=i\Leftrightarrow a_{i} \equiv 0 \pmod{i}$$$
Problems are not bad, but the problemset is too hard :(
Congratulations, you're now officially interlude 2.0
i never know what E, F problems look like. lol
Very INTEREST Round! I have never got the place on div2 before
pC is very nice
what a shame how could I miss such a cute contest! :,c
A was torture for me.
weak pretests and lack of explanation for problem B
Dekh rhe ho Binod, C ko kitna tough banaya ja rha hai!
About how my Div1D gets FST: somehow creating a vector and resizing a vector $$$O(n^2)$$$ times magically make my code 5x slower.
I was thinking C for more than 40 mins like what exactly I could do...just read the tutorial and found that it was an easy problem :). just didn't get the right approach:(
Ratings updated preliminary. As I said here: https://mirror.codeforces.com/blog/entry/104766?#comment-932270 cheaters will be removed later.
My submission for B no problem I can not find any test case that can fail.Can anyone help me with a failing case??
numbers don't have to be distinct.
""such that gcd(i,ai) are all distinct"" Distinct was mentioned
Dude gcd must be distinct but the ai can be the same.. suppose an array of 2 numbers 1000,1000 have gcd's with the index's as 1,2 respectively, gcd's are different here but numbers are the same:)...what I get is that u have encountered that ai must be different.. if that's not the case still finding the mistake:)
Problem D https://www.codechef.com/submit/ARRAY_OPS wtf
Thanks to this contest, I had become LGM!!!
appreciate very very much for writer and tester!
my friend：“Hello！” me：“How do u know I become a Expert？”
Fortunately I miss this round(I have registered but forget ha) Only 2k solved pC Are you sure this is div2???
Anybody knows the solution for B if all ai were to be distinct between one another?
(meaning that for any l <= i, j <= r and i != j: ai != aj)
candidate master, I'm coming :>
Please don't use questions from other websites . Question d of div 2 or question b of div 1 was previously asked in codechef starters 33. https://www.codechef.com/START33B/problems/ARRAY_OPS . This gives unfair advantage to those who have seen the question previously.
why my rating is rolled back which I gained after giving this contest any help
https://mirror.codeforces.com/blog/entry/104766?#comment-932270