Hello, Codeforces!
We are glad to announce that Codeforces Round 1108 (Div. 2) will take place on Jul/12/2026 17:35 (Moscow time). The round will be rated for participants with rating below $$$2100$$$. You will be offered $$$6$$$ problems, with $$$2$$$ hours and $$$15$$$ minutes to solve them. At least one problem will be interactive, so please make sure to read the guide for interactive problems before the contest.
The problemset was created and prepared by 0mar, countful, diss_quack, farmpiggie, lce4113, Whoname, and me. We are all members of the UCSB ICPC community.
Thank you to the following people who made the round possible:
- Um_nik for pre-review of the round.
- cry for coordination of the round.
- Alexdat2000 for Russian translations of the problem statements.
Our army of testers: BucketPotato, golomb, _istil, GusterGoose27, __baozii__, Arpa, omsincoconut, DylanSmith, AksLolCoding, spacewalker, Enigmurl, Bruteforcer101, Hori, Argentum47, lrnnz, mtand872, SpyrosAliv, Lance0, Atouts, bakunawa, lems, ColtsFan10, atsliwak, akimuuwu, and conqueror_of_4fecta.
- VIP tester sagbis for solving problem A and nothing else.
- MikeMirzayanov and KAN for the wonderful platforms Codeforces and Polygon.
- You, for your participation.
We hope you will enjoy the round!
Left/Top: ezraft, Whoname, 0mar, lce4113, countful, diss_quack at the ICPC Southern California Regional.
Right/Bottom: diss_quack, ezraft, lce4113, farmpiggie at the ICPC North American Championship.
UPD: The scoring distribution is $$$500-750-1500-1750-2250-2750.$$$
UPD2: Editorial
oars sirs
ok
Again...
ok
ok
You forgot:
I think testers and setters deserve contribution even if they post something stupid like “ok”, they contributed a lot more to codeforces than most comments would by helping make the round
it's actually more like:
a = '' for i in range(random.choice([1, 2, 3, 4])): a += random.choice(alphabet) print(a) if you in tester or you in setter: contribution.index(you) += 15 else: contribution.index(you) -= 15ok
as a tester, make sure to smash that register button
As a someone, I like smashing that Register button
As a someone, I usually smash that Register button twice a month
oh no i got smashed
:D
okay
woah
as a tester
As not a tester i hope i become pupil in this contest
I hope you make it
:)
As a tester, front forget, back forget.
yes yes yes yse finally
would it be in A B or C or like at the end like D E F ?
A while ago there was an interactive problem in C div2 (2209C). It is the first interactive problem I've ever solved
so basically c or above and i don't understand what does this interctive problem mean
Read this then
Finally an interactive problem....
Excited!
Then you realize that you are unrated
It doesn't matter lol
I LOVE YOU COUNTFUL! I LOVE YOU COUNTFUL! I LOVE YOU COUNTFUL! I LOVE YOU COUNTF
I DESPISE YOu coNUTIFUL! I DESPISE YOU CONOFUL! I DESEPISE YOU CONTEFEL! I DASPAS YE CONTIF
How dare you.
Because, I, am EVIL
Hi EVIL, I am MyBrainGotTLE
As a tester, UCSB is next to a beach
as an author, UCSB is the beach
As a participant, .
my #99 rated contest! good luck every participant!
I hope there will be 6 interactive problems
As a taster, countful gave me his burritos
As a toaster, I made a toast for countful
oof, i read ucsb as usb-c somehow
Has anyone tested the solvability of the problems using AI?
Hope i am able to solve till D or E . glhf
Thanks for the round , Wishing everyone the best of luck
.
As a participant I hope to reach expert this round pls pls pls
hello **everyone ** how are you all??
OK
ezraft lce4113 Thanks for organizing.
Excited to see yg again at NAC next year
As not a tester i hope i become candidate in this contest
First half of time: solved ABCD.
Second half of time: stared at the screen to see my rank dropping.
I'm asking myself where did my comments go:
PS: How can the author write the checker for A?
It's just some knapsack dp. Comments were removed since they were during the round
Oh yeah thanks
it's just like n = even..then the answer will be n,n-1,n-2...1. if n is odd then we can use some dp but the question gives n is always even
Yeah but the checker can't be written that way
got u, didn't get earlier
hint for C.
We only need to care about subsequences with sum $$$0$$$ and $$$-1$$$
We only need to think about the $$$-1$$$'s, and then the count of each positive element in increasing order. And then just do combinatorics to count putting even and odd number of an element.
https://en.wikipedia.org/wiki/Alternating_series_test Not exactly a direct hint, but being familiar with the proofs around these series is where (I believe) I got the intuition for handling this problem.
can anyone explain why it is showing -9 in betweeen arrows, is it bad to ask for a hint.
$$$C$$$ is a hard counting problem man. It's not very easy, coming up with the observation is hard, and implementing the counting carefully is also hard. How did 5k people manage to solve it?
Didn't really like $$$B$$$ too. Took too long to get that $$$1, 2, 3, sum,...$$$ pattern.
There is a very clean solution for C. The editorial will be out soon
$$$n \choose 0$$$ + $$$n \choose 2$$$ + $$$n \choose 4$$$ + ... = $$$n \choose 1$$$ + $$$n \choose 3$$$ + $$$n \choose 5$$$ + ... = $$$2^{n-1}$$$
Perhaps this could make your life easier.
Ohhhhh I was stuck on this problem for 2 hours... I need to improve my combinatorics
I wrote a loop to do that :(
Got humbled by C terribly :(
same
Now you will lose pupil and I'm reaching pupil this time *laughing in evil voice*
UNO Reverse x2 :(
I stayed pupil xDDDDDD
(we're now both proud graytists)
Is there a deterministic solution for E?
What's the random solution. I've been thinking that since adaptive the grader can always defeat us
Simply generate $$$m_0$$$, $$$m_1$$$ randomly will hopefully distinct $$$b$$$. $$$x$$$ may be relevant to $$$v$$$, but $$$m_0$$$, $$$m_1$$$ is not relevant to $$$v$$$ according to the description. Choose an $$$x$$$ with $$$15$$$ bits of $$$1$$$ and $$$15$$$ bits of $$$0$$$ will pass with a high probability, I think.
I think you can prove its not possible: if you query 0..{a times}1..{b times}. WLOG (u can reorder bits) , and you get the same number back, then no matter what two numbers X and Y u give they could return {first a bits of X}{last b bits of Y toggled}.
Thanks. I was thinking how to handle this corner case during the contest but failed, so I didn't submit any solution...
My E sol doesn't use any random element and passed, I might be missing some case though but don't see it for now.
Ok i think i found a case
Depends on exactly what you mean by deterministic.
Is there one where you can just hardcode in values? Yes, you just take the probabilistic solution and do your rng() calls outside the code and then hard code it in. However, this makes it so a strong adversary has probability 1 of hacking your code; they can just check what your values for m0/m1 are to make your m0 look like m1 (or vice versa) and trick you into assuming the wrong one. Luckily, hacks are disabled on E so nobody can be said strong adversary.
Problem A and B are like, if you're able to figure out the pattern, its cakewalk otherwise you keep staring at the screen for hours, no luck. I love mathematics.
C is a great problem :-)
it's really not
I've submitted A twice (since I'm not sure that if the first submission is correct), if the first one is correct, will I get -50 for resubmitting?
Its so hard :(
A huge thank you to the contest authors and testers for putting together such a fun and well-crafted Codeforces round! It's easy to forget how much thought, debugging, balancing, and testing goes on behind the scenes to make these contests enjoyable for everyone. I had a great time solving the problems, and I really appreciate all the hard work that made it possible. Looking forward to the next one!
My favorite things about this contest:
I've solved C terribly https://codeforces.me/contest/2246/submission/382297651
Thanks for the contest, it was my favorite div2 in a while! I feel a bit bad for using an alt, but I felt like it'd make me a lot happier than basically never having the motivation to do another contest again, and this contest was definitely evidence for that.
Unless I'm missing something, isn't the success probability kinda low (like only 0.99 for like 50 * 10^5 testcases)? Maybe it'd be better if the bound on things were $$$2^{60}$$$ instead of $$$2^{30}$$$? I liked the problem though
you should feel bad since alt accounts are not even permitted if i remember correctly XD
I'm aware of that but imo the main downside of alts is that they deflate rating and ruin standings/rankings. Since that's already happened a lot, I believe the negative utility incurred by my alt is much less than pre-AI, and worth just making myself happier :p
Can someone explain solution of c and d, I'm absolutely cooked
You can divide the array into blocks... (block of -1s, block of 2s, etc...). for example, a=[-1,-1,2,2,3,3,3] is divided into {-1,-1} {2,2} {3,3,3}
iff u choose odd number of elements from a single block consisting of only x, ur total will be x (cuz +x=x;+x-x=0;+x-x+x=x;+x-x+x-x=0;etc...)
in order to obtain 0, you can either:
1.consider choosing even number of elements from each block
or
2.u can choose odd number of elements from the block -1 and odd number of elements from the block consisting of x and odd number of elems from the block consisting of x+1 (x is arbitrary but greater than 0). This works because +(-1)-(x)+(x+1)=0 and there is no choosing from exactly k block combination that will cancel out the -1 ($$$k \ne 2$$$)
no. of ways to choose any odd no. of elems from a block of size n=no. of ways to choose any even no. of elems from a block of size n= $$$2^{n-1}$$$
the initial -1s allow us to fudge with the target sum. if we take even-many -1s, then our target sum among regular numbers is 0. Otherwise our target among regular numbers is -1.
To obtain sum=0 with even-many regular numbers: consecutive selected pairs (b1,b2), (b3,b4)... have nonpositive sums. Hence resulting total sum is <=0 and is equal to 0 Only if each consecutive pair has equal elements. Then num_ways to obtain total=0 using even-many regular numbers is easy counting problem.
To obtain sum=-1 with even-many regular numbers: similar case. code is easier than explaining:
Hi all! Did someone try D?If yes please drop some hint.
Use bitset ideas + figure out optimal solution when n = 1.
in C to avoid tricky combinatorics you can just do knapsack dp with a map and only store sums which are <eps away from 0 and <eps away from the current number, where eps is some small integer (i have 10 in my code)
B is classical and too hard for the position.
Somehow the queue is so good today
Crazy Contest , It just Fu#k me
I wrote the following code in E: 382296469
I have a few questions:
1) why does it work?
2) why does it stop working if K is increased (there are always two bad values of v)?
3) how does the ``standard'' solution differ from mine?
Apparently, the probability of my solution getting an AC is many times lower than what the authors expected.
for problem E, x=1 directly gives 'ty' and also the parity of 'v'. Tbh I wasnt even thinking to come close to intended solution. Solving other problems seemed kinda boring compared to this. The setters must have felt |cinema|.
My solution is coinciding with one more contestant though I didn't share my code not i usw any platform to publicize my code also the contestant is unknown to me. This is a total coincidence of same solution.
I have been flagged for cheating on problem C. However, I did not cheat in any way. The message I received said my submission, 382266816 was found to be similar with cindu_1402/382277909, Kiruthika_10/382279819, Sarmi_18/382281148, Saha_.na/382282080, Boomi_07/382282494, bu_xiang_qu_ming/382285591, Dharsh_30/382288493, LioHein/382290058.
First of all, my submission only shares the same idea with LioHein's one, 382290058, while the others do exactly what is explained in the editorial (I overcomplicated things in my solution). Therefore, I believe that this excludes any accusation having to do with everyone but the last contestant listed above, LioHein.
Now, even though me and LioHein do basically the same thing, I must say that our codes are as different as two can be, while still doing conceptually the same thing (treat even and odd length cases separately, and when dealing with the odd length case, fix the values that are going to appear on odd number of times (besides -1), and we calculate the number of ways for each of these using some prefix and suffix precalculations). Not only do I precompute the powers of 2 while he uses fast exponentiation (i have fast exponentiation as a function in my code as a template but i do not use it), but he keeps an additional array with each unique value and its frequency and solves the problem on that array, which is smarter and easier than what I do (I just manually traverse each block of equal values each time I need to). I believe anyone could look at our 2 codes and say that nobody cheated. It was just a coincidence that we both did not see the easier solution explained in the editorial and came up with this.
Is there anything else I can do to prove my innocence? I actually did well in this contest and it would be a shame if I wouldn't receive rating for it (I will assume that if I get flagged for cheating the round doesn't count for me, I don't know for sure). Do you guys know anything else I can do, maybe I should contact someone else? I thought this would be the right place to write this message but maybe there is somewhere else better, idk.
Oh, this is the first time I've been mentioned in a comment. I just found out that an article accusing me of cheating was sent to my email. Now I know what "skip" means. But I'm probably not from the same country as the blogger, and I watched the solution. For a classification discussion question, isn't it normal to have a fixed discussion mode and approach? Thank you again for the blogger's mention, which made me notice this strange email, even though I didn't perform very well in that competition.
Problem C was interesting good job bros
Hello. I recently received an automatic plagiarism warning for my submission to Problem 2246D. I would like to request a manual review of my solution, as I solved the problem independently during the contest and did not copy or share my code with anyone. After comparing my solution, I do not believe it has significant similarity with the submissions mentioned in the warning. If the system has produced a false positive, I would sincerely appreciate a manual verification of my submission. Thank you for your time and consideration.