Hello, Codeforces!
I'm pleased to invite you to Codeforces Round 1028 (Div. 1) and Codeforces Round 1028 (Div. 2). It starts on 31.05.2025 17:35 (Московское время). This means that Children's Day will come during this round. I'm sure everyone will be impressed with Children's Day, even if they're no longer children.
I remember when I was a kid, I always looked forward to Children's Day. On Children's Day, there were always candies and fun activities at school. But as I grew up, this festive atmosphere was diluted by the trivialities of life. But luckily, we had Codeforces. Spending the holidays with interesting problems doesn't actually have to be more boring than candies and activities ¯\_(ツ)_/¯
This will be the second round I've hosted on Codeforces. To make it better, this time I've called on my friend MagicalFlower to help me organize this round. Also, errorgorn has helped us very much, we are fully indebted to this well known 🐸 on Codeforces!
For both divisions, you will have 2 hours to solve 6 problems. I hope you will enjoy these problems.
I would like to thank:
- errorgorn for his 🥵 and 🥶 coordination.
- Alexdat2000 for Russian translation.
- MagicalFlower for providing more rejected problems than me. While you may not be able to see these problems, these efforts cannot be ignored. 👈🤣
- EvenImage for existing and VIP Testing.
- JoesSR, qiuzx and 275307894a for Legendary Grandmaster Testing.
- zhaohaikun, N_z__, HealTheWorld, _istil, grass8sheep, EasonTAO and ffao for International Grandmaster Testing.
- Error_Yuan, H_W_Y, Hanghang007 and literalchild for Grandmaster Testing.
- tarche for International Master Testing.
- ODT, Tyx2019, Hank2019, Bazoka13 and bookcat for Master Testing.
- Shoryu386 and ToxicPie9 for Candidate Master Testing.
- daitangchen2008 for Specialist Testing.
- zhufangyi, ls114514, clare_288, Awd_, wengxuanyu, likerun and JessicaZhang for Newbie Testing.
You for participating the round.
MikeMirzayanov and KAN for Codeforces and Polygon systems.
Especially, I'd like to thank JoesSR, zhaohaikun and ToxicPie9 for helping us prepare this round, which might not be able to run as smoothly as now without them.
Finally, I would like to give my heartfelt thanks and praise to errorgorn.
Both of the rounds I hosted would not have been possible without the support and efforts of errorgorn. Although he often rejected my problems 💀 and stood me up a lot 😡, I could sense his love for the problems and his seriousness about the competition in the time we spent together preparing for these rounds.
errorgorn is an interesting guy, you can often see him sending funny emoji like 🤯 in the discord, and he would also sometimes share me with some of the local culture of Singapore. I am so lucky to have had this fun time with him.
Some time ago, errorgorn happened to tell me that he might not have time to continue as Coordinator, which I deeply regretted. Likewise, I'm starting my college career, and this will probably be the last round I host at Codeforces as well.
Hopefully this round will be a perfect end to my experience hosting rounds on Codeforces. It's really quite an unforgettable experience, and I'm also looking forward to the next collaboration with errorgorn.
The main character of the problems will be Gellyfish🍏, and her friend Flower🌸.
Score distribution:
- Div.1: $$$500-1250-1750-2250-3000-(2500-3500)$$$
- Div.2: $$$500-750-1250-2000-2500-3000$$$
Good Luck & Have Fun! 🔥🔥🔥
UPD1: Congratulations to the winners!
UPD2: Editorial is out.
Sorry guys, errorgorn can't coordinate anymore. He's busy coordinating dates with me 😳
🤯
?? Is that gay or intentional?
yes
So intentinoal or gay
maybe he didn't read after "is that gay", hope you got the answer
Bro he is coordinating tutor dates(I don't know what i'm sayin').
Errorgorn is gonna help ToxicPie become a grandmaster. That's the dates he's talkin' 'bout
How'd you use an emoji?
that background looks intentional
I aim to reach pupil in this round ,and solve at least 3 problems
I am from the future , you made it , you will reach expert soon !!
As a tester, I hereby strongly recommend Frieren: Beyond Journey's End (葬送のフリーレン).
It's a nice music, i promise!
Hope to solve 3 questions for the first time in a div2.
Why so many downvotes? :)
This is my first contest as a specialist!
It's my too! Good luck!
mee too :)
do you mean was ?
Don't be upset now. It was your first contest that you got pupil from a specialist!
good luck
Appreciate the effort—looking forward to the contest!, and good luck with your college career.
Hoping that problems will be very easy
They are hard(
Hopefully it's going to be a fun game :D
Feeling your love for errorgorn — is this a record for 'how many times someone is mentioned in a round announcement'?
hope to solve three in 20-30 and then grind on 4th
now fingers crossed for crossing 1700.
As a tester,I think these problems are brilliant and I hope you find them enjoyable.
Whenever I try to use emoji, it says:
Emoji (and other unusual UTF-8 characters) are not supported :|
And this guy filled the blog with emojis.(¬_¬)
You can use HTML. See here.
Use no emojis in these blogs.
hope to solve 3 problems and get +delta
First true Div 1! orz madhavG
a->anfixed, thx!
I'm literally 1 rating away from participating in Div 1 XD
The strongest expert -> The weakest CM
It should be "is an interesting guy" ig, on the last 4th paragraph.
🤯
As a tester,I hope you enjoy this contest :)
It’s really sad to hear that this will be your last round as a coordinator =(( Thank you for all the effort and passion you’ve poured into preparing such fun and thoughtful problems. Even if you won’t be hosting rounds anymore, I hope you’ll stay connected with the Codeforces community in some way. Wishing you all the best in your next chapter!
Happy Children's Day ;-)
hope to solve 2 questions for the first time in Div-2
all the best to everyone
Hope to not get wrong on first 3 submission
same LOL :'(
Got 4 incorrect on A
I have been losing ratings in the past 3 rounds. Hopefully, this pattern will change today :)
I will never be a contester in any contests of THU qwq
Wasn't div2C/div1A a simple wrapper over https://codeforces.me/contest/1043/problem/F ?
i solved it using DP with time complexity O(n * max(a) * gcd)
would be time limit exceeded on the problem you shared (I haven't solved it)
Problem 2 can be done in O(n) ig, premax of indices and max of biggest index in p and q (also their respective index :( in case of equal)
binary exponentiation cost logn for each operation
The time limit on C was surprisingly tight. Tried to do 2d caching for a while before I realized the second dimension was unnecessary.
Getting Destroyed by testcase 3 on problem D for an hour and a half crew. Fun problems, thanks!
same same, i'm guessing the solution will be simpler than my dumb logic.
WA on pretest 9 in C?
same :(
same :(
same
same:(
Same :(
same;(
So what's your idea?
got it,I assumed that the maximum count of operations to make a number = gcd can be atmost 2.
can you give a Example?thx
And why is that wrong I mean can you give me a example where it's greater than 2. I tried hard but was never able to find such a example.
check above
Yeah thanks
what is that Div2B :"/
2^i + x (x < 2^i) > 2^j + y (y < 2^j) if i > j
yes. that is precisely what i was trying to do.
iterate left to right,
get the maxm guy in q , find its pairup in p and check with ans[i]
again iterate left to right,
get the maxm guy in p , find its pairup in q and check with ans[i]
got so many WAs on tc3.
can't see the code yet so some guesses
forgot the case when max p_i == max q_i
overflow
compared the modules instead of the actual values like the guy below said
idts i am overflowing any way.
here is my code,
v => stores power of 2 precomputed.
could u find a reason?
so the third guess
the third guess?
Comparing modulo instead of actual values.I too made the same mistake
While finding the maximum, you are taking modulus. So, when taking modulus the maximum value is becoming lesser than second maximum value. So, instead of calculating the maximum first, we have to compare the values of p[i] & q[i], and then we have to find the answer.
could u explain with a testcase ? i am still not able to understand why.
oh HolyFUCK. I got you both. FUCK FUCK!
bro please tell me also i too got wa on pretest3 3 times!
So here's what was going wrong in my code:
I was comparing pairs based on the expression (2^p % mod + 2^q % mod) % mod directly while iterating.
The issue is that when p and q are large, 2^p % mod and 2^q % mod can overflow and wrap around, giving smaller values than they actually represent.
Because of that, a pair like (60, 55) might appear smaller than (30, 29) just because modular arithmetic distorts the comparison—even though 60 > 30 and 55 > 29.
So what I should've done is:
First compare the raw exponent values (p, q)—without applying modulo—to decide which pair is lexicographically larger.
Only after picking the better pair, apply the modulo while computing the final value: (2^p + 2^q) % mod.
That way, I'm doing all comparisons on the actual exponent values and only reducing the result modulo mod once at the very end, avoiding any distortion from early modulo.
Glad I couldnt figure out A immediately and decided not to participate further :)
that's a strat ig
Could anyone kindly help explain why this solution isn't working(at test case 3) for problem B? TIA
there might be other errors also
but one i can see is in
you also need to take mod after doing sum. (Did the same mistake :(
try adding another mod at the end after taking sum while printing
You forget to % mod again when printing the answer.
At this part of your code, for(ll i=0;i<n;i++){ cout<<(ll)(power(2,res[i].first,mod)+power(2,res[i].second,mod))<<" "; }
Supposedly, for(ll i=0;i<n;i++){ cout<<(ll)(power(2,res[i].first,mod)+power(2,res[i].second,mod)) % mod <<" "; }
div2C<<div2D
yea C and D were wild
Div2 A-C were fun though. But soon gave up on D. Still no idea now.= =
for D I kept trying something around "loosely" gathering information about the values by going thorough the queries. In the sense that, every time u do something, u know something about the values from before. The information are all of the type "s[i] was at least v". And by keeping every min value, at the end, u can check if u get the correct thing. And that seemed to suffice in my head. It didn't work tho.
my D ended up working. My solution was correct. I should've coded it myself instead of vibe-coding it...
Fuck Gepetto
Submission
I think my solution to problem C is $$$O(n^3)$$$, why it can pass pretests?
UPD: Oh I got it, the time complexity is $$$O(n^2)\cdot \log{[\max(a_i)]}$$$.
even with 5000*5000 it showed tle
you really telling me 5000*5000*log(5000) doesn't pass in div1A?? no comments
You can precompute all GCD pairs up to $$$N - 1$$$ in $$$O(N^2)$$$ I think. You make a sieve like loop, where you iterate over numbers (results) $$$d$$$ and mark $$$GCD[i * d][j * d] = d$$$. The last time you substitute $$$GCD[i][j]$$$ will be for $$$d = gcd(i, j)$$$. You can avoid multiplication if you write it like this:
Why is this $$$O(N^2)$$$? Because the number of substitutions is equal to $$$\sum (N / d)^2 \lt N^2 \zeta(2) = N^2 \pi^2 / 6 \sim 1.5 N^2$$$.
Nice sieve, I believe you, but what is this symbol? where can I read more about this?
ζ(2)
It is known as the zeta function
Yes, the lies machine did say that too,
heard of it few times, but never really fiddled with it.
It's just summation of reciprocals of squares up to infinity, ie. $$$\sum 1/k^2$$$. It's just notation for this, a Riemann zeta function. It just so happen that while the sum of reciprocals (ie. $$$\sum 1/k$$$) diverge, this sum converges to this value $$$\pi^2/6$$$. Since we are adding up to $$$N-1$$$ and not to infinity, the sum in the time complexity is less than that and the whole thing is $$$O(N^2)$$$.
good to know, I never used it before (at least in contests) in my time complexity appromixation.
You could also do $$$GC[i][j] = GC[j\%i][i]$$$
Isn't modulo operator expensive and should be avoided?
It has a higher constant factor but is still a lot faster than nlogn.
322318871
Given $$$j\geq i$$$, $$$GC[i][j]=GC[i][j-i]$$$. This can remove the modulo cost.
mine passes though?
322233494
I forgot you can't see code few minutes after contest, so here.
bfs (towards 1 / global gcd) turns out to be much faster
(although I can't figure out the exact complexity in my head right now, can someone figure?)
Div2A>Div2B
nah bro , B was wayyyy more complex
actually if you get the logic of B, then it seems very easy, but even after that you have to take care of overflows, modulo etc. which makes it tougher than A. Also anyone with patience can solve A, by taking multiple cases.
bro is flexing his binary knowledge
Div2B>Div2C
bro is flexing his DP knowledge
I used DP and it got TLE, but I think that Div2 A > Div2B
i mean if u had to choose subset first thing that should come to mind is DP ;)
I'll keep that in mind next time.
Why so hard？
lowkey I agree this Div1A and B are harder than usual for me
Find the difference
First TLE and second AC
Line 44, f[i]=0. This is not the reason
In line 44 the position of i, j is swapped inside memgcd method.
Yeah, I got TLE just because cache-unfriendly
Thanks for the nice contest!
Really, I was quite surprised by both the simplicity and difficulty of div1B/div2D. It's really easy to fall down the rabbit-hole of erroneous thought. I was only able to do it after using the technique "ok, instead of thinking in a straightforward manner, let's think in reverse (ie, bottom-up)". Once you start thinking that way, the problem becomes very straightforward and you realize that the solution is like 10 lines of code.
I wonder why I struggled so much with it... I guess for future reference, be more prepared to think in reverse?
geez, I did thoughta about thinking in reverse immediately, but the solution is still not straightforward to me. So sad.
If you want, I can give you the following hint:
Let's consider the smallest value $$$v$$$ of the array $$$b$$$. Clearly, all of the positions that did not have that $$$v$$$ as their value could not have had an ancestor $$$\alpha$$$ such that $$$\alpha \leq v$$$. This means that we could go through this implicit DAG and set all of the positions that the original $$$v$$$ can reach in $$$a$$$ to, well, $$$v$$$. Then, notice that this idea kinda repeats for the other values.
Kinda get it. Still it is quite intricate. Thx!
I mean, the description is kinda scary, but really, the solution just ends up being:
Well, we just want to know what's the largest value a certain position can be after trying to undo the queries. Say initially $$$b = [?, ?, 9]$$$ and we have a single operation $$$x_1 = 1, y_1 = 2, z_1 = 3$$$. In this case, we know that whatever $$$b_{x_1}$$$ is, it can't be less than 9. Same with $$$b_{y_1}$$$. Then, we can maintain that restriction on $$$b_{y_1}$$$ and $$$b_{x_1}$$$, stating that both must have values of at least $$$9$$$.
We can then understand that applying these operations in reverse creates an implicit DAG, as in $$$z_i \rightarrow x_i$$$ and $$$z_i \rightarrow y_i$$$ (technically, it's something like $$$z_i[i]$$$, as in that position after the $$$i$$$ th iteration).
I suppose that makes sense, but how do we justify that after getting all of those maximums we would be able to recover the minimum? Well, this is where thinking of the smallest value helps. After somehow propagating all of the values, either there was a path in the DAG where the minimum was never replaced or all of the paths somehow replaced the minimum. If all of the paths were replaced, then we just say that it's impossible. Otherwise, we know that we can set that value. What about the 2nd largest minimum? Same idea as the first minimum could not have interfered in the paths taken by the 2nd minimum (as they would have been replaced).
Then, the solution becomes: Reverse the queries and maintain a vector $$$\textit{mx}$$$. Initially, $$$\textit{mx} := b$$$. After that, for each query of the form $$$x_i, y_i, z_i$$$, set $$$\textit{mx}_{y_i} := max(\textit{mx}_{y_i}, \textit{mx}_{z_i})$$$. You have to work out some edge cases such as when to reset $$$\textit{mx}_{z}$$$, if you have to apply that operation with both $$$x_i$$$ and $$$y_i$$$ (or perhaps neither) and whatnot, but this set of operations gives the original array $$$a$$$ if it exists. Then, you can just unreverse the queries, apply them onto $$$\textit{mx}$$$, and see if you get $$$b$$$.
Does that make sense or did I make it too confusing? haha
really clear and impressive.
How is the solution straightforward when thinking in reverse?
See this comment I just made
Can anyone tell me what is the pretest 9 of problem div2 C??
Why is time limit on 1A and 1C so tight? I was just optimising constant factor for most of the time on C, not fun at all. If O(n * m * H) is not supposed to pass set higher limits on them. If it is supposed to pass set lower limits.
yea why it doesn't pass ;-;
Please Help How to Solve B?
I got wrong answer in tc3, got pounded by B today.
Yeah me too. I handed in like 7 times and they all got WA in pretest 3. No idea about the edge case.
Since you have gone past some testcases, so you must be knowing we would be keeping track of max p and q values with their positions, and so you would have been trying to do something like max(2^maxP + 2^q[i-ppos],2^maxQ+2^p[i-qpos]) and you are right but the problem is performing mod on powers can result in incorrect answer as say a>b & a>mod and b=mod-1,then max returns b%mod>a%mod even though a>b.So you need to go case wise and compare integer values in case of maxP==maxQ and for other cases ,if maxP>maxQ then result is 2^maxP+2^q[i-ppos] and similar for other case.For reference you can look 322247403
Since you solved C,can you recommend some similar problems to this.
Ohhh I finally understand now!! Thanks for your patience for teaching me!
Here are some similar problems that I think they are interesting (Did them before during previous contests):
Easier problems:
https://codeforces.me/problemset/problem/2093/C (Number theory and math)
https://codeforces.me/problemset/problem/2071/B (Math)
Harder problems:
https://codeforces.me/problemset/problem/2104/D (Also GCD)
https://codeforces.me/problemset/problem/2097/A (An interesting math problem)
While finding the maximum, you are taking modulus. So, when taking modulus the maximum value is becoming lesser than second maximum value. So, instead of calculating the maximum first, we have to compare the values of p[i] & q[i], and then we have to find the answer.
It was nonsense To prove my point, only 300 people were able to solve more than 3 questions
How do you solve Div2C?
Make all elements in the array equal to the gcd of the array. Use dp to find the minimum number of operations to make a single element the gcd of the entire array, then apply n-1 operations.
How can I use DP here?
dp[cur] = number of operations required to make it the gcd of the entire array. For each element in the array such that gcd(cur, a[i]) < cur, dp[cur] = min(dp[cur], dp[gcd(cur, a[i])+1]. Base case is dp[gcd of entire array] = 0.
Bro can you recommend some problems or resources similar to learn this kind of DP.I have seen only knapsack and some popular patterns
it was basically a knapsack kind of dp only.. just maintain an index and previously accumulated gcd , decide whether to pick it up or not and update the gcd accordingly..
I originally wrote a knapsack-like solution, where you could either make cur = gcd(cur, v[i]), or just continue to pos+1. This is similar to the knapsack take/not take idea. This resulted in TLE due to the tight bounds though, so I just realized that the answer for some particular cur value is independent of position for this problem. Thus I reduced the dimension of the DP and passed.
dp on subsets ,selecting a minimal subset whose gcd is equal to gcd of whole array
let call the gcd of array is g
my idea is if the there is an element equal to g, then I will output n — [number of element equal to g]. if there are no such element, then it take maximum 2 operations to produce g, so I perform brutal force to find whether there is any couple of elements that produce g. If it does have one then output n, else output n + 1 instead.
However, my approach got wrong at pretest 9, and I can’t find a counter-testcase against my logic.
this is my submission 322294608
Consider this sample case: 1 4 210 1155 770 66
why frozen?
First time getting stuck on Problem B for so long. (why so hard contest)
I think I had the biggest comeback in codeforces history today Solved question B in 1:50:18 Solved question C in 1:59:52 322287747 322294715
Got the idea for B correctly but for some reason pretests failed. Interesting problem. At one point I forgot they were permutations and considered 2 maximums.
Basically find the largest number and its index in P then 2^that number + corresponding in Q. The same with Q.
It'd be nice if C++ had modular exponention.
If you have two positive integers $$$P$$$ and $$$Q$$$, both $$$\leq 10^5$$$, you can proceed in the following way.
Let's compute an array of all powers of $$$2$$$ modulo $$$MOD = 998244353$$$. You can do this with this piece of code:
Now
powers[i]stores $$$i$$$-th power of $$$2\,(mod\,998244353)$$$. You can now compute $$$2^P+2^Q\,(mod\, 998244353)$$$ as follows:Div1C has a bit of the old Codeforces vibe.
In 1A's DP. If I check if the
dp[j]!=INFbefore updatingdp[gcd(i, j)]I can got AC, but TLE on #7 if I didn't check it. And, my solution is $$$O(5000^2)$$$ by getting all 5000*5000 gcds before calculate the test cases. I can't understand why the time limit is unmeaningful tight.Sorry, I never have a good luck and I can't have fun in this round, only the fire fit my emotion.
I also had the concern about the constant factor of $$$5000^2$$$ GCD's, but luckily my solution passed, so I checked the difference between my solution and your first submission.
It turned out:
If you implement GCD with recursion, it will timeout. Using std::gcd is OK.
During the DP, you should update
dp[gcd__[a[i]][j]], notdp[gcd__[j][a[i]]]. It's due to the cache efficiency.gcd__[a[i]][j]is a contiguous memory access butgcd__[j][a[i]]is not.With the two fixes (and without
DP[i][j]!=INFpruning) you can get AC (322321188). I first thought it's all about the speed of GCD but the second fix was also necessary to pass the test 7.I agree that the time limit is a bit tight. However, given that just updating
dp[gcd(a[i],j)]was enough to get AC, it's understandable that author didn't see the necessity to increase the time limit.As I recently found out (and probably many people did but considered unimportant), there is a very easy way to $$$\gcd(i,j)$$$ for all $$$1 \le i,j \le n$$$ in $$$\mathcal{O}(n^2)$$$ time. The proof is a little mathematical though.
Let $$$k$$$ be a candidate of $$$\gcd(i,j)$$$. Then, both $$$i$$$ and $$$j$$$ must be a multiple of $$$k$$$. Among all values that swept through $$$(i,j)$$$, the largest such value of $$$k$$$ must be the value of $$$\gcd(i,j)$$$. So perform a doubly nested loop inside the loop for $$$k=1\dots n$$$, analogously to any sieve-like algorithm that relies on the Harmonic Lemma.
The time complexity. Let $$$\displaystyle f(n)=\sum_{k=1}^\infty {\frac{n^2}{k^2}}$$$. This becomes $$$\displaystyle n^2 \sum_{k=1}^\infty {\frac{1}{k^2}}$$$. The factor in the sum is known to converge, and due to the Riemann Zeta function we know that its value is $$$\zeta(2) = \pi ^2 / 6 \approx 1.65$$$. So our number of operations is bounded above by $$$1.65n^2$$$, meaning that we have an algorithm to preprocess all $$$\gcd$$$ in good time complexity and also great constants.
The relevant submission, 322328173, passes in 234ms.
EDIT: I just got notified that you can just simulate the Euclidean algorithm in DP to get $$$\mathcal{O}(n^2)$$$. That is true. Not having to rely on $$$\gcd(i,j)=\gcd(i,j-i)$$$ and still getting great constants is pretty cool though.
Hi, im a bit confused, why do we need to precompute gcd when the gcd computation of c++ compilers are pretty optimized?
std::gcdstill has $$$\mathcal{O}(\log \max(a,b))$$$ time complexity. If you precompute, it will be $$$\mathcal{O}(1)$$$ afterwards.thanks, i was under the impression gcd computation is faster than log(min)
https://codeforces.me/contest/2115/submission/322293995
why does this TLE for Div1C? I'm pretty sure it's O(n*m*h), which should be comfortably AC.
long doublewhen not needed.I think the biggest issue was using long double instead of double, but changing the loop order of the first loop also halves the time it takes to run, does anyone know why?
322294608
can anyone tell me why my code was wrong at pretest 9 (div2C)
I'm not allowed to see your code but I'm think you might be wrong on this test =)
1
4
30 70 105 42
Correct answer is 6!
My solution gives 6 for this, but still failed :(. Check my comment above,I am lost
Oh, thanks, I assumed that the maximum operation to produce the number that equal to gcd of array is 2. how dumb am i....
Amazing contest! But the time limit for Div2D and Div2C was very tight. My Div2C got TLE for 5000*5000. My O(nlogn) solution for D also got TLE cause I used too many maps. My mistake for not writing in an optimized way, still not having such a tight bound would have been great.
I got no idea to solve problem D :( ,is there some simple idea to tackle it ?
Also struggled a bit in understanding what is happening in A , but logic was not so difficult finally
Nice Chinese TLs, guys.
to be honest, $$$100\times 400\times 4000$$$ in C seemed kind of wild
and it turns out to be way quicker than i thought it would be...
Also the ML didn't allow this complexity to pass. Too narrow.
I'm sorry, but there is a fairly simple $$$O(m ^ 2 h)$$$ solution for Div1.C, and we have no other choice.
It was a very good round with pretty tought problems and a lot to learn from. You'll did nice jobs making problems and conducting the contest.
Very good round! D was super nice.
Div. 2 A Simple solution
If your knight has died, you cannot win. Therefore you can assume your HP is $$$\min(HP, KHP)$$$, where HP means your HP and KHP means your knight's HP. That means Gellyfish wins if and only if $$$\min(b, d) \lt = \min(a, c)$$$, since she goes first.
The Div2C should have allowed n^2*log(5000) to pass
My solution is approximately $$$n^2 \log5000$$$, it passed the pretests in 500ms.
mine n*max(a)*log 5000, also passes in 800 ms.
Can someone please tell me why this failed on testcase - 3 PROBLEM BYou're essentially trying to compare two numbers here, obtained after % MOD. You should be comparing the powers of two.
so it means that if
2^j > 2^ithis holds then2^j %M > 2^i %Mdoes not necessarily holds is it?yes.. just try to change the
modto see2^2 % 5 > 2^8 % 5Sure. $$$2^{30} \gt 2^{29}$$$, but $$$2^{30}\; \% \;MOD \lt 2^{29}\; \% \;MOD$$$.
The problem asks you to find the (max value) MOD 998244353 not the MAX (value MOD 998244353)
if(pow2[p[i]] > pow2[p[pp[i — 1]]]){ pp[i] = i; }
I foresee some potential problem here. Do not compare pow2 with pow2 because modulus operation are taking in place there. I suggest to compare it directly.
I must have some crazy bug in B. I took away the check that it is possible to attain the answer with the min operation (so basically the check that at least a or b equals c where c = min(a, b)), and my solution somehow turned from WA to AC. What's interesting is my AC solution is very obviously wrong, since it doesn't output -1 on any tests like:
1
6 4
1 1 1 1 2 3
1 2 5
1 2 6
3 4 1
3 4 2
What is more interesting, my AC and WA solutions should differ only on tests of this type, and my AC solution somehow passes while being wrong on them, while my WA solution doesn't while being correct on them... Would be very thankful if someone could explain to me wtf is going on
Shouldn't this test case give -1 since b[5]==b[6] should be true?
Yes it should give -1, my AC solution doesn't output -1.
Sorry I misread. My solution gives -1 here, so maybe the pretests are just weak.
I tried hacking my solution and got Unexpected Verdict...
Are pretests for 1B too weak? My wrong attempt passed during the contest, but i realized it and fixed it afterwards.
Hope system tests get all wrong solutions WA.
Also I was stucked in 1C for precision problems, since large combination numbers are needed.
Don't know whether official solution requires it or not.
No need for large numbers.
Let’s denote $$$H = max(a_i)$$$. While there are at least two different numbers in the array, the optimal thing is to act greedily: reduce the maximum number if the sword doesn’t shine, and reduce all numbers otherwise (unless the minimum is already 1). If we fix the number of steps it will take for the “greedy part” to be over (i.e. all numbers are equal), it’s easy to calculate the probability of this happening: a dp where your state is $$$(a,b) =$$$ there are $$$a$$$ operations left in the greedy part (at most $$$m$$$), and we still need to apply $$$b$$$ non-shine operations ($$$b$$$ is initially equal to $$$\sum_{i=1}^{n}(a_i - \min(a_i))$$$, so at most $$$n*H$$$). Transitions are straightforward and this dp is $$$\mathcal{O}(m \cdot n \cdot H)$$$.
Once all the numbers are equal, you can notice that you if you use the “non-shine” operation once in a number, you need to do it in all the others too (otherwise they will never be equal again). You can do a second dp where state is $$$(a,b,c) =$$$ there are $$$a$$$ operations left (at most $$$m$$$), we already used $$$b$$$ “shine” operations (at most $$$H$$$), and there are $$$c$$$ elements in the array (at most $$$n-1$$$) in which we reduced their value by one (if we reduce all the $$$n$$$ values by one, we increase $$$b$$$ by one and set $$$c$$$ to zero). Transitions are not too complicated neither.
When fixing the number of operations in the first part, the initial state for the second part is fully determined. Both parts have the same complexity, so full solution is $$$\mathcal{O}(m \cdot n \cdot H)$$$, and there are no big numbers involved.
Wow, nice observation, thx.
Petition to set all round duration to 3h
+1
Hey I'm your 11000-th fan lol
+1
too hard /_ \
How to solve Div2-B ?
first , you need to notice that taking the greatest exponent will always result in a better answer, because it will be greater than the other ones by at least a factor of 2, so you will be tracking the prefix max on p and q . now for every index i , one exponent would be the biggest value in the prefixes of both p and q, now to get the other exponent you need some caseworking , basically if the biggest value was on the p side you need to get the index it was in (you can create the index arrays for both p and q ) and the other exponent will automatically be the q[i-(that index)], vice versa if the max was in q , now if the prefix maxes were equal in both p and q , you'll need to consider 2 cases , take the index of the max in p , take the index of the max in q , than the ans would be the max between p[i-(second index)] and q[i-(first index)] . and do that for all i to construct the answer
Div2 C's Time Limits are too tight,I don't think i like this problem
For some reason my code passed during contest, but now is getting TLE in system tests
I even got TLE on Test7 though my complexity is $$$O(nV)$$$.
Was there a faster solution for D1A? I ended up changing my code in fear of system tests (1.5s runtime / 2s) and it was still incredibly slow.
my complexity was
n * maximum * gcd computation... it ran for 1.5s in pretests ... but it passed system test just nowyeah that was the time complexity of both my original and newer solutions, the second one I just memoized the GCDs which did not seem to help very much
did your submission pass system test ?
yeah
yayy!!! lezzgooo ....
I did not memoize GCD, passed in 750 ms
322233494
My solution is $$$O(N^2log(K) / log log(K))$$$ (where $$$K$$$ is $$$max \; A_i$$$) and it passes in 187ms: 322286852
Firstly you divide everything by $$$gcd(...)$$$ so that you have to find the smallest subset of elements such that their gcd is $$$1$$$.
To find this subset, you greedily remove elements, the next element removed is the element with the most (unique) prime factors that are most frequent, for example:
$$$A = \{2, 3, 4, 5, 6, 9\}$$$, you remove $$$6$$$ because it is the only element divisible by $$$2$$$ and $$$3$$$, which are the primes that divide the most numbers (3 each).
You remove elements until at least one primes divides every number, at this point you can't remove more elements without modifying the gcd.
This works because you really only care about the most frequent primes, they are the only ones that can make the gcd change. By removing the most you can from those, you leave space for other elements to be removed.
The complexity is:
1. For each removal you take $$$O(Nlog(K) / log log(K))$$$, because you search through every element for the best to remove, and each element takes $$$O(log(K) / log log(K))$$$ to process (this is the maximum number $$$k$$$ of distinct primes such that their product is $$$\leq K$$$, I think);
2. You remove $$$O(N)$$$ times.
So the final complexity is $$$O(N^2log(K) / log log(K))$$$.
I hope this is clear enough :)
If I am not wrong, this can also be extended to larger values for $$$A_i$$$ (around $$$10^7$$$) (without using hashmaps).
My solution can be implemented storing frequencies with the index of the primes:
$$$fq_2$$$ becomes $$$fq_0$$$, $$$fq_3$$$ becomes $$$fq_1$$$ and so on. Like this you only use $$$O(Nlog(K)/loglog(K) + K/log(K))$$$ memory, instead of $$$O(Nlog(K)/loglog(K) + K)$$$.
anyone who was struck in 3rd testcase div2D, and then corrected the solution?
yeah so for div2D my issue was with the backwards-walk logic. I had to split the cases more ((a, b) -> c, (a, b) -> b, (a, a) -> b, (a, a) -> a). And just a whole bunch of ifs regarding the lower-bounds and exact values
the core idea is just propagating lower bounds for the values and then doing a recheck at the end
Getting TLE related to this: https://codeforces.me/blog/entry/97390
Why was i not able to correct my code during the contest? Other competitors got tle on test case 5 during contest and were able to make changes to get AC.
happened to me as well, i changed long long to int and it ran in about 1200ms, my code had the complexity of 5000*n*log(5000) approximately
is there a way to request rejudge?
D2C had 15 pretests...mine was WA on 14 (╥﹏╥)
whoa !!!
Couldn't figure out how to speed up B, any hint?
think of some value for each i that guarantees the max so far
My teacher once told me, "If the contest is organized by Chinese, don't participate. All their problems will be math-related." Today, I participated in the contest and became convinced that my teacher was right.
Why wouldn't you bound $$$m$$$ to $$$4000$$$ in D1C? Why does $$$100 \times 400 \times 4000$$$ pass? Why doesn't my solution pass then?
My solution for Div2C was a brute force, I want to make all the elements equal to the GCD of the array
I will try each time to get the minimum gcd until the minimum element in the array is equal to this gcd, finally count the number of elements that aren't equal to this gcd
precalculating the gcd for all possible combinations using a sieve will probably make it more efficient.
minute of silence for those whom got TLE with $$$O(n^2 \log n)$$$ in C
You could have reduced it to n2 by storing gcd of all numbers from 1 to 5000 with each other in a vector of vector. I did that and my code got accepted.
It's still $$$O(n^2logn)$$$ though but it passes
How is it still n2logn?
Nested loop + gcd calculation for two integers a and b takes O(log(min(a,b)))
I think the other one doesnt pass since it recalculates the GCD for the same pair of numbers multiple times, maybe if you store them if calculated once so you don't calculate them again passes though.
Yeah exactly. It's weird compiler optimizations. Also gcd(a,b) passes faster than __gcd(a,b)
Why was my first submission skipped?
If you submit on a problem which got accepted, only the last submission counts, also you get -50 for resubmit and I think the score you get is less too. All previous submissions get skipped
Why frozen? I cant submit my code.
you can start vp.
thanks for the div2 C loved raging and almost wanting to end everything
Can anyone explain why my latest submission of C is counted, even though my previous submission is also AC. It should be other way around right?
Codeforces rule, resubmission -50 points.
Goofy ahh contest
Why is the standing still frozen?
That was a very tough contest, I never performed this badly. I think I will see a -100 delta. But anyway, thanks for the contest and the efforts to prepare those problems.
DIV2C/DIV1A should be re-evaluated with an adjusted time limit.
can anyone explain why for div2b this fails... x = (pow2[ma] + pow2[b[i — idA]]) % mod; y = (pow2[mb] + pow2[a[i — idB]]) % mod; cout << max(x, y) << " ";
note: ma is maximum prefix of vector a idA is the index of maxim prefix and the b names are just the reverse..the codes which have gotten ac they have compared these two only but with different if()else conditions then why is this code wrong
if maxa and maxb is equal, then you should compare the second terms b[i — idA] and a[i — idB]. But you are first summing up the powers of 2 first(which are modulo X) and then compare with gives the wrong answer, I did the same as well at first,
Can anyone provide a hint for C?
It seems like it has no pattern whatsoever.
The final value has to be the gcd of all starting values.
Once you make one of the numbers equal to this gcd, all others can be made equal to it with just one operation.
Dynamic programming.
How the same code for Div2 C sometimes getting accepted and sometimes giving TLE on TestCase 7??
Can you please help the code i have submitted for div2b is same as ypur first submission why did it fail why it isnt simply max(ab,cd) as in your code
Sure, Let's suppose the value of ab is greater than cd.
Now when you are taking mod, then the value of ab might become smaller than cd, but in reality value of ab is greater than cd. Consider this example
int ab = (binpow(2,44) + binpow(2,4))%mod; int bc = (binpow(2,30) + binpow(2,30))%mod;
Here, binpow(2,x) means (2^x)%mod.
After this step, the value of ab & bc are as follow: ab 125811513 bc 150994942
Now, here you can see that in reality ab is greater than bc, but due to taking mod, it's value has become less. So, instead of calculating their values, we should just compare the powers of 2, which I have done in my next submission. I hope this helps.
Rejudge my code please!
https://codeforces.me/blog/entry/143400
not really sure what learning did Div2 C really had, with tough time constraints, i mean like same dp solution which passes with int16, is meant to TLE on TC 7 if u use long long by default in ur template, seriously??
Long long solution fails: https://codeforces.me/contest/2116/submission/322307127
int16 solution (above solution when done with int16) passes: https://codeforces.me/contest/2116/submission/322308744
I also use int as long long, and I'm facing something weird, sometimes my solution is getting accepted, and sometimes it's giving TLE on TC-7.
https://codeforces.me/contest/2116/submission/322315881 In Div2C why is it giving tle on using long long and got accepted when used int..
Well, your solution has a really huge constant factor due to using a deep recursion (2.5e7) and self-written recursive gcd function. It is known that using long long type increases time of arithmetic operations(including computing a reminder, which is necessary for gcd). It is very likely that this is why you get TLE. Rewrite you dp in iterative way, use std::gcd (which is written not recursively, but iteratively -> faster) and you will get AC with both long long and int. Here you can also invent some funny optimizations, like pre-compute all gcds for all pairs of numbers <= 5000. but they are 100% redundant.
UPD: it seems like I wasn't correct at all, probably the only way to pass a solution is to precompute these gcds. The takeaway is : you should use #define int long long carefully when dealing with problems with tough TL or ML.
Why is there no rating change dor div 1
My solution for 2C passes with
int(1.5s) but TLEs withlong long:*)long long is slower than int, in most cases it shouldn't matter but for tight time limits like C, it can cause TLE.
I realize I should learn to skip challenging problems earlier in future contests. During the competition, I spent 1 hour and 20 minutes struggling with Problem C. However, when I reviewed Problem E after the contest ended, I managed to solve it in just one hour! This experience has taught me the importance of adjusting my time allocation strategy during coding competitions.
Is there any glitch in system testing? My submission for div2 C was accepted during contest, failed on test 7 in system testing. Now when I submit the exact same code, it is getting accepted. Was hoping for a positive delta but missed because of this :)
Gellyfish any explanation — or anything that can be done about it? A rejudge would be appreciated
Same, went from +100 delta to -50 because of this. Easily solved C in contest and if I got TLE during contest could have optimized the code during the 1.5hrs I was working on problem D.
I guess using a std::set to store all the ''useful'' dp states will make your code ' complexity far below 5000*5000
Yes, if our code has failed, so should be others' having same logic and code as ours. People having same code as me have got AC which is really unfair.
+100 to -50!? This shit hurts
Hope things turn around for you soon.
its absurd to lose expert rating to this trash.
I think Div1-C has weak test cases. Many submitted codes can be hacked (time limit) with the following case:
I hacked myself
Why am I getting "unexpected error" when I attempt to submit for 2116A - Гелифиш и трёхцветная фиалка and 2116B - Гелифиш и гипсофила?
maybe its wrong with the server or ...
try with another device or wait or refresh ur web<3
my code gets AC on div2-D，but i think it is fake;how to hack it?https://codeforces.me/contest/2116/submission/322329033
Hey Gellyfish can we get a rejudge? I got A/C in contest for C on my first submission, and now got rejudged to TLE. You've got people who have 5+ failed submissions that later got A/C, this is unfair to the contestants that got a false A/C during the contest with no chance to correct this error. My ranking went from Top 500 to ~4,000 for a silly judging error
Is it possible that this is because although the theoretical time complexity of your code meets the problem's requirements, the constant factor is too large? It's normal for the judging system to have some fluctuations.
Yeah, in my case i used std::set for dp states, which barely passes (or fails) vs std::unordered_set with my exact same code passes with time to spare.
It's just BS that people who got 5+ failed submissions rocketed past me in the standings and i had no chance to correct my code. I solved the problem relatively easily in around 10 minutes understanding the time complexity and got accepted on first submission.
My projected rating post contest was supposed to be 1750, instead i ended up back at specialist. Spent 1:30 mins on problem D, if i had known there was any chance of code failing on C i could have easily corrected it within this time. Trash judging IMO
can anyone tell me where to find editorial of this contest
It's not published yet.
Becoming one of the winners of Div.2 for the first time and become a Candidate Master！
The question is very interesting, but I didn't finish 2F in the end.
May I inquire if there are any official tutorials, and when they will be released?
Normally, Codeforces updates ratings and releases tutorials 2-3 hours after the system test. Why is this round so slow? Are there any issues with Codeforces?
First reach CM!
.
Hey, Can anyone look into mycode for Problem B Div2, It is failing for test 3.Not sure why it is failing and able to figure where went wrong.Help me on this.
I guess this can help you
where am i going wrong in qn B?
https://codeforces.me/blog/entry/143308?#comment-1279438
Oh I only solved 1 problem in Div.1. It's too hard T_T
I couldn't come with a DP solution for the Div2C, so I choose greedy method and it worked for me. When the GCD is not present in the array, I greedily keep on choosing the pairs which will give the least GCD, so first I scanned through all the pairs and then checked the pair with smallest no to every other no in the array. https://codeforces.me/contest/2116/submission/322288935
Please post editorial fast
when editorial
why so many downvotes ? that was an interesting contest. thank you for the round
DIV 2, PROBLEM C, PRETEST 9
Input: 50 numbers... My Answer: 50 Given Answer: 53
My approach: I found the GCD of all the 50 numbers, which is 1. So there necessarily exists a co-prime pair in the 50 elements.
So, my first operation will be on this co-prime pair, which will give me 1. Now, for the remaining 49 elements, i will pair them with 1, one by one, and hence obtain all the ones.
In this way my total operations will be 50.
Please tell me where i went wrong?
6 10 15 -> gcd(6, 10, 15) = 1 but You need 3 numbers(2 operations) to make 1
You cannot make 1 directly with only 2 numbers because gcd(6, 10), gcd(10, 15), gcd(6, 15) != 1
Thus, there are some cases that [total gcd is 1 & No co-prime pair exists.] I think pretest 9 is one of these cases.
Since there's no editorial yet, F has super low number of solutions even now but it seems
treap would be useful? It can do range updates and range reversal easily. The updates are a problem since we should store sets instead of scalar values, but how about storing just indices of sets in a separate DSU data structure with $$$O(Q \log N)$$$ nodes? Pushing a set from a treap node to children will make it merge with only disjoint ones. This structure (DAG) will have some sources, "remove" operation disables a source, "insert" adds a source and queries are about finding the smallest non-disabled source reachable from a given node.
Although D1C was really hard for me, still it's quite nice to finally reach gm
Is it too hard to post editorial for this contest?
Don't blame Gellyfish! Here: https://codeforces.me/blog/entry/143418
Why so many downvotes? I think it's a great contest with themes.
Hi, my submissions for this round has been skipped! this is the message I got
Your solution 322239991 for the problem 2116C significantly coincides with solutions Prady/322211648, Siddarth_MSR/322229699, mehul1512/322239991, Rafat_Kabir/322252055, AlterAB/322290280.
However, the coinciding code is already published on GeekForGeeks- link
pls upvote so I dont lose rating:(
Hi
My submission to the problem 2115C has been skipped due to similarity with some other submissions. However, that is because I had used a code snippet from GeeksForGeeks, published before the commencement of the round. Here is the link:
https://www.geeksforgeeks.org/minimum-length-of-subsequence-having-unit-gcd/
As it can be clearly seen, the article was published in 2023.
Please look into it Gellyfish errorgorn
Thanks!
Hello,
My submissions for the round got skipped because of similarity with some other submissions on problem 2116C. Your solution 322229699 for the problem 2116C significantly coincides with solutions Prady/322211648, Siddarth_MSR/322229699, mehul1512/322239991, Rafat_Kabir/322252055, AlterAB/322290280.
However, that is because I had used a code snippet from GeeksForGeeks, which was published before the round started. This is the gfg link: https://www.geeksforgeeks.org/minimum-length-of-subsequence-having-unit-gcd/
Please look into it Gellyfish errorgorn
Thanks.
Dear Codeforces Team,
I recently received a message regarding a significant coincidence detected in my solution (Submission ID: 322252055) for Problem 2116C in Codeforces Round 1028 (Div. 2). The message indicated a potential rules violation due to similarity with other participants’ submissions. The message I received was:
"Your solution 322252055 for the problem 2116C significantly coincides with solutions Prady/322211648, Siddarth_MSR/322229699, mehul1512/322239991, Rafat_Kabir/322252055, AlterAB/322290280."
However, that is because I had used a code snippet from GeeksForGeeks, published more than 2 years before the commencement of the round. Here is the link: Minimum length of subsequence having unit GCD.
Clearly, according to the post regarding Third-party code by MikeMirzayanov,
Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1.the code was written and **published/distributed before** the start of the round.Please have a look into this Gellyfish errorgorn MikeMirzayanov.
Thanks!
why in test case 1 in C div1(Gellyfish and Eternal Violet) is said "Otherwise, if the sword does not shine in the first round, she will attack monster 1 in the first round. For the second round:" how about Gellyfish choose not to attack