There will, and there shall be a THU round!
Nihao Codeforces! After the unfortunate event which led to Codeforces Round 1010 (Div. 1, Unrated) and Codeforces Round 1010 (Div. 2, Unrated) being unrated last week, we’re back and stronger than ever!
Tsinghua University’s Student Association of Algorithmic Competitions (THUSAAC) is pleased to invite you to participate in Codeforces Round 1012 (Div. 1) and Codeforces Round 1012 (Div. 2) on 23.03.2025 08:35 (Московское время). This round will be RATED for everyone. You will be given 2 hours and 30 minutes to solve 5 problems for division 1 and 6 problems for division 2, and two of each will have subtasks. Note the unusual time of the round.
Our team of amazing problem setters include: Iam1789, Ecrade_, E.Space, QuietBeautifulThoughts, gyh20, SpiritualKhorosho, dapingguo8, myee, abruce, _Lucien. Some of the problems prepared were not used in the final contest but we would still like to thank them nonetheless.
We would also like to express our gratitude to the following individuals:
KAN for helping to host the round;
FairyWinx for coordination and helping with the problem preparation;
The team of problem setters for crosschecking the problems and also donghanwen, SnowySummer, wangjinbo, xiaoziyao, turmax, SomethingNew, teraqqq, temporary1, LeoPro, gmusya, KiruxaLight, 18o3, mz1 for testing the contest and providing us very useful feedback;
Tsinghua University’s administration, especially our advisor Wentao Han for helping us in all means possible to ensure the smooth organisation of the whole THUPC event;
MikeMirzayanov for the amazing Codeforces and Polygon platform!
THUPC is an annual event hosted by Tsinghua University’s Student Association of Algorithmic Competitions. It is the largest student-run competitive programming contest in China with the top 100 Competitive Programming teams from all over China coming onsite to vie for the crown of BEST CP Team in China after qualifying from a pool of 1000+ teams.
We hope you will enjoy and have fun in the contest. Good luck.
UPD: Here comes the scoring distribution.
Division 1:
Division 2:
UPD2: Congratulations to the winners!
Div.1:
Div.2:
UPD3: Editorial
based
I agree
Hope you all enjoy our contest :)
sto Ecrade_ orz
great contest c was really interseting
C was of expert lvl
hope the contest will be held successfully this time :D
I hope that today I will become a specialist. Hope on this contest
As a participant who has taken part in the preliminary contest but failed to enter the finals, I will reach CM again in the contest.
thu rounds, best rounds!
As a participant, I hope the problems are cool!
Auto comment: topic has been updated by fengzhengwei (previous revision, new revision, compare).
Cool!
expecting a good round
I hope it goes well.
orz fengzhengwei
I am your biggest fan!
master i miss you.
THU never makes me disappointed!
Oh, the limit of D1 A disled me.
I feel really sad about it but I think problems are good.
It seems that I got another opportunity to participate in Codeforces with pay while on the job.
Where is the score distribution?
The revengers ARE BACK LoL
This could be the surprising second opportunity to achieve an academic link with Tsinghua University throughout my life even if I'm in mainland China
Isn't the number of testers of this round quite low? Especially for a div. 1 round.
Partly because the authors decided to not accept Chinese testers.
Updated list :)
orz QuietBeautifulThoughts and SnowySummer
Score distribution?
please add scoring distribution
Hopefully, this round will not be postponed and then unrated at the same time like the last unusual scheduled round...
Are the questions sorted by difficulty?
Auto comment: topic has been updated by fengzhengwei (previous revision, new revision, compare).
Auto comment: topic has been updated by fengzhengwei (previous revision, new revision, compare).
Waiting for guests to leave so that i can attend the contest ;sob
The best coders in the best university in China can NOT EVEN COUNT THE EXACT NUMBER of problems.
Sad.
Don't be so sarcastic bro. It's just a little typo.
We're now working on the onsite contest. It'll be fixed soon.
It says 6 for DIV 1 but its for DIV 2 :)
first time div.1!
Auto comment: topic has been updated by fengzhengwei (previous revision, new revision, compare).
hard c
Good luck everyone, glad we can have a late night contest.
extra registration please?
why can't i register omg :sob:
Is there no extra registration?
What if I forgot to register? Can I still participate?
MikeMirzayanov
extra registration?
FairyWinx please open the contestttttttt, hedging myself rn by doing the problems but dont want to waste my time
is C correct?
Why where is no extra registration?
Why no extra registration and also registration closed at 11:00 and contest started at 11:05. I wanted to participate :(
Why is there no extra registration? I wanted to participate :(
As an onsite contestant, the lunch is McDonald's and they provide better meal than Zhili Cup(which is 1+1=13.9 combo).
As an online contestant, I didn't get any free lunch nor dinner. I'm hungry now.
how does my C run in 78ms :D ?
Um, I feel bad about D1 A.
The limit $$$\lfloor \frac{n}{3} \rfloor-1$$$ misled me.
When I saw the limit, I considered dividing the permutation into $$$\lfloor \frac{n}{3}\rfloor$$$ groups with size $$$3$$$. That wasted much time.
But the true answer is around $$$\lfloor \frac{n}{2}\rfloor$$$.
If the limit is $$$\lfloor \frac{n}{2}\rfloor-100$$$, I can solve the problem much faster.
Did there anyone have the same experience as mine?
Insert smug face.
I also didn't understand why the bound was like that. So I just ignored it and tried to think of maximizing number of primes.
maybe because it's hard to prove floor(n/2) primes exist.
its actually doable for n — 2 * primegap(n) i guess
this is a lesson not to guess from limits..
I thought that we can use the fact that for all $$$m$$$ there is at least one prime $$$p$$$ such that $$$m \lt p \lt 2m$$$, so in our case, we can take $$$m=\lfloor\frac{n}{3}\rfloor$$$ and be sure that there is a prime in the double that interval, so we can actually easily prove this tight bound and the proof of the more loose bound is not that straight forward, or it is?
maybe im missing something but floor(n/2)-c seems like a bound that wouldn't work for a problem no matter the constant, the biggest answer you can get for any given in is (ignoring exact indexing here) n/2 — distance from the midpoint to the closest prime
D surprisingly easy, could've swapped place with C.
C easy on the logic, but hard on the implementation (or I'm just over complicating things).
C just statement is unclear
Div2C today = implementation skill issue.
WA/TLE/RTE for no real reason, oh well...
Wow I hate 1B
also B1 >>> C1 like wow i found C1 so so much easier
As someone who solved B1 but not C1, I disagree
ok what the fuck was i doing for B1 ......... MY B2 IS WAY SIMPLER LIEK I KNEW YOU COULD SIMULATE IT BUT I COULDNT FOUND A WAY TO SIMULATE IT FAST ENOUGH EVEN THOUGH IT'S LITERALLY RIGHT IN FRONT OF MY FACE
Why can't I see others' code?
UPD: ok I can see now. thx
Is it just me or in div. 2 D felt easier then C?
When i submit a and b submission of D> C so go for D and find it much easier
I saw the statement of D is more simple then C.
u are not alone
I got idea to solve C very fast while can't figured D in 30 minutes... so in my case it's C < D.
any tips for c?
https://codeforces.me/contest/2090/submission/312006956
I pregenerated all the paths for both types of guests and just checked if the path was already taken or not, u can see pretty clear pattern of which seats are closest to the start.
can you tell error in mine?
https://codeforces.me/contest/2090/submission/312038005
So i figured error in mine
on ti = 1, it will give the nearest sear whther it is occupied or not
so you need to check in both priority queues , the problem setters definitely did us dirty in this question
tho I lost expert, but I loved problem C for some reason. especially after getting one the fastest solutions for the problem
C2 is very nice, but unfortunately I thought of wrong solution and spent half contest implementing..
Become IGM probably. I've come up with the solution of C2, but it's too hard for me to implement.
Could anyone explain why I'm downvoted?
jealousy
Is C not meant to be solved by maintaining tables and the count of people sitting at a table? I used a
std::set<std::array<int, 3>>>and suffered TLEDont go for n*n Try around (sqrtn +k)*(sqrtn+k)
the order can be pre-computed. Note that in a table if we know the distance for the bottom left cell of a table, then we can calculate further distances like this
where d is the distance of bottom most cell. now the order will always be in diagonal order (draw to note this).
the only exception will be the top right cell. if we consider the table above the current table in the next level diagonal, then the top right cell of current table comes before the bottom right cell of that table. knowing this, we can pre compute orders and then simply place the people
After solving B2, I accidentally submitted it to B1, so my total score for B1 and B2 ended up being lower than before submitting... (early B1 > late B1+B2). Sad lol. (Mistakes like this are irrecoverable, right?) Fortunately, it looks like my ranking didn't change.
Sorry but how did the statement of D1C get approved?
The statement has critical information spread between utterly irrelevant story lines to the point where its extremely irritating to read (at least for me).
I understand that the problem setters sometimes want to associate a story with a problem, but on CF its usually:
Natural and short (1-2 sentences) enough that it works as the problem definition.
Added as a paragraph before the formal definition so that you can skip past it.
This statement does neither of these. Instead you have utterly useless lines like
To remind the correspondence, M's mother adorned each key with a gemstone of a different type.between actually critical information that makes the reader think this will be relevant to the problem when it isn't in the slightest.I agree, reading it gave me an aneurysm lol (especially since usually all problems have stories or none of them do)
the problem itself is fine though imo
As someone who didn't try the question after reading it,
It was a nice story.
"The keys are distinguishable" isn't useless information to put in a statement, it's just phrased in the context of the story instead of in math language. The statement similarly mentions that the locks are distinguishable.
I can't agree with you more.
codeforces
Namely,
C:2720B(Unaccepted)
D:1118B
Is it just me?
Setters, literally messed up with problem c there,
it stated — For the fourth guest, distance to cell (1,4) is 4, so they chose it, For sixth guest distance to cell (1,5) is 6, does that even make sense!
they later fixed this 6 to 5. Making mistake while correcting a mistake in a round with 10 >= master level setters sets me low :(
In Div2C, can someone please explain, why we place on (1,5) and not (2,2) ?
Aren't we simply taking Manhatten distance ?
For the sixth guest, the distance to cell (1, 5) is 6, the same as to cell (2, 2), but since the x-coordinate is smaller, they choose it.
They asked you to break ties based on x followed by y
distance between (0,0) to (1,5) is 6,
Distance between (0,0) to (2,2) is 4.
There is no tie in first place. !
brother didn't read the question properly, you can only move on the corridors
you are right, I didn't read. I didn't have time :( . I spent a lot on E1 :( .
can you tell error in mine? https://codeforces.me/contest/2090/submission/312038005
So i figured error in mine
on ti = 1, it will give the nearest sear whther it is occupied or not
so you need to check in both priority queues , the problem setters definitely did us dirty in this question
You need to walk through the corridors. To reach (2, 2), you can walk: (0,0)- > (0, 1) -> (0, 2)-> (0, 3)-> (1, 3)-> (2, 3) -> (2, 2), which is 6 steps
Any guest can only move through the corridors, and they can only transition to neighboring cells by sides, spending the same amount of time on each transition.
Now, this makes sense. This corridor part I didn't take into account. Anyways, I solved E1, and took longer than expected :( .
use bfs timing instead, I don't even read all the clarification and straight to coding.
2C wasn't explained well, lost a lot of time because of it
Has tourist achieved Rank 1 this time ?? Finally #2 curse broken !!
Yet another speedforces round. Failed to get to IGM :(
How to prove Div1A? I just guessed a solution of doing the following three conditions repeatedly which got AC:
If there is a value which will result in the smallest remaining prime, do so using the smallest such value.
If all numbers overshoot the prime, then increment the smallest prime.
If all numbers undershoot the prime, then just put the largest remaining value.
https://en.wikipedia.org/wiki/Bertrand%27s_postulate
I took the prime 'p' closest to (n/2) and used the sequence p, p — 1, p + 1, p — 2, p + 2... until I got the required number of primes in c.
This works because the prime gap between the two primes closest to (n/2) is not larger than n — #primes in c. Prime gap, gn is pretty small for the input n. I guess it doesn't exceed 148 from what I can see on the gn table on Wikipedia, because gn is 154 for the prime 4,652,353.
take a prime p in ($$$n / 3$$$, $$$2 n / 3$$$) was the clever part. rest $$$p - 1$$$ , $$$p + 1$$$ , ..
Did the exact same thing. Experiemented with some numbers when everything undershoot the prime and LUCKILY the largest remaining value worked.
Great contest! But the statements could be more clear.
Sadly, there were not that many participants as usual. I randomly got enough sleep today, woke up quite energetic and participated in the morning contest at my timezone. And I don't regret it!
C. the distance is implicitly stated as the guest can only move 4 cardinal direction.
F. has good story, guy eating ratatouille moment there.
Distance was indeed implicitly defined. And that what I meant that there was no definition, as a definition is generally explicit)
bad statement.
I passed simulation with bitsets in Div1B, basically maintaing bitsets of non-zero elements of both arrays, and every time only perform operations on such indices where both $$$a_j \gt 0$$$ and $$$b_i \gt 0$$$ (finding so by doing AND of bitsets). What is an asymptotics of maximum number of operations that can be done by this solution (by operation I mean substracting non-zero from $$$a_j,b_i$$$)? Is it something reasonable, or I was lucky?
Either a[i] or b[j] becomes 0, so operates are at most 2n
Oh lol, thanks, I don't know how I missed that
Actually operations are atmost n, anyway same a[i] don't need to come to that b[i] because it's already becomes 0
I read div2 c completely from the announcement
Hey, can anyone proof my div2 D, just luckily got AC after 10 pen ToT.
312026711
How to solve Div2 E1 ?
I wrote a brute force solution but it got TLE on test 25 :(
sounds like my brute force is smarter xD
Optimize brute force a bit, by remember next[i] and its left over sum.
I've TLE on test 25 and tried to optimize bf too. Works
Tanks for making this unrated. I'm sure there's a lot of people who got stuck on C.
Also, a stupid question, was the ceiling sign always there?
bro it's rated
Weird constraints of B.
Reading 1C1/2F1 be like, am I taking somewhat english reading comprehension exam right now
There is a whole paragraph in D1C :skull:
problem D , find a prime number p in ($$$n / 3$$$ , $$$2n / 3$$$) (guaranteed there exists a prime) . Now put $$$p - 1$$$, $$$p + 1$$$ , $$$p - 2$$$ ,$$$p + 2$$$ , ..... and place remaining numbers. At sufficient number of even positions we have $$$c[i] = p$$$
Wow nice.
I totally miss the idea in contest sadly :(
Congrats! 8th grader JDScript0117 gets 5th place in div1 !!!
Congrats!!!!!
Congrats! 8th grader Donaldqian0712 got 59th place in div1 and became International Master !!!
This contest was so wack for me, missed B and C and solved in A -> F1 -> D order then was too slow on C.
I guess the fact that C,D,E1,and F1 are all within 250 points of each other makes for a weird dynamic since there's a real strategic decision to go for certain tasks first since they're all supposedly nearly same difficulty according to point spread but at the same time it's weird to be 1600 and somehow miss a Div2B and Div2C just simply because this round gives a lot more options than your usual CF round.
As participant, I hope I don't see these kinds of contests in the future
very true c had so many issues
Can someone please tell why does this get tle how do i optimise this solution
Is anyone able to determine why my submission for Div2C: 312026477 is wrong?
My logic was to use two priority queues to maintain available seats, one for the 1s and one for the 0s, then when a 1 enters, ensure that the first available seat in the pq wasn't already taken by a 0 previously. I couldn't get past pretest 2.
I had also defined a custom comparator to order the seats appropriately based on Manhattan distance.
DIV2 B can someone check why my code getting WA on TCase 4?
Logic was if arr[i][j] == 1 and either there is a 0 on top of it, then there should be 1s continuously appearing to the left of it and if there is a 0 on the left of it, continous 1s should be there on top of it (starting from the 0th row).
312042843
You are missing the case when both left element and upper element are 1's.
check this case out :
3 3 010 111 011
The 1 at (3,3) is assumed to be valid according to your code but it isn't.
Can someone try to hack this
I just find next alive b for each ai, but i think it's possible to chain ai's with bi's and force the solution to be n^2
Hey it's provable that it passes. consider the set of good indices as indices in array A and array B that are non zero. (so initially there are 2n such indices)
and the round indices are the set of good indices that change in round r.
now since you maintain a set you're only visiting the good indices in the round r and kill at least half of it. (at least one from each pair for the current round)
since there are only 2n indices to kill your solution doesn't make more operations than 2n!
how do you take into account the case when he pops some {$$$ai, bi$$$} but that $$$bi$$$ was already $$$0$$$ so he just changes the $$$bi$$$ for that $$$ai$$$ and pushes into set again. Can you prove that these reattachments will be bounded by $$$O(n)$$$ and not go $$$O(n^2)$$$ (which I believe was his main confusion).
I have attempted 'D' and reached the 8th test case before getting a WA due to a permutation issue. Still, I’m happy that my approach successfully passed the first 7 test cases in one of the contest’s highest-scoring problems!
As someone who skipped school today -18 rating isn't what I expected.
Never mind, bro. Rebuild it, brick by brick...
I litteraly solved D and still get -110.
I love THU round! XD
div2.D is a really tricky problem.
I used 1h time to think about random algorithms(that is because I used ramdom_shuffle() to solved div2.C before).I also used 30min time to think about why the 2,1,3,4,5,···,n was wrong.Almost the end,I thought about the correct solution.
PS:the samples are very confusing,I believe many people tried the 2,1,3,4,5,···,n first and got WA on test 8.
If you think I am wrong,don't downvote please
In Div.1 E, accroding to validator, sum of N is guaranteed to be less than 80. And its not shown in the statements.
If the validator was corrected to fit the statement, only jiangly's code will be able to pass (125ms *10 = 1250ms), among all 4 accepted codes till now.
When/where editorial?
My solution for B: For every row and column count blocks of '1' which should either be 0 or if 1 should be tied to the beginning of the row or column for a valid insertion of balls in the row or column. Finally, go through the grid again and wherever a ball is present check if the insertion of balls is valid or not along the row or column. Answer should be 0 if found invalid along both ways. Is this wrong or is my code wrong? code
maybe you can try this example
your code's answer is NO but the correct answer is YES.
Damn, the problem statement of d2c is so hard to understand.
Hi, when will the editorial be posted?
I need tutorial.
qwq
When solution? I really want to know how to solve 1B / 1C though I didn't participate it
Div1 C1 is a nice problem; I actually solved this in contest but the idea was unfortunately too slow to extend to C2. While you're waiting on the official editorial, here's a quick hint for C1.
After a lock is just opened, the number of chances person $$$k$$$ gets to open the next lock is based on two things. What are these two things? (Explicitly mentioned in Hint 2)
Given that person $$$k$$$ was the last to open a lock, what is the probability person $$$x$$$ unlocks the next lock? Consider the cases $$$x \gt k$$$, $$$x \lt k$$$, and $$$x = k$$$.
Thank you!
When is editorial coming out
how to DIV2 C?
Several people have answered that in previous comments
Hi. Are you planning to release an editorial soon ?
Can someone explain div2 E1 and E2 ? please :D
You want to find out in which operations there are some non zero values in a matched with non zero values in b. At most you can have 2n of this instances since every time there is a match at least one number becomes 0.
You can do this by keeping a set of active (non zero) aIndexes and active bIndexes, you also have an offset which represents the current offset of the aIndexes. Now you calculate the necessary offset for each active aIndex to meet with an active bIndex (using binary search in logn). Next, in each update you go the next offset which gets you a match and if the a that match remains non zero you look for its next matching active bIndex.
For E2 you can do almost the same thing, you only need to also keep track of the sum of all active 'a's, and stop when their sum becomes equal or less than k.
Here's my code 312026398
Where is the Tutorial?
In Div2D, I solved it by picking a prime $$$p$$$ in the range $$$\frac{n}{3} \lt p \lt \frac{2n}{3}$$$ as the first number and then alternating as:
Proof:
Case 1: If $$$\frac{n}{3} \lt p \le \frac{n}{2}$$$, then
with $$$x \lt i$$$ ensuring $$$\lceil c_i \rceil$$$ remains prime for several steps (until $$$p-x \lt 0$$$). Since $$$p \gt \frac{n}{3}$$$, we get at least $$$\frac{n}{3}$$$ primes.
Case 2: If $$$\frac{n}{2} \lt p \lt \frac{2n}{3}$$$, then
Since $$$p \lt \frac{2n}{3}$$$, we have $$$x \ge \frac{n}{3}$$$, yielding at least $$$\frac{n}{3}$$$ primes.
Does this look correct? Also, is there a way to maximize the number of primes in this construction?
Here's the closest to optimal as possible as I can find:
Do the same $$$p-1,p+1,p-2,...$$$ trick, except we go as close to $$$p/2$$$ as possible. This gets asymptotically close to getting 100% of the slots correct. With $$$n \geq 22500$$$ for example, you are guaranteed 99% of the slots to be correct.
Still Waiting for the tutorial.
I recently got a notification that my Codeforces solution 312004364 for the problem 2090D coincides with others, so I just wanted to clear things up.
When solving the problem, I referred to some code I found online(https://www.geeksforgeeks.org/minimum-absolute-difference-of-a-number-and-its-closest-prime/?ref=ml_lbp) with minor adjustments to understand the approach better. I didn’t think much about it at the time, but I now realize that since others might have used the same sources, it ended up looking similar. Definitely wasn’t my intention to copy or break any rules. Note: I made some changes to the code referenced above after its understanding. So , I assure you that such similarity arose purely due to coincidence. I hope everyone understands.
I will make sure to write solutions more of my style going forward. Lesson learned definitely.