Γεια σου (Hello), Codeforces once again!
Adam_GS and I are glad to invite you to participate in Codeforces Round #912 (Div. 2) which will take place on Nov/30/2023 19:35 (Moscow time). Note the unusual start time of the round. As usual, this round will be rated for participants with rating lower than 2100.
Problems were created and prepared by Adam_GS and me. We tried to make them interesting, with short and clear statements. We hope that you will enjoy them!
I would like to thank:
- ScarletS for amazing coordination of this round.
- Adam_GS for joining as an author after testing the contest.
- fishy15, Andreasyan, phattd, Murinho, irkstepanov, wuhudsm, Ari, satyam343, Qualified, nyaruhodo, Trumling, Earlyamazon, freedommo33, jeroenodb, FiniteMoves, czauderna, m.szeliga, Piokemon, Marky, jerzyk, jamjanek, t.kwiatkowski, Saudi, revanth2002, htetgm, purp4ever, nor for testing the problems and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.
You will be given $$$6$$$ problems (and one subtask) and $$$2$$$ hours and $$$15$$$ minutes to solve them.
The score distribution will also be announced shortly.
Good luck and have fun!
UPD1:
Score Distribution: $$$500-1000-1500-(1500-2500)-2250-3500$$$
UPD2:
UPD3:
Congratulations to the winners:
Div2:
Div1 + 2:
As a tester,the problemset is superb!Hope you enjoy it :)
As a tester , I wound recommend to read as many problems as you can
As a tester, I would also recommend solving as many problems as you can.
As a participant, I hope I can do both.
Nice to see a round from a person(Theo830) who was sitting to my left on IOI2023 :) And a Person(Adam_GS) Against whom I played Table tennis :))
orz
I had the privilege to play ping pong with Adam_GS too!
I had the privilege to tylko jedno w glowie mam Adam_GS!!!
I had the privilege to be in the same team with Theo830 orz xD. Unfortunately i didn't meet Adam_GS (Maybe next year)
As a tester i can say that the problems are fun and interesting with a Cypriot twist ;)
As a Cypriot I can say you were right about both :)
Good luck everyone ^_^
Tomorrow I will understand how bad doing contest late(like Chinese).
I might give this round and solve D1-D2
According to score distribution, D2 >> F .
You meant D2 > E ?
No, D2-4000 , F-3500
As a tester, I wish you all good luck!
As a
testerCypriot, I hope that statements are short and pretests are strong, making our tiny island proud!ps. I will be competing so if I lose rating Theo830 pls make it unrated
Dremix10 orz
Dremix10 orz
Dremix10 orz
Yooo Mihai orz (Coaie)
Mihai orz (Coaie 2)
Dremix10 orz
Dremix10 orz
Dr. Emix10 orz
*Clarification Dremix knew nothing about the troll on problem C which made it 100 times funnier seeing his reaction xD
As a tester, I confirm the problems are interesting... hope y'all have a positive delta!
Div.2- Fs are usually easily solved by most IGMs in contest, furthermore, they are usually GM level. I hope that such a group, to whom Earth puts all their faith in to solve any problem, are not only lowly GMs, so this should be factually wrong
The fact that there is no account with username avengers makes me sad.
My sleep and the contest are at crossroads today. I will choose the contest.
GLHF
Guess — D1,D2 can be dynamic programming with varying constraints.
this aged well
As a tester
orz
As a tester, certain problems are, for the lack of a better word, based.
mohdabuzaid15
At least i can blame sleep deprivation if i mess this round up
The start time is 00:35 for me, so I can sleep well
The start time is so late to me: 23:35=)), I can't sleep tonight if I fail in this contest
The timing of this round is awful for Chinese students, I hope I won't be late for class the next day
Let's compete and see who do better this round tomorrow my school too
he won
contest >> sleep >> university exam
Agreed! Somehow, my love for contests grows twofold during exams. With an exam tomorrow, this contest will surely be my doom, but a beautiful doom nevertheless..
literally me rn. I've got an exam tomorrow and 0 motivation to study
contest >> sleep >> The first class at 8：00（+8）
The first, I will be giving a contest at 10:05pm(India)
Hi
Hoping to become a Pupil after today's contest
As a farmer, I mean tester.
Problem D1
damn
W cyprus round
orang soon?
Nice problems. I got 5 wrong answers and wasted 1 hr for a simple integer overflow bug in D, could've been a good contest for me.
How to counter it?
There are a couple of ways:
Use 128 bit integers if you can, though I wouldn't recommend that as a great practice as such.
Consider the given problem: I counted the "sum of required moves" and compared that to the number of allowed moves. Here, individual elements could take upto ~1e18 moves for large bits and considering that there are ~1e5 numbers, the sum could be as large as ~1e23. One way to avoid the overflow is to stop adding to the "required" variable once it exceeds the "allowed (k)" variable, just add an if statement (or alternatively, use min(required, k + 1)).
Keep a backup of the remaining
kand do the operations for each bit in an online fashion, i.e, don't wait to accmulateneedfor each element and then check if $$$k \gt need$$$. Instead, keep on subtracting from $$$k$$$, and track whether the operation was a success or not. If it wasn't, overwrite it with the old $$$k$$$.It is essentially the same as finding a missing number from the set $$$1, 2, 3, \times n$$$. If you do
n*(n + 1)/2 - existing_sum, you face overflow issues, but if you do it in an online fashion, where you run a loop, and in each iteration, add $$$i$$$ but subtract $$$a[i]$$$, it'd work.Since all numbers start < 2^20, can't we just check if we have enough operations to get all numbers to 2^20? If so, isn't the strategy to split the remaining operations equally among the elements, i.e. the max would be (2^20 + (remaining ops)//n)? I thought there should be no need to check "required moves" for bit spots above 20, but maybe I'm missing something.
Consider a single element, say, 1. It is true that it starts with one bit, but if $$$k = 10^{18}$$$, then new bits would appear.
Can relate so hard to this ;_; I faced the same issue, assuming you're talking about the "long long overflow".
But how in this particular problem long long can overflow? Long long is 2^64
no of operations req to set ith bit in all elements.
yeah, i get it now, thanks
Same deal here, but I got FST as my punishment.
$$$E$$$ was easy to solve, but hard to implement. Thanks for cool tasks!
UPD. After checking some submissions, i can say that i am just noob and E wasn't hard to implement:)
Shit! I dint check E after seeing D2
balanced contest with good problems
What the fuck is a pretest number 15 anyway
Man I had such high hopes for D2, unlucky
What was your approach? It's clear that we keep the amount of steps for each i to get all numbers to i-th bit and iterate from the leftmost until we can subtract that amount from k. But then how do you find the remainder bits that also will be part of the answer?
See this
I suspect its the first max constraints test or similar.
I coded a weird approach without realizing it was actually still $$$O(q \cdot n \cdot \log(10^{18}))$$$ in the worst case and it reaches pretest 15 before failing.
What is weird, even if it is some maxtest, my verdict is not TL
Unless I have overflow somewhere in my code (unlikely)
What was the approach for C?
i solved it using suffix array
if the suffix sum is negative then it is better to merge it with previous else keep it in a new subarray
ah damn I feel like I shoulda thought of that. Thanks
Nice E!
Solved A,B and C. But I feels C is slightly easier than B
Problem C and Problem D in CF EDU 66 are the same actually, isn't that enough to make this round UNRATED?
include<bits/stdc++.h>
using namespace std; int main(){ int n, k; cin >> n >> k; vector v(n + 1), cs(n + 1), csSuffix; for(int i = 0; i < n; i++) { cin >> v[i]; } long long int suffSum = 0; for(int i = n — 1; i >= 0; i--){ suffSum += v[i]; csSuffix.push_back(suffSum); } long long int sum = suffSum; csSuffix[csSuffix.size() — 1] = -2e18; sort(csSuffix.rbegin(), csSuffix.rend());
for(int i = 0; i < k - 1; i++) { sum += csSuffix[i]; } cout << sum << endl; return 0;}
include<bits/stdc++.h>
using namespace std; int main(){
int t; cin >> t; while (t--) { int n; cin >> n; vector<long long int> v(n + 1), cs(n + 1), csSuffix; for(int i = 0; i < n; i++) { cin >> v[i]; } long long int suffSum = 0; for(int i = n - 1; i >= 0; i--){ suffSum += v[i]; csSuffix.push_back(suffSum); } long long int sum = suffSum; csSuffix[csSuffix.size() - 1] = -2e18; sort(csSuffix.rbegin(), csSuffix.rend()); for(int i = 0; i < n - 1; i++) { if (csSuffix[i] > 0) sum += csSuffix[i]; else break; } cout << sum << endl; } return 0;}
They are slightly different. One asks for a specific number of sub arrays and the other doesn't.
They aren't the same actually (today's C allows for any number of subarrays, that EDU D requires $$$k$$$ subarrays), but the solution ideas are still almost the same (reduce the problem to sum of suffix sums).
But no, rounds aren't made unrated because of repeated problems. Only copied problems make rounds unrated. If the problems were similar on accident, the round is kept rated.
Even if they were the same, I don't think the contest would be unrated. In contest 1898, B is a classical problem appeared on other websites and D is an easier version of https://codeforces.me/contest/1513/problem/F. But the contest is still rated.
Stop it. There are more than 20000 problems, for each problem you can find simular. But if you really search every problem, for which reason you participate in contest...
Come on!! The solution to Problem B was uploaded on Youtube around 40 minutes before the contest ended. That would explain the sudden rise in submissions (700+) on Problem B in the last half hour. Disappointed ://
so I can assume, you've googled it........
Not sure about visiting Cyprus after this contest
Great problems! Keep it going. Would love to see a div1+div2 from you next time!
We are planning to make a div1+2 together soon™
Missed Specialist just for a minor fuckup!!
E is a really cool problem, I love how the winning condition is so simple and easy to prove.
It reminds me a bit of this problem: 1549F1 - Gregor and the Odd Cows (Easy), which has some similar ideas.
Any hints for D2?
I tried separately calculating costs to set all bits going from highest to lowest, then calculating the cost to set all lesser bits after I set the i-th bit in all numbers.
For yet unknown to me reasons, this approach does not work, or maybe I haven't anticipated overflow somewhere in my code.
Yeah, I might have a suspicion why this solution won't work. So when we are searching the first bit that the final answer will contain, we do not consider that some of the numbers have it set to 1. That's why when we calculate the "lesser" bits, we do not actually sure if all the numbers have a suffix of zeros. (cause from some of them we did not subtract anything at all)
Logic of my solution is something like this:
So, if some bit has come before, I either don't do anything with the number at all, or that bit has to erase any lesser bits anyway
I couldn't come up with a counter example myself, I don't know if this is the part in my solution that is wrong, but I did have such concerns during the contest (but I chose to believe that my guess is correct)
It sounds like this solution is $$$O(32qn)$$$...
It's actually only $$$O(64^2 \cdot N + 64 \cdot Q)$$$
Where $$$O(64^2 \cdot N)$$$ part is precalc
I've explained it a little bit messy, but hope you've gotten it.
If you change number x at some bit i, then you need to update the cost function for other bits
That's why I have an array
costs— initial cost to set bit $$$i$$$ in all numbers, and 2D arraypost_costs— the cost to set any bit $$$j$$$ that comes after $$$i$$$UPD.: nvm, I see how my solution is failing, I can't just calculate costs taking the initial bit that I've set and looking at the costs to set lesser bits.
How are you handling this post_costs, I can't figure out anything except O(nlogA) per query.
I tried doing precalc, but the way I'm calculating the costs later on when answering the queries is not correct.
I had the idea to optimize the D1 solution using a bitwise trie. Same idea, but you traverse the bitwise trie which contains some additional information.
I didn't manage to implement this, so could anyone say whether this is the right idea?
No. I thought about this idea on the contest and saw, that when we have to go to the left son in our trie(when we calculate the answer), we also have to know all information about all subtrees of the right son. We cannot maintain full information about subtrees of the right son, because it requires some additional memory and time :(
Oh. Well then I look forward to seeing the official solution!
Ahhhh....Thursday....watching my favorite anime characters and my rating go down....what can be better?
any hint for problem C ?
Maybe try starting from the end
what is the idea in problem C?
If you start a new subarray whose left end point is i, then the change in answer would be the suffix sum: suf[i]
Where can i find official solutions for this contest ?
they will update the contest post with editorial after some time ( hopefully soon )
you can check posts for previous contests, you will see the editorial link to understand how it looks
Okay, Thanks!
editorial is here now, please check the post
I solved B but I don't know why it works, hopefully, system test passes :D
may i see your solution?
so I just did AND of every row ( excluding the diagonal element ) and printed that as the answer after checking if it forms the grid
after this, I just tried to create another grid ( not explicitly ) and checked if it was the same as the original grid, if NO, I said it is impossible, but I don't know why it is impossible.
ok it passed, I am lucky, hopefully editorial explains it well
oh same solution as me but whats this
int and = (1<<31)-1;mean?it make you can AND in the first round of loop?
because i did this
Im not good at bitmask sry.
They are turning on all bits but leftmost bit (which is the sign bit).
oh so I started with the first member being arr[i][j] .. but it was 0 when i == 0 and j == 0 so I didn't know what first value to choose
this and value is a binary number with 31 1's in it, which is more than any number so doing AND with it will give back the input number
why is your whole row not zero for the first row.. because arr[0][0] is 0 so and first row will always be zero in your case.
sorry I'm in a bit of a hurry mb
this is my B solution here
but i do from every top and right number of M[i][i] that i just realized top of M[i][i] is the same as left of M[i][i]
Yeah same, I applied same thing and don't have concrete proof of why it works
misunderstood problem C summation (len of subarray_i) * sum_i :(
got AC in problem C without knowing what exactly I was doing LOL. Maybe it will be hacked
If you want to build intuition for problems like today's C. Theofanis' Nightmare, try upsolving 1132F: Clear the String. I was lucky to have upsolved it very recently and the idea instantly clicked :) (I've also added hints for 1132:F if you don't want to read the editorial.
Notice that in "Clear the String", you had made 2 choices on the first element, instead of guessing the first cut subarray, you were thinking small, like what happens to the first element. It could have either been cut alone, or could have been merged with some other element.
This prompts you towards a DP definition $$$dp[i]$$$ represents the answer for $$$a[i \dots]$$$. Then, you either merge the first element with its neighbor, leading to $$$dp[i + 1] + a[i]$$$, or you cut it alone, which makes you think about how to reuse the value of $$$dp[i] = 1*s1 + 2*s2 + 3*s3 \dots k*sk$$$.
Since you cut the first element alone, you would need to shift each element to the left of * by 1, hence, this leads you towards thinking of how to compute $$$2*s1 + 3*s2 + \dots (k + 1)*sk$$$ given $$$1*s1 + 2*s2 + 3*s3 \dots k*sk$$$. Hence, the introduction of suffix sums.
Submission
What is the intuition behind Problem B?
It's the fact that $$$0 | x = x$$$ and $$$1 | x = 1$$$ for $$$x \in {0, 1}$$$
This observation is enough to solve the problem.
Consider a binary array. If all elements are 1 in the matrix, then an array $$$[1, 1, \dots 1]$$$ suffices. Else, there is atleast 2 zeroes (not one, think why?). Then, if you can just find any of these zeroes, then you can notice that $$$0 | x = x$$$, hence the entire row is your answer.
You probably meant to say that $$$0 \mid x = x$$$ and $$$1 \mid x = 1$$$ apply for $$$x \in \{0, 1\}$$$.
($$$\oplus$$$ is bitwise xor, not or)
True, my bad. Fixed.
Amazing round, loved solving the problems!
Susge, but i dont see any submissions
I don't know how to code, so I solved some of them in mind.
xdd
okay
I overcomplicated C to a stupendous degree. Looking at everyone else's submissions, simply going from the back was enough. I instead viewed it as $$$\text{psum}[a_1] + 2(\text{psum}[a_2] - \text{psum}[a_1]) + 3(\text{psum}[a_3] - \text{psum}[a_2]) + \dotsc + k(\text{psum}[a_k] - \text{psum}[a_{k-1}]$$$, then expanded it to yield $$$-(\text{psum}[a_1] + \text{psum}[a_2] + \text{psum}[a_3] + \dotsc + \text{psum}[a_{k-1}]) + k \cdot \text{psum}[n]$$$,
then I iterated over $$$1 \leqslant k \leqslant n$$$ and chose the $$$k-1$$$'th minimum values of the prefix sum in order to minimise $$$\text{psum}[a_1] + \text{psum}[a_2] + \text{psum}[a_3] + \dotsc + \text{psum}[a_{k-1}]) + k \cdot \text{psum}[n]$$$, and summed them.
The way I did this was sort the prefix sum and create ANOTHER prefix sum for that prefix sum. It got pretty damn hectic.
235105543
Thank to your explanation. My friends did like you as well but I don't understand until your comment LOL. They used only about 6 minutes, whereas traversing backward cost me 1 hour to come up with
D1 using binary search?
yes, but cost function can overflow long long if not careful
can u plz explain your logic
Try greedy from highest set bit to low. If it is possible to make all $$$a_i$$$ have the bit set with no more than $$$k$$$ then do so. Here we binary search the highest bit possible, though a loop may be sufficient. Edit: I don't think it is correct though, you can try reading editorial of this problem.
Why do you need binary search? Just iterate the highest bit form high to low.
That's true. In fact, my approach is probably wrong.
Edit: I changed to loop and got accepted, my hubris :((
Legit random solution for F or weak systests? (Enjoy to hack)
Add all vertices to the set of answer. Repeat the following sufficient amount of times:
https://codeforces.me/contest/1903/submission/235123989
Hacked with a bipartite graph, when there is an edge between two nodes if they have different parity.
The answer is $$$2$$$ but there is almost no chance to find it.
Tried solving D1 using this approach: While iterating from higher order to lower order bits, say you are at bit
bit. Then, you check the current bitwise AND for that position. If it's not one, and we can make it 1, we should. So, for every $$$a[i]$$$ which doesn't have thebitposition set, we set it. To set it, we look at itsbit - 1bit. If it is set, then we need to add $$$2^{bit - 1}$$$ (i.e, we are borrowing from the neighbor while clearing the neighbor's bit). If the neighbor is not set, the cost has to be $$$2^{bit}$$$.Can anyone please point out the flaw with this strategy?
Submission
Suppose the
bit-2bit was set, then you need to add $$$2^{bit} - 2^{bit-2}$$$. In general, you need to check all the bits with lower value than the current bit, not just the next one.Ooof, how did I miss that? Thanks. Fixed Submission
I guess I got too involved with figuring out the borrowing strategy that I overlooked this simple fact: Each operation only increases the value by 1, so if we want to turn on the $$$i^{th}$$$ bit, then there is only one number that we'll reach first before others, i.e $$$2^i$$$ (pretend the higher order bits are zero). And also, there's just one strategy to go there, because $$$val + cost = 2^i$$$ implies that $$$cost = 2^i - val$$$.
Since, any number can be represented as $$$\sum 2^{set\_bit\_index}$$$, we can clearly deduce the cost is $$$2^i - \sum 2^{set\_bit\_index}$$$
Problem D1: week test case submission case:
0
I try to solve D2 with Trie but failed, does this problem solvable with Trie?
Am I right in that the only thing that matters in E is $$$(s_x \oplus s_y) \mod 2$$$ and whether there is more ones or zeros among $$$(x_i \oplus y_i) \mod 2$$$? If so, I love the problem, but I hate what it did to my rating haha
Yes.
I can't tell you how salty I am that I only got this like 5 minutes before the contest ended... It's a really nice problem though. Congrats on reaching CM by the way!
Thanks!
I got stuck in problem E because my answer is choosing "First" while the testcase says "Second" and I'm trying to figure out what is wrong in my idea while it's all correct.
So I just want to say that the most most stupid thing you can do in a contest as a problem setter is to put a testcase in a problem and say that this is not the optimal solution in the description.
I don't have to read the description cool ... and I don't have to search in all the page for a fool note.
Can't agree more! Especially comparing it to this problem. (
same here...
Pretty much in every interactive task no testcase has the optimal solution in it. Also, it's never mentioned that the presented interaction is optimal/not optimal, so I think there should be no problem.
Of course the output will not be the optimal solution, it's obvious I think. But the answer here is incorrect so this is a different case.
Interactive problems are often like this , that's why I don't really read the sample's interaction
Sounds like skill issue honestly.
good contest
Great contest and nice problems ! Special thanks for problem E :)
You can do divide and conquer on queries in d2
Crucial observation is that if we add to a certain number to make bit B on, every bit below it turns to 0, which means for future steps, the adding calculation is straightforward. I call these numbers "stragglers".
The idea is that for bits > (highest possible bit of MAXAI), either we kill or don't kill all the bits. If we kill all the bits, every number is a straggler, so it becomes easy to calculate. Else, the array stays the same. So no extra memory needed at this step.
For bits <= (highest possible bit of MAXAI), we actually care about the array. If we don't kill all the bits at this step, we store A. If do, we need roughly sz(A)/2 elements in the worst case. At least it seems.
However, notice that although the array A is big, after we kill off the biggest bit, there are only sz(A)/2 possible values. So actually, yes, at each recursive step, we only need sz(A)/2 + sz(A)/2 = sz(A) memory, so after bit <= (highest possible bit of MAXAI) we only need MAXAIlog(MAXAI) memory total.
Queries can be updated naively because the depth of the recursive calls is log(K) and we split it up into disjoint intervals, so each query is only touched log(K) times
This is my thoughts after discussing w/ adamjamil after contest. In contest, I had such a scuffed impl since I sort of handwaved the argument above, leading to a lot of extra constant factors that weren't needed. But here is the final impl, is pretty fast :) submission
Who is adamjamil?
The impostor
Looking at my graph I think I'm really a purple coder.
Problems were really high quality
Can somebody tell me why are samples in E not correct? I lost 20 minutes because of that, it is so stupid. There were few more technicalities that were so dumb. Overall, I liked the problems. Great round, better than last few.
There are samples only for input example :)
They haven't any relations with correct tactics for the problem.
My solution goes first in the first testcase of sample)
I get it, but just imagine implementing the solution that works, running it, and getting First, Second as an output, while the sample output is opposite. If both players play optimally, the winner is uniquely determined. I don't see a reason for doing this.
Reason is to don't give any hints to participants.
It could be done by giving a trivial test case. On the other hand, the solution is enough complex that it is very difficult to spot any pattern based on samples only.
Some individuals have mentioned encountering integer overflow issues with their
D1andD2. A helpful workaround involves utilizing along doubleinstead of anint64_t, aslong doublecan manage cases like1e25or1e1000. It's noteworthy that you can still compare along doublewith anint64_t, and if the situation permits, thelong doublevalue remains equivalent to theint64_tvalue.I think int128 should be enough
Doesn't that involve a lot of risk of precision errors?
Mantissa of
long doubleis 64 bits long. https://en.wikipedia.org/wiki/Extended_precision#x86_extended_precision_formatSo? Doesn't that mean that there is a big chance of having integer numbers beyond 2^81 (for example) being wrong?
In this scenario, there's no need to make any adjustments to that number because
kis evidently smaller than the cost. Therefore, there's nothing to be concerned about.Greetings from Greece! The problems were interesting, congratulations.
After working through the problems (since I didn't solve any in-contest), here my thoughts:
A: nice easy problem (I misread as exactly K at first, and thought I was going to have to implement something more challenging)
B: a nice problem, perfectly fits the expected difficulty
C: really nice problem, 1 observation about how to rewrite the sum, then easy short code
D1: nice problem D (fairly standard though)
D2: hard for problem D, but a really good problem in my opinion
E: nice interactive problem, observation felt the same difficulty as C to me both E and C basically just involved rewriting some summation *slightly, and then implementing something relatively simple
F: another really nice problem in my opinion, perfect fit for it's difficulty I had trouble setting up the implications in contest, but after seeing some solution and learning a very clean way of doing it --particularly from ecnerwala's solution
My favourite problem : E