Hello, Codeforces!
I am pleased to invite you to participate in Codeforces Round 899 (Div. 2), which will be held on 25.09.2023 17:35 (Московское время).
All problems were written and prepared by me.
You will be given 5 problems, and one of them is divided into two subtasks. You will have 2 hours to solve them.
I would like to thank:
irkstepanov for excellent coordination and Russian translation!
Golovanov399 for providing useful feedbacks.
kizen for helping me much with one problem of the contest.
ko_osaga for Nutella testing.
leinad2, Numbering, qwerasdfzxcl, kizen, Golovanov399 for Red testing.
Kaling, Mingyu331, chaeyihwan, Kawaii2DIdolOfGSHS, azberjibiou, mjhmjh1104, DELTARUNE, wuhudsm, as_dfsdf for Orange testing.
unordered_map, alex0211, gs20036, namolbbaemi, eeeDA, nlog for Purple testing.
andyandy, JaewonOh, kongum, Coruncanius, ez_code, fs_edge, chromate00 for Blue testing.
Hanlana18, papergundam, sjmjys954646 for Gray testing.
MikeMirzayanov for great Polygon and Codeforces platforms!
And last but not least, You for participating in the round!
Score distribution: $$$500 - 1000 - 1500 - 2000 - (2000 + 2000)$$$
Good luck and enjoy the round!
UPD: Editorial is out.
UPD2: Congratulations to the winners!
Official Contestants
Official + Unofficial Contestants
Auto comment: topic has been updated by windva (previous revision, new revision, compare).
As a tester,problems are awesome.Hope you enjoy it :)
We hope that the contestants will not spend a lot of time just reading the meaning of the questions.
As a tester, I did not know that the contest would be scheduled this early. Well, that was quite early, I guess.
Anyways, the problemset was enjoyable. Everyone, good luck on positive $$$\Delta$$$, and I hope you enjoy the contest as well (regardless of the $$$\Delta$$$).
I also didn't. I was thinking of late October or so lol
So we expect late editorial?
Editorial is out now.
As a tester, the last problem is the best problem I've seen recently. Good Luck and Have Fun!
As a tester, I can't agree more.
As a tester, windva is handsome, so please participate.
Will there be a problem based on cuteness of windva ? ( i'm not sure just guessing)
As a tester, I personally did like problem D and E. Hope you do not give up early and have a good result
As a participant, windva is god. :blobaww:
da xing hao
As a tester, I really enjoyed testing this contest.
The problems are creative, and solving these problems require a variety of approaches. Each problem has its unique style, and will broaden your perspective to the next level. Plus, they are fun to solve!
I saw windva putting a tremendous amount of effort and time to run this round. Moreover, windva is really cute, so please do consider participating actively.
Big thanks to windva, for creating this beautiful set, allowing me to test it, and for being cute.
This should be hackable, but I'm too lazy to write a testcase against it.
224983900
Seems like you're in the wrong post XD
Wish me luck I hope this contest is another step into turning gren
We are ready
Good luck everyone! Hope you get your color-up!
You have to get red to become purple :)
Win some, lose some :) What's important is learning from your mistakes
I hope this will be an unrated contest for me :)
How did you solved A,B,C,D all of them in just 1 minute in last educational round?
I solved them in 38 minutes and submitted at once.
Why?
I'm guessing, to avoid losing rating, in case you can't solve enough tasks to get positive delta?
As a participant, windva is 大. very good at 三行詩. :blobaww:
Big handsome guy windva orz
2 out of 3!
Hope to solve at least one problem :)
Can anyone please explain why when I read input this way it is not accepted : 225037625
but when I read it this way it is accepted : 225042785
I thought both of them the same and I even runned debug with the first test case for the first submission and it just works like how I expected
in first case you are breaking the for loop and not taking the complete input which gets carried on to the next tc
I'm kinda new here, is this round rated?
All codeforces rounds are rated, unless said otherwise in the announcement.
Hope that I can solve problem D :)
rated for the participants with rating lower than？
The round is rated for participants of rating lower than 2100(Master).
how do I become a tester for some codeforces round?
I invited some of my acquaintances to test the round, and the coordinator invited in more testers. I don't know exactly from what route he invited them.
Guys I won't be able to participate if I just didn't will that effect anything after I registered?
If you don't submit anything during the contest, then your rating won't change. You can cancel your registration anytime before the contest starts tho
I hope everyone reaches their goal <3
I couldn't solve C, should I commit suicide?
Lol, thought of killing yourself over a petty puzzle.
I wouldn't if it wasn't solved by so many people.
Was C really that strikable. it would not have striked even if i had given a month to it
Cat, it was just a joke.
Why dfs in D is so slow. I got TL int $$$O(30 \cdot n)$$$, changed $$$30$$$ to $$$21$$$ and it's still $$$2.7$$$ seconds...
Intended solution probably solves all bits at the same time
Oh, it's interesting! I know only solution for each bit separately.
I am going to break my 1666 rating :))
Any hints for C ?
If you fix the leftmost element which you will remove, then what would be the answer?
what an elegant solution you've coded!
Hmm, but can't you then proceed to remove even more elements down the line? Or would that not be beneficial since there's no use in flipping the parity twice?
Work backwards. Start from $$$i=n-1, ..., 0$$$. There are 4 cases: The $$$i$$$ location is odd or negative, and for each, it can be $$$\geq 0$$$ and $$$<0$$$. For each case, you can do a greedy decision.
you can do DP. Check my solution.
You can get answer by checking first two element of array(obviously n>=2).
Why the skill difference between D and E so high everytime. btw how to approach E anyone?
This second question that came, well in the third test case why was the output 6 and not 7? You could include 1 too in the set.
But then the set would contain everything, which isn't allowed.
"Find the maximum number of elements in an attainable $$$S$$$ such that $$$S \ne S_1 \cup S_2 \cup \dots \cup S_n$$$."
What is the logic for B? Thanks.
Store all element in map that represent union of all, after that for each element of map see which sets include that element and remove that set. which map element results in lowest removal is answer. here's my solution --> https://mirror.codeforces.com/contest/1882/submission/225124593
Can you please explain in more detail?
mp is storing union of all(you can use set too) after that i am seeing that how many element will remain if i want to remove all sets which contain that element. which element removal gives most element remain is answer , temp map(m) is storing the current union.
You have to exclude at least one Element from the answer, so fix this element and add all the sets that doesn't contains it.
How do you solve D? (Hints)
tree dp / rerooting
I can solve it with tree DP easily for one root, but what is this rerooting trick you mention? Any links?
If you know $$$dp[u]$$$ and there is an edge $$$(u,v)$$$, you can find $$$dp[v]$$$ in $$$O(1)$$$ https://usaco.guide/gold/all-roots?lang=cpp
Think about how dp values change if you change the root to an adjacent vertex (old and new roots are connected by an edge). You'll notice that only the dp values of the old and new roots change, and this change can be calculated in $$$O(1)$$$. Now, you can just do a simple dfs traversal of the tree and always move the root when going up or down. All vertices will be the root at least once during this, and you can store those answers in a separate array.
If you have the formulae to calculate dp for any parent from it's children then you can also use the same formulae to reroot the tree to the child from it's parent. Keep doing it recursively in dfs and calculate answer for every node
A ok
B Unimaginably bad
C Unimaginably bad
D Unimaginably bad
E1 Unimaginably bad
E2 out of my skill no comments
total: 6.9/100 (fail)
abort_dodger_3000
For me, it's like
A ok
B out of my skill no comments
C out of my skill no comments
D out of my skill no comments
E1 out of my skill no comments
E2 out of my skill no comments
total: 93.39/100
Quite similar problem to problem D : 1187E - Tree Painting
It's basically the same idea
B's pretest were pretty weak, probably gonna fst a lot
:)
Why TLE? It is $$$O(n)$$$
Submission: 225143030
It seems like O(20n). We allowed fast O(20n) solution, but the intended solution is actually O(n) and not guarantee slow O(20n) solution to get AC
Are $$$3$$$ seconds not enough when $$$n = 2 \cdot 10^5$$$? It is C++!
I don't think it really makes sense to allow a slower solution only if it's implemented efficiently. I think you should've either allowed the slower $$$O(20n)$$$ to pass easily or changed to like $$$a_i < 2^{60}$$$ and a 2 second TL to only allow the fast $$$O(n)$$$.
I guess it was quite hard because diverse languages (ex. Kotlin, python) have to be considered. We had to guarantee O(n) solution implemented by Kotlin to get AC
I agree with your point.
However, we had to consider slow languages, so had to set TL at least 3s. And due to this, we intended to pass O(20n) instead, because we thought it would be impossible to block O(nloga) in TL 3s even if we increase the constraints. In fact, there were O(20n) codes which worked in nearly 1 sec so I thought it wouldn't depend on the subtle difference in code's efficiency.
Thanks for your feedback :)
Usually, a constant of $$$20$$$ is too small to distinguish between two solutions. So it was the right decision not to block $$$20n$$$. But maybe it would be better to increase the TL? I don't think it's easy to squeeze $$$O(n^2)$$$ into this problem in any reasonable time, even on C++.
By the way, thanks for problem C, I really enjoyed it!
You can check my O(20n) solution. which works at 1.3-1.4 seconds. 225156423
A: We can solve by greedy: Let b[i] be the minimum it can be, which means, if a[i]==b[i-1]+1 then b[i]=b[i-1]+2, otherwise b[i]=b[i-1]+1.
B: For each $$$t \in \bigcup_{i=1}^{n} S_i$$$, assume $$$t \notin S$$$, we can let $$$S = \bigcup_{t \notin S_i}^{} S_i$$$, and take it as a candidate of answer.
C: Observe that if we removed the i-th card, then for j>i we can get max(0, a[j]) score by appropriate order of operations. Assume the most top card we removed is i0-th card, then the answer will be a[i0]*[i0%2==1] + sum(j>i0)(max(0, a[j])).
Assume we need to remove card denoted by '*' get scores from cards denoted by 'a'(for odd position) and 'b'(for even position):
...*a..b.bab...b..a..b
We can do operations like this:
...*a..b.bab...b..a..b -->
...*a..b.bab...b....a -->
...*a..b.bab...b.... -->
...*a..b.ba...a.... -->
...*a..b.ba....... -->
...*a..b.b....... -->
...*..a.a....... -->
...*..a........ -->
...*.......... -->
.............
D: When u is the root, it's useless to do operation on u, and for each other node v, we need to cost (a[parent[v]]^a[v])*size[v] to make a[parent[v]]==a[v]. Therefore, if we let 1 be the initial root of the tree, and u is the parent of v when root is 1, then node v will contribute (a[u]^a[v])*(n-size[v]) to the answer of nodes in subtree of v, and contribute (a[u]^a[v])*size[v] to the answer of other nodes.
E1: We can use 3 operations to swap two numbers in the permutation: [I]*s*[II]t[III] --> [II]*t*[III]s[I] --> [III]*s*[I]t[II] --> [I]t[II]s[III], and do 2 opartions on 1, n will cause no change. Therefore, we can build operation sequences for p[i] and q[i] separately, and if the parity of lengths of them is the same, we can fill (1, n) to operation sequence of p[i] if it's shorter, or fill (1, m) to operation sequence of q[i]. Otherwise, if n is odd, we can add n operations on 1 for p[i], similar for m is odd. If both n and m are even, the answer doesn't exist.
Assume we do operation on position i, there are i-1 numbers before and n-i numbers after. Therefore, the change of the parity of inversion number will be (i-1)+(n-i)+(i-1)*(n-i)%2, and when n is even, the parity of i-1 and n-i will be different, so the parity of inversion number will be changed after every operation. Therefore, if n and m are even and the initial parity of inversion numbers of p[i] and q[i] are different, the answer doesn't exist.
How did you arrive at the answer for D?
since doing xor on a whole subtree is kind of like doing suffix xor on an array, you can consider do something like difference array, that is, make every edge $$$(u, v)$$$ have a weight of $$$w[u] \text{^} w[v]$$$, then the weight of $$$v$$$ is indeed the xor of path from root to $$$v$$$(except the root, but it is not important), and the problem become "Make all edge have weight $$$0$$$, in one operation you can make an edge's weight xor with $$$c$$$", then it is obvious that xor edge with it's weight is optimal.
Thanksss
Additionally, i wanted to ask is it a common technique to break down an operation on a subtree as an edge.
.
Can you explain why?
My understanding was as follows: If you XOR the root and a certain set of bits get flipped in root's value, then those bits will get flipped for the entire subtree (since operation is on the entire subtree, not just root). So, essentially the problem remains identical just with the flipped bits i.e. you want to match those bits in the root's value with values in its subtree using the XOR operation on the subtree.
Consider an example with only 1-bit numbers: If root's value is 1. And its subtree has node1=0, node2=1, node3=0, node4=0, node5=1. Then, if you apply operation on the subtree rooted at the root itself, these numbers will become root=0 and subtree will have node1=1, node2=0, node3=1, node4=1, node5=0. Clearly, the nodes in subtree which had different value compared to root still remained the same before and after the operation.
For D[problem:1882D], the conclusion that it is useless to do operation on the root (to minimise cost) seems obvious.
However, in your statement/solution, are you assuming that for a node v to become same value as root, the value of node (v) has to (at some point) become equal to the original value of its immediate parent after a sequence of operations? If so, how can we prove it for optimal cost?
Tried DFS and Rerooting for each bit in D, got TLE, shouldn't
20 * npass?No need to do it for each bit. If you want to make a whole subtree equal then you need to make all children of the root equal to root otherwise its not possible. There is no way we can change the root value to be equal to the value of the child without changing the child.
Please take a look at this comment
The contest is maybe very good But it DID NOT FIT ME. :( problem D is DP. I am not good at DP at all:( especially on tree :(:( E1 WA#10, mistake, didn't pass pretest until contest over. :(
problem C is fun. feel good over A B C.
How did you reach purple without a stronghold on dp?
Dp on trees is more annoying than normal dp. I struggled with the code a bit too
For Problem C, DP was way straight forward than the greedy method for me. DP Solution
Thanks for this, I really need to get better at dp lol-
Bro skill issue tbh
This is the method I used as well in testing. In fact I did not know there is a greedy solution until today.
I tried the same approach but didn't bass the example.
It's much easier to think about Dp solution for problems like this than to think about a greedy solution -$$$ at $$$ $$$least$$$ $$$for$$$ $$$me$$$-.
In your solution, can you explain the calc(v,i+2,1)+v[i] case when the parity is odd?. I was thinking on the exact same grounds but cannot understand why this is needed.
Let's say we are on an odd position i now. If we take this value right now and if there exists another value at position i+2 it will become even after the operation.
Example: [1,-5,2,-3,5]
After taking the element at position 1: [1,-5,2,-3,5] > [-5,2,-3,5]
Here you can see that the value 2's position has changed from being ODD to Even.
But if we take the element at position 3 first: [1,-5,2,-3,5] > [1,-5,-3,5]
As you can see the position of the element 1 has not changed from being ODD to Even. So we can take this element even after taking the 3rd element.
So, for that it is optimal to take the value of (i+2)th element before taking ith element. So by calc(v,i+2,1), I am saying that "I will take the ith value after taking the (i+2)th value."
I hope it clears up the idea behind it.
Hi bro, still did not understand this line - ->So by calc(v,i+2,1), I am saying that "I will take the ith value after taking the (i+2)th value
why we need to check this for only i and i+2th element. like example 1 -2 -2 -2 4 -2 -2. Here we can take 4 and then 1 as well which is not at position i and i+2, How is this case handled?
It is a recursive function. And it has 3 branches for odd positions.
(1) Take the current value and make the next value ODD and calculate from there.
(2) Do not take the current value and calculate from the next position.
(3) First calculate from the i+2 th value, then take the current value. So, making no changes to the positions of the next elements.
And it has 2 branches for the even positions:
(4) Remove the current value from the array and make the next position even. And calculate from there.
(5) Do nothing to the current value and calculate from the next position which is an ODD position.
So for the case you have mentioned we follow these sequences:
3->2->5->1
The numbers represent the type of operation at each time stamp.
it was a very good contest and I do learn a new thing from D problem thank you Windva for writing these Masterpiece
ACCEPTED!!!
He already agreed with the results, it's his big old brother who is seeking attention
Why multitest in D???
The system tests for E1 are weak. A test with two decreasing permutations of length 2500 causes my solution to TLE. I'm not sure why some tests were included for E2 but excluded for E1, since I'm pretty sure test 87 from E2 would have caused the same TLE on E1 (the code that causes the TLE is unchanged between my submissions). This also seems like the most intuitively "hard" case, so I'm surprised it wasn't included early on among the pretests for both versions of the problem.
D is too similar with Leetcode 834. It is possible to "transform" 834's solution to D's solution by just adding weight of the egdes by a[u]^a[v]
Leetcode 834 solution (in Chinese version) :https://leetcode.cn/problems/sum-of-distances-in-tree/solutions/
My solution: https://mirror.codeforces.com/contest/1882/submission/225158821
To have that transformation you need the main idea anyway, so I don't think this is a major issue.
C was too much ad hoc for me, fuc*** my whole contest :(, D was straight kinda straight forward, submitted just after the contest was over :(
Problem B Is too much for div2B
Video Editorial For Problem A,B,C,D
My DP solution for C is not working. Can anyone plzz check?
int f(int i,bool flag,int a[],int n,int dp[][2]){ if(i>=n) return 0; if(dp[i][flag]!=-1) return dp[i][flag]; if(flag==1 && i%2==0){ return dp[i][flag]=max({a[i]+f(i+1,0,a,n,dp),f(i+1,1,a,n,dp),f(i+2,1,a,n,dp)+a[i]}); } else if(flag==1 && i%2!=0){ return dp[i][flag]=max(f(i+1,0,a,n,dp),f(i+1,1,a,n,dp)); } else if(flag==0 && i%2==0){ return dp[i][flag]=max({f(i+1,0,a,n,dp),f(i+1,1,a,n,dp)}); } else if(flag==0 && i%2!=0){ return dp[i][flag]=max({a[i]+f(i+1,0,a,n,dp),f(i+1,1,a,n,dp),f(i+2,1,a,n,dp)+a[i]}); } }
int32_t main(){ fio; // createsieve(); int t; cin>>t; while(t--){ int n; cin>>n; int a[n]; FOR(i,0,n) cin>>a[i]; bool flag=1; int dp[n+1][2]; memset(dp,-1,sizeof(dp));
int ans=f(0,1,a,n,dp);
cout<<ans<<endl;
}
Super Fast Delta Delivery!
In problem C i got AC but i don't know if my idea is good or just lucky
practically i maintain a multiset where i keep the values that i took
a priority queue where i keep the value i didnt take but are on odd positions
a cnt where i mantain the values i didnt take on even positions
i have a value tura that means if i have to look on even or odd positions , because i deleted a even number or odd number of numbers before
so practically when i am on a odd position i see if its > 0
if it is i take it and tura becomes 1 -tura
if i am on a even position i see if i took a position before if i did and this one is bigger than 0 i take this position as odd also
if i didnt i will see if i have cnt > 0 if yes it means i can take it if its bigger than 0
then if i cant do that either i see if v [ poz ] > min ( multiset.begin() , priority_queue.top())
if yes i take it and i give up a element to the left
Can someone pls explain this solution by Jiangly for problem B? https://mirror.codeforces.com/contest/1882/submission/225097723
I hope this commented code helps:
225190010
The variable Or is used to store the union of all the sets. We enumerate the number $$$x$$$ to erase for the answer. Then it's clear that all sets containing $$$x$$$ should not be selected, and we can select all other sets . So we can know the largest union set to get which doesn't contains $$$x$$$.
For code implement, uses bitmask to record each set, and some bit operators to check the conditions above.
Since October 2022, I have participated in 3 CF Rounds, all in May, this year. After that time this one was the first. This year I participated in the IMO and IOI. Hence, during the last few months, I was training for both IMO and IOI. I started training for the IOI after the IMO. During that period I have not participated in any CF Round. I was virtually participating in different 5-hour IOI-style contests, mostly IOI. To understand the problem statements clearly, I read them slowly. And now I think I am not in my best form of CF-style contests. Fortunately, I managed to solve A, B, C, D and to write the code of E. After I finished coding, then finding and fixing bugs, around a minute was remaining for the contest to end, so I quickly tested my code on the test cases available in the statement and sent the code. But… I got WA on TEST 1. What?… and after a few seconds of checking my code, I found the following:
I wrote this to locally debug my code to find bugs, and forgot to change it into a comment… I quickly fixed that, but it was already late for a minute… The contest was over… During the system testing I hoped that my idea of the problem was wrong, or that there was another bug in the code (so that the lateness of 1 minute wouldn't change anything), but, fortunately or unfortunately, after the end of the system testing, I sent the fixed code and got AC… WOW… I thought I would be more relaxed should I get WA.
P. S. By the way, the Honourable Mention from the IMO and Bronze medal from the IOI, which I earned, made me feel happy that a story like this happened during the regular round but not the official contest.
Editorial please!
In problem D, how to prove that in the optimal cost solution, all values in the subtree of a node v should become equal to the original value of the node v itself after certain operations?
Assume you would make an operation on the node $$$v$$$. Then all the nodes in the whole tree will be $$$xor$$$-ed. If you only look at one bit position, that means either we $$$xor$$$-ed with $$$0$$$, then nothing changes. Or we $$$xor$$$-ed with $$$1$$$, then all bits $$$1$$$ changed to $$$0$$$-s and vice versa, so the differences are still the same. We did not get closer to our goal. So using an operation on the root is futile. This means all numbers will be equal to the number in the root.
I'm getting WA on test 5 E1, it says:
Checker Log
wrong answer incorrect A
what does that mean?
Thank you to the author and helpers for the contest! I liked all the problems except D, which I felt was standard and boring, and E2, which I can't solve. C and E1 in particular I like a lot. Thanks again :)
C2 (:
Thnx
it will be [1,2,4,6,7] not [3,4,5,6,7]
DP Solution for C, considering
dp[i][0][0] => not removing the ith index as an even index from the start,
dp[i][0][1] => not removing the ith index as an odd index from the start,
dp[i][1][0] => removing the ith index as an even index from the start,
dp[i][1][1] => removing the ith index as an odd index from the start,
dp[0][0][1] = max(0ll,a[0]);dp[0][1][1] = a[0];
for(i=1;i<n;i++){ ll x,y ; x = dp[i-1][0][0]+max(0ll,a[i]); y = dp[i-1][1][1]+max(0ll,a[i]); dp[i][0][1] = max(x,y); x = dp[i-1][0][1]; y = dp[i-1][1][0]; dp[i][0][0] = max(x,y); x = dp[i-1][1][1]+a[i]; y = dp[i-1][0][0]+a[i]; dp[i][1][1] = max(x,y); x = dp[i-1][1][0]; y = dp[i-1][0][1]; dp[i][1][0] = max(x,y); }submission — 225203776
hi...why are you adding max(0,a[i]) for computing dp[i][0][1]
Because initially left positive integer at odd position can be collected afterwards performing necessary operations on right
oh yes..Thanks a lot
can anyone explain B to me??
I understood that we need to opt out the set with least no of unique elements wrt other sets,but how to implement this.
For me I just used the fact that all elements <= 50 so I tried union of every set not containing X for every X in [1, 50], if that union if not the same as union of every set then it works.
Hi, can someone tell me why the following code gives me a runtime error (I ran it in an IDE outside of Codeforces and no RTE was picked up). Thanks.
Really fun round ngl
I and wxy_is_a_dog/2255153050 had studyed the Replacing DP，and we studyed https://www.cnblogs.com/wlzhouzhuan/p/12643056.html this blog.So our solutions have something in same by accident.
I got a message stating that my solution to the problem 1882C - Карточная игра coincides with qilby's submission (both submissions: 225107761, 225130187). The submissions are very similar (and what's even funnier, our nicks are also pretty similar), but the coincidence happened only due to how short the solution to that problem was (all variable names used there are pretty standard like $$$s$$$ for sum and $$$ans$$$ for answer or $$$ll$$$ for long long type). Moreover, I've submitted the solution $$$\approx$$$ 30 mins after De_Coder so it would make no sense to take that long if I had been cheating. The solution didn't use any data structures/advanced algorithms hence I didn't use any code written before the contest.
MikeMirzayanov
For Question B, Set and Union. Test Case 3.
s2 U s3 U s5 = {1,3,5,6,8,9,10} but the test case missed 1. i.e s2 U s3 U s5 = {3,5,6,8,9,10}. Why is 1 missing for test case 3?
The answer for test case 3 should be 7 right?