久别无恙, Codeforces!
We are glad to invite you to take part in Codeforces Round 942 (Div. 1) and Codeforces Round 942 (Div. 2), which will start on Apr/30/2024 17:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions. Some problems will be divided into two subtasks.
The problems were authored and prepared by N_z__, wyrqwq, yinhy09 and me rui_er.
We would like to thank:
- TheScrasse for his perfect coordination.
- Alexdat2000 for Russian translation.
- negative1, tzl_Dedicatus545 and lelml for providing some
rejectedproblem proposals and discussing problems with us. - peti1234 and A_G for LGM testing.
- 10circle, le0n, Clein.qwq, AC-Automation, LMydd0225 and prvocislo for red testing.
- Survivor_winner, _rey, lvkaiyi0811, heaksicn, fishy15, FzArK, Error_Yuan, golions and jamesbamber for orange testing.
- zplqwq, StudyingFather, htetgm, carnation13, purp4ever and Tricopter for
violetpurple testing. - tianbincheng, dxbt, LaMatematica14, OgradL, newb_programmer, joaozao, ssshanto, Quinx and 1egend for blue testing.
- lzqy__, stalkkk_19, madsere and Alenygam for cyan testing.
- Amirben for green testing.
- acoatoitgs for gray testing.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
You
for participating in this round.
Score distribution:
- Div. 2: 500 — 750 — 1500 — (1000 + 1500) — 2500 — 3500
- Div. 1: 750 — (500 + 750) — 1250 — 1750 — (1750 + 1000) — 3500
We hope you'll like the problemset!
UPD: Congrats to the winners!
Div. 2:
Div. 1:
Editorial is out.
Hope to get postive delta!
I am rui_er fan!
Unfortunately I can't participate, but GL&HF to you!
Hope to solve ABC in this round
I hoped that too but ended solving A,B,D1 lol :)
Looking forward to this high-quality contest.
rui_er!
As not a tester,I don't know how this round is like.
As a problemsetter, hope you have fun!
As another problemsetter, Good Luck.
As a person who read three body problem, hope to solve three problems.
As a person who will be reading the problems, hope to solve four problems. GL&HF
As a person who read three body problem, hope to solve three problems.
How hard will this round be? They are known to create hard problems. :/
Div.2 will be as hard as Div.2, and Div.1 will be as hard as Div.1 :)
lol :D
So sad that I can't participate this contest, GLHF
I think you will get upvoted if you mention the fact that you are also a team member of us.
You're right :D it went from -9 to +9
Hope for high-quality problems!
As a tester,
Yeeeep
As a tester, I comment after purp4ever for a living.
when testing gets more upvotes than the actual contest
As a tester, I tested
I hope this is a perfect competition.
As a tester,I also tested :)
GLHF!
I am curious about why this contest changed into div1,div2. I remember it was div1+div2 until yesterday.
The sponsor is not available.
What’s the reason to prefer separate rounds over a combined round?
So you can't increase rating by beating div2 people.
Certain div1 people have replied to me with "so i dont need to solve 2 more trivial problems"
Doesnt make sense to me because it takes 5 mins but ok
As far as I know, separate rounds are just the default for historical reasons. I think there is no big difference between separate and combined rounds (i.e., just those 5 minutes).
[maybe having separate rounds instead of combined rounds also affects the rating system? I have no data about that]
If this was a combined round, maybe hack and FST would not have occurred in Div1-D.
Clearly,this will make it more difficult to increase the rating.(
QP
As we all know, cute rui_er is a kind of ruler.
OMG ruler round
She always come back
orz wyrqwq
rui_er!!!
As a tester I don't know what to comment.
This is what I acknowledged from Algodoo marble races, so the figure above actually disobeys the rule in Algodoo.
Purple HSL: [270, 100, 100]
Violet HSL: [300, 100, 50]
And, more astonishing, violet belongs to Team Pink, not Team Purple. If we change "L" of violet to 100, we will obtain magenta, which definitely belongs to Team Pink.
I like violet :D
Good luck & have fun to all participants!
Hope I can reach IGM lol
Hope you can reach IGM! ^_^
Well, you did it oneesama~
As a tester, hope you enjoy the problems!
as a Minecraft lover , I hope there is Minecraft in the tutorial
++
SpeedABforces
As a non Tester me happy ;)
Spent one hour just to realize that the answer for B is long long :v
wrong place ;[
LOL I didn't notice bro
wait no but same, had 4 penalties until I've figured it out
Brooo, thanks, completely missed that. There even was a hint that it's pre-test 3
I got AC for problem E one minute after the contest. I enjoyed the problems, thanks
it's not the Edu round bro
Kk, thanks for the notice and sorry
As a participant, I will do my best and use all heuristics I know
I became CM in today's edu, where shall I register? div 1,2?
Maybe you can register Div.2 now and take part in Div.2.
Like changzhou, became Master but got negative delta in Div.2 :(
It would be cool to continue the tradition with photo of authors and coordinator:)
In Edu, many solutions to problem A, including mine, are hacked, because of set.
How is it possible? The time complexity is $$$O(t*n*(n-1)/2*4*log(4)) = O(5*10^7)$$$ which should not work longer, than 2 seconds.
I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(
Hopefully my solutions will not get hacked in this round.
I think you have commented on the wrong blog.
my bad
Was the div2 registration intended to close this quickly? Almost 20 hours to go and "registration completed".
Registration completed means u have successfully registered to participate in the contest, that doesn't mean that registration has ended for all.
Oh, I don't recall clicking Register on that edition for some reason xD, must have done it before the announcement or something.
orz rui_er
久别无恙, Codeforces!
Please comment in English or Russian.
nutella, not LGM, testing.
Why did div1+2 collapse into div1,2?
because there's no sponsor :(
Why downvote me, it's the truth...
I'm also a team member:(
Now you got upvoted cause you mentioned you're our team member :D
I wish high rating to participants. Best of luck everyone.
GL&HF! Hope for high rating!
wow CN Round! Hope I can return home on time :D
Seeing "You" in legendary grandmaster colour felt so heartwarming even though I might never get there.
If you click on it, it will direct you to your profile :D
Wish get blue!!!!!
Wow,Chinese round!
Yet another Chinese round!
why this c is so difficult
Going for D1 first before C might be a wise choice, because of its lower point value.
As a tester,I look forward to becoming Master.
may be in this contest I become a pupil or not. lets see!
Hope to get
violetpurplejust want to know what does the score distribution
(1000 + 1500)
mean?two problems or something else?
It mean task with subtasks. Example: Problem F in CF940
Thanks, that's clear
I have participated in edu round yesterday and rating still not changed yet, If i participated in this round, my rating will change depending on my old rating?
the rating will depend on updated rating of yesterday's contest.
Hope everyone will not get stuck in A, B and C.
i was stuck at C in yesterday's contest
then learn dp bro
Yes, I have to.
I did in A.
If this round is hard I will be angry
are you angry now?
As a Participants and who will enjoyed the problemset, I hope the problemset will be good :)
as a tester, hope you enjoy this round. This is certainly a very interesting round and I personally enjoyed it a lot, hope you guys have fun!!!!
My first ever Div 1!
希望可以解决一个题
please comment in English or Russian
As a problem writer who wrote rejected problem proposals, GL&HF to everyone!
If you like MO this much, you could try asking these on AOPS. That way, non-mathematicians can focus on coding! Leave us some problems!!!
Worst contest I have ever seen!..
that problem of the ordered pairs(a,b) have the vibes of a N1 Imo Shortlist xd
what is MO?
Mathematical Olympiad
ah thank you
Can someone answer this please — The rating changes of div2 participants will be made considering the performance of div2 contestants only or the performance of div1+div2 participants combined ?
i spent more time thinking about B2 than any of CDE.... I even had to use OEIS as a crutch for B2 (https://oeis.org/A063647 is the number of possible $$$y$$$ for each $$$x$$$) cause im too stupid at NT
Tfw I spend nearly two hours sitting in one place at D2. Always feeling so close, then turning out that I got nothing.
I'd appreciate a hint.
can anyone help me in c, i get correct submission (using binary search ) 258901211 but get 5 wrong submission by using the end value 1e12,1e14,1e15,1e18 . can anyone say the reason why only 1e13 get accepted
Same mistake I did and suffered 2 WA.
k-=(mid-arr[i]);
This will overflow. Since n is 1e5 and mid>=1e15i got accepted on 2e17. (probably 1e18 is going overflow and others are not enough , dont know)
cool contest! how to solve E please?
B2 is an easier problem of an IATI problem: https://infos.infosbg.com/files/Contests/IATI/2022/day1/Senior/statements/A3_divide_en.pdf
Can we binary search on C div 2?
Yep, use BS to find max of min in the list after purchase.
you can BS what's the new minimum element after adding k cards
Probably possible, but not necessary. You can straight-up iterate one time to distribute evenly so that we have $$$x$$$ minimum elements ($$$x \le n$$$), then iterate another time if after that $$$k$$$ is still positive.
Yes, but not necessary. Wasted like an hour doing it. Then looked at implementation of top guys and felt really stupid.
My approach didn't even consider BS. Just get the list sorted and then bump up the minimum with your coins to equal the 2nd lowest, then the 3rd, etc.
that will work for small k, but k is too large here.
Large
k
is not an issue: my solutionToo large? I was able to optimize the step of increasing the minimum to O(1) time for a total complexity of O(n). No need to worry about the magnitude of k.
in div.2 D2 number of pairs(n, m) {n fixed, m unbounded} is equal to this OEIS A063647 but couldnt proceed further. did someone solve it by looking at this oeis?
nah it's just some basic math deductions lol, not sure if my solution will fst tho
How to solve B2? The max I could reduce the problem to is that any pair $$$(a, b)$$$ must satisfy $$$((a / g) + (b / g))$$$ divides $$$g$$$ where $$$g = gcd(a, b)$$$, but I still have no clue how to actually count this faster than $$$O(n \sqrt{n} \log{n})$$$.
Also B2 >>> C in my opinion, it took me ~15-20 mins to come up with the overall approach for C while I was unable to get anywhere on B2 after 1.5hrs of thinking T_T.
It should be reduced to count pair $$$(a, b)$$$ such that $$$(a+b) | b^2$$$
You just need to prove that if $$$(a + b) | b^2$$$ then $$$(a+b) | gcd(a,b) b$$$
It's actually enough to iterate over all factors of $$$b^2$$$ that no more than $$$b+n$$$
The question is about the hard version, not the easy one
Yes. I'm talking about B2. :)
But if $$$(a+b)|b^2$$$ then the $$$a = 4$$$, $$$b = 4$$$ from the fourth example of B2 (which is confirmed to be a valid solution) won't work: $$$(4+4)/4^2 = 8/16 = 1/2$$$, this is not a natural number. Are you really sure?
You might misunderstand the notation here.
$$$(a + b)|b^2$$$ means that $$$b^2$$$ is divisible by $$$a+b$$$.
Oh, yes, my bad, sorry
Let $$$a=gx, b=gy$$$ where $$$gcd(x,y)=1, g=gcd(a,b)$$$. $$$(x+y)$$$ divides $$$gy$$$, let $$$gy=q(x+y)$$$ or $$$qx=y(g-q)$$$, $$$y$$$ divides $$$qx \implies y$$$ divides $$$q$$$. Let $$$q=py$$$. So $$$gy=pyx+py^2 \implies g=p(x+y) \implies p$$$ divides $$$g$$$. Also note that $$$x<n/g$$$ and $$$y<m/g$$$. This allows you to check all pairs $$$(x,y)$$$ such that $$$gcd(x,y)=1$$$ and $$$x+y = g/p$$$ by iterating through all values of $$$p,g$$$. Overall time complexity is $$$\sum_{p=1}^{min(m,n)} \sum_{g=rp, 1<=r<=min(m,n)/p} \ min(m,n)/(rp) = \sum_{p=1}^{min(m,n)} min(m,n)/p = O(min(m,n)log(min(m,n)))$$$
Here is how I solved B2
Assume that $$$gcd(a,b)=g$$$ and let $$$a=gx$$$,$$$b=gy$$$ and $$$gcd(x,y)=1$$$. Since we need $$$g(x+y)$$$ to divide $$$g^2y$$$, we get that $$$(x+y)$$$ divides $$$gy$$$. So let $$$A=x+y$$$ and $$$B=y$$$. Here are few observations
$$$A>B$$$
$$$gcd(A,B)=1$$$
$$$A$$$ divides $$$g$$$ giving $$$A\leq g$$$
$$$gB \leq m$$$
$$$g(A-B) \leq n$$$.
Thus we get that $$$B\leq\sqrt{m}$$$ and $$$A\leq \sqrt{m}+\sqrt{n}$$$. So we can brute force on each $$$(A,B)$$$ pair which satisfies $$$1$$$ and $$$2$$$ and find the value of $$$g$$$ that ensures $$$3$$$,$$$4$$$ and $$$5$$$ by say precomputing multiples of every number.
Maybe it is an easier way:
let $$$s=a+b$$$, then $$$(a+b)|b \cdot \gcd(a,b)$$$ equals to $$$s| b \cdot \gcd(b,s-b)$$$, equals to $$$s | b \cdot \gcd(b,s)$$$.
It meens that, for each prime $$$p$$$, let $$$p^{k_1}|b$$$ and let $$$p^{k_2}|s$$$, then $$$k_1 \ge k_2/2$$$.
Calculate all prime factors of all integers, for each $$$s$$$, calculate the number of $$$b$$$.
I do really enjoyed this contest. Unfortunately, couldn't derive the formula for Div.2 D2 that would work with O($$$nlogn$$$) complexity
Out of curiosity, is there an easier approach than matrix expo to calculate the cumulative sums in Div1C?
I solved it purely by observing the matrix. Took me a lot of time but managed to solve it using just prefix sums.
It is actually a tree with depth less than $$$\log n$$$.
Yes, but how do you count the number of times a node at depth $$$d$$$ is added to the current node?
The recursive prefix sum value seems to be a linear equation of $$$d$$$ levels. I just gave up and used matrix expo to calculate the values in $$$O(\log^3(n) \cdot \log(k))$$$ time (the base matrix is just the lower triangular matrix, i.e, 1s for $$$col \leq row$$$).
Then I just used these values along with the tree to calculate the answer.
Simply write down on paper and notice that it is Pascal triangle.
I strongly recommend you learn Generating Function! It is extremely useful!
In this problem, let's write down
a[1] a[2] a[4] a[8]
asb[0] b[1] b[2] b[3]
and see what happens if you do the reverse of $$$f$$$ in the problem statement.b
will becomeb[0], b[1]-b[0], b[2]-b[1], b[3]-b[2]
. And if we write down this array in the form of a generating function, it will be a transformation from $$$p=b_0 + b_1x + b_2x^2 + b_3x^3$$$ to $$$q=b_0 + (b_1-b_0)x + (b_2-b_1)x^2 + (b_3-b_2)x^3$$$, which turns out to be $$$q=p(1-x)$$$. If you do it for $$$k$$$ times, it will be $$$q=p(1-x)^k$$$. The coefficient of $$$(1-x)^k$$$ is simple.As you can see, generating function provides a clear and simple deduction towards the solution. Usually it is problem-agnostic, which means you can put anything involving counting (especially dynamic programming) into a generating function, and use math tools to solve it. You don't have to stare at the coefficients anymore. I got this solution using generating function withint 5 minutes.
Yes, the $$$i$$$-th value is actually $$$\binom{k+i}{i}$$$. If you turn your head, you should try see a pascal triangle
facepalm I observed the matrix of linear equations was the lower triangular matrix but somehow didn't realize this T_T.
Thanks for the help!
i did something even more stupid
i knew $$$i$$$-th value is $$$[x^i] \frac{1}{(1-x)^k}$$$ then immediately went to do code that without thinking more 😹😹😹😹😹
"if you turn your head" lol
Too simple formula encourages guessing instead of solving, it is not cool.
Div2F is nice, implemented binary search part but couldn't to find minimum >= previous on
x
jumps in time.I'm too bad at maths for this.. was so close to IM but now I'm back to low master cause I got hardstuck on NT lmao
:( :( :(
Mathforces.
Weak pretests. Maybe I can get positive delta with points earned by hacking.
can someone give me the submission of div2 C i checked my code at least 1000 times i couldn't find a mistake.
of cource 258890400
How to solve D1 div 2?
First, you have to see that
a
must be a multiple ofb
. Then, it is a pretty straightforward (n+m)*log(n+m) implementation, where you iterate over all possibleb
and over all multiples ofb
.$$$a + b$$$ must clearly be a multiple of $$$b$$$. This is only satisfied when $$$a$$$ is a multiple of $$$b$$$.
However if $$$a$$$ is a multiple of $$$b$$$, then $$$gcd(a, b) = b$$$, meaning $$$a + b$$$ must actually be a multiple of $$$b ^ 2$$$.
So we have $$$a + b = k * b ^ 2$$$, or $$$a = k * b^2 - b$$$. So for each $$$b$$$, you can just count the number of multiples $$$k$$$ which generate valid values of $$$a$$$ in a total of $$$O(m \log m)$$$ or $$$O(m)$$$ time depending on implementation.
can you help me understand how do we find that the time complexity is
O(mlogm)
?We are counting values of (a+b) which are multiples of b.gcd(a,b).
e.g. (a+b) = k.b.gcd(a,b) (for some k values)
dividing through b gives a/b + 1 = k.gcd(a,b)
This means that a is divisible by b, e.g. let a = Xb, then gcd(Xb, b) = b
Which reduces the problem to
a+b is divible by b^2
Iterate all b's, and look for how many b^2 fit beneath "maximum value of a" + the current b and sum them all up.
You need to know two things for this.
1) are you aware of "sieve of eratosthenes" ? What is the concept behind it ? What will be runtime complexity of it ?
2) Reduce the formula
Why do you need SoE or something like that if ones just use the following piece of code?
Same problem can be solved in multiple ways. my approach and your approach are different.
My solution is based on what I did during the contest, I never claimed, that it is most optimised approach xD.
I reducing the formula, I reached an observation, that 'a' must be multiple of 'b'.
Now, for all 'b', within 1 to m, I will traverse through all possible multiples of 'b'.
To understand the time complexity I gave an example of SoE.Hope I have explained how I solved the problem.
mathforces
Am I the only one using Mobius Inversion to solve Div.1 B2? I spent almost an hour and couldn't find simpler solution. Also C<<B2
Yeah being stuck in D2 made me lost rk1(Div 2). I spent almost an hour in it :(
Actually when you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g in about $$$O(n+m)$$$.
BTW how to solve by Mobius Inversion I dont know lol
These are some good problems 💪💪🔥🔥
https://codeforces.me/contest/1972/submission/258921511
Can anyone pls tell what is wrong in this code for C?
use long long instend of int
i have already defined #define int long long
The value of the variable hi which you have initialized as 1e18 is leading to this error. I changed the initial value of high to (maxa + k), where maxa is the maximum element of the freq. array and then the solution got accepted.
New Submission
I think in the final output k should be min(k, remaining).
B2 is restarted
My pre-contest predictions:
Seems that all my predictions are correct!!
"Thanks" for such a round to let Chinese Rounds become stereotyped!!!
Exactly.
TheScrasse meanwhile I want too hear your voice about these Chinese style problems. I am wondering if these math problems are interesting for you, and the round is balanced with these problems.
My take:
edit: how can I forget the FST of problem D? Pretests seems to have n=m.
About the last point: feedback is from the testers, which cover a wide range of ratings. In this case there was no big complaint from any tester. Maybe the testers overestimate the beauty of the problems?
FST on D is just me being blind, seeing $$$5$$$ generators (with two of them which weigh 7 KB) and missing $$$n = m$$$. This is the second time I miss this detail, I hope the third time does not happen :(
Always math :)
Is stereotyping always harmful?
How to solve D2 (div. 2)? I've figured that x * y / (x + y) = n means (x — n)(y — n) = n ^ 2 and was trying to iterate through n, looking at all its divisors, getting divisors of n ^ 2 from it and trying to form all valid (x, y) pairs from it. But since n can get pretty large, O(max N * sqrt(max N)) takes too long.
$$$a+b | b\cdot (a,b) \rightarrow g(x+y) | g^2y\space \space(let g = (a,b) ,x = a/g , y = b/g) \rightarrow (x+y)|gy \rightarrow (x+y)|g \space \space((x+y,y)=(x,y)=1)$$$
When you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g.
please find the mistake in this. Div2 C 258921994
Thanks for this contest, I really liked problem $$$C$$$!
If you submit the code casually, you even have a good chance of passing problem B and D1.
A question to anyone who solved div1C: does $$$\mathcal O(n\log^2 n)$$$ solution with the restoration of the value from indexes with a lower
lowbit
value to indexes with biggerlowbit
values work?UPD: the question is no longer relevant.
is my implementation wrong or does binary searching on number of perms not work?
my logic was that if you wanted X perms than array should be [X/n, X/n, ..., X/n+1, X/n+1] with X % n of them being X/n+1.
for some reason i get WA on pretest 2 so now i sad :(
258903132 258901827
oh wait its probably cuz X=0 makes my code not work... oopsie :3
nevermind... i think it is still wrong
could somebody pls help me?
spotted an ar69420 in the wild
can u acc fix my code pls :(
i also bin searched but i used some stupid stuff to calculate 258909591
Does my solution Can be hacked ? 258885731
Thank rui_er for giving a so easy CN Round.
Div. 2 B and C were literal guessforces. I spent an hour trying to find a solution to B, even wrote a brute force, then I viewed the samples and be like "Hmmmm... It's almost as if the U count is odd then Alice wins else Bob". And pretests passed... Whatever. Probably I'm just too retarded and it's actually very easy to prove.
Yeah whenever you remove a coin, you always remove a U coin.
There are three neighbour cases
In all three, the parity of U does not change, so the only relevant fact is the parity of U.
The problem statement says we should also remove the selected U. So it actually always changes to the opposite parity.
My comment was perhaps not super clear. I refer to the parity staying invariant after you remove the first U coin, i.e. the neighbour transforms don't change parity, only the initial coin removal does
i have gone mad after realizing the solution for B after spending an entire hour.
The brute force also passes 258885731
how have so many people in Div2 solved D2?
Can it really be ChatGPTed tho?
what is the optimal rearrangement of the the 6th test in Div2 C test samples ?
I tried a lot during the contest to figure out what is the best rearrangement but I couldn't find it :(
If you meant this testcase:
Then it's as of following:
Then we get:
Now, one possible arrangement might be:
($$$46$$$ elements in total, valid subarrays are $$$[1, 9], [2, 10], \dots, [32, 40]$$$)
Thank you a lot ^_^
I hope there will be a plagiarism check for this Round, since apparently the solutions to Div 2 A, B, C and D1 were leaked hardly an hour into the contest.
a, b, c were all brute force that even 800's can solve. I dont think it is necessary to check plagiarism for them
Nope, never. Regardless of the difficulty of the question, plagiarism is a serious issue.
I can't call myself a mathematician anymore :(
Thanks for Interesting problem and positive delta~~
Anyone knowing in how much time aproximative the ratings will be out??
i think this contest was unrated
Nope, ratings are out. I never saw a div2 to be unrated
i wasn't sure about that
Why A is failing on systest?
Auto comment: topic has been updated by rui_er (previous revision, new revision, compare).
CNOI Round 🤓👎
In div2 on D2 we have 588 accepted solutions. In div1 on B2(same task) we have 582 accepted solutions.
funny :)
why D1 is so easy may be some other problem can be placed at D and D2 can be a different problem
There seemed to be a weak pretest in C? 4000AC->3600? And I seemed to fly about 100 rank:)
Yeah, also jumped a bunch of places up. But then again, you're responsible for verifying your solution even if you managed to pass the pretests.
Yup. I made the upper bound on answer smaller than it actually is, giving WA on test 9. Tbh sucks going from +30 to -100 delta.
How do you know your delta? C-F predictor does not seem to be showing correct values anymore
lol, i spent like 40 min trying to solve B, because i didn't double check examples , and i didn't read n coins on the table forming a circle
Could you please give me testcase of problem C div 2. I got WA but I don't know why.
was it rated?
day by day div 2 is getting harder for me :)
That's what she said, and it wasn't for div-2. xD
I have made detailed video explanations for C and D1 Question Here are the links for anyone who wishes to watch
C : https://www.youtube.com/watch?v=ZP4HPYTWtZQ D1 : https://www.youtube.com/watch?v=cSKooXv7FKA
Finally a div.1 standing with tourist rk1 and jiangly rk2! BTW, congrats to Kevin!
amazing problems! However math problems are a little more than I expected,which I'm not good at.
orz rui_er!
Why more and more gcds?They are not interesting!!!!!!!!!
please provide an update on when the rating will be updated?
I found myself waking up six times throughout the night, hoping to see my new 'Max Rating,' yet it remains unchanged even now!
Is it rated?
yeah, why not?
they still didn't update our rating
That's normal. I'm used to it.
How long did it take at most?
about one day
Is there any issue/delay in updating rating of this round?
Possibly this?
Did anyone try to prove the solution div2 B? I think we get the pattern pretty quickly, but proving it is not intuitive. How do we prove that with induction?
At every turn, the parity of the total number of 'U' cards flips. This is because once we flip a 'U' card, the number of 'U' cards decreases by 1. Now since it has two neighbours , it will be either a). DD -> UU b). UU -> DD c). UD -> DU
Either the number of U increases by 2, decreases by 2 or remains same. Since we already discarded a U card, the parity always flips. Also since the maximum number of U can be the current size of the string, we can guarantee the game will end at most after n turns. The winner of the game is the person who gets the string with only 1 U left. So we can conclude that whoever starts with odd number of U's will be the one who will get to the state where there is 1 U left, and hence will win the game.
got it thankyou.
I couldn't prove it too ,just discovered the pattern through test case,but couldn't understand the gist of the problem.
Can you tell me who will win for this case"UDU" ?
Was this contest unrated?
Over a day and wasn't rate. Why??
And finally, it's rated!
Tourist reclaims the throne!
hi https://codeforces.me/contest/1972/submission/258916012 https://codeforces.me/contest/1972/submission/258916865 they have cheated on same time and same code!(Q-D) please check https://codeforces.me/contest/1972/submission/258922220 https://codeforces.me/contest/1972/submission/258916012 and (Q-C)
tourist is back on top againnn
so happy for him, nice comeback!
in this contest there again those (before some of them i already mention in previous contest where they failed the system test for a problem)tried to change there code and may happen that they might be undetected so posting this (majorly they tried avoiding a bit by looking at the format of i(i+j) and just trying to be smart let them be declared as a variable instead of using directly and all the necessary loops needed in submissions of D2 div2: 258918241 258918681 258918681 258917636 258918237 258917628 258918431 258917198 258917154 Vladosiya MikeMirzayanov
《久别无恙》
nazmulaas2023 is my second id....on this contest..by mistake of mine i submitted my code into nazmulaas2023...that's why my code of nazmulnns2066 and nazmulaas2023 is same...unitentionally i did this...please consider..i apologise for this mistake
i made a mistake during the contest..i submitted C in my wrong id which is nazmulaas2023..when i realize this...i change some of the code and then submitted in my id nazmulnns2066 which i did the contest..that's my code look similar.. i apologise for my mistake..
sorry MikeMirzayanov, but the system declare that my 1972C submission is similar to huanjua. My explaination is we are both students come from Ho Chi Minh City and in 2015-2016 entrance exam in VNU.HCM for grade 9 there is a problem using the same binary search idea and we use the same idea. Please give me back my rating. Thanks