Ciallo, codeforces～(∠・ω< )⌒☆
We are pleased to invite you to participate in Codeforces Round 939 (Div. 2), which will start on 13.04.2024 17:35 (Московское время).
The problems are from Otomachi_Una and me.
This round will be rated for participants whose rating is below 2100. Participants with higher ratings may participate out of the competition.
You will be given 6 problems and 2 hours to solve them. We hope you find them interesting.
We would like to thank:
- DaiRuiChen007 and lichenghan for helping prepare this contest.
- IgorI and irkstepanov for coordinating the round.
- A_G, NemanjaSo2005, yeminghan, lunchbox, Andreasyan, lsantire, RabbieWjy, yurongyi0504, KKT_89, MinaRagy06, carnation13, Romakolesn, blitztage, qsc114, Adam_GS, Evarine and htetgm for testing.
- MikeMirzayanov for Codeforces and Polygon platforms.
Score distribution: $$$500-750-1500-1750-(1500+750)-2500$$$
Good luck on the round and high rankings to everyone!
UPD: Editorial out.
UPD: the winners
| Div. 1 | Div. 2 |
|---|---|
| BurnedChicken | zjy114514 |
| StarSilk | King_of_Beggars |
| maspy | _MyGO_Tomori_ |
| 415411 | LegendaryGrandmasterLjm |
| Rubikun | naniak |
Photo of authors (unfortunately, I can't come, so my profile is shown in the picture): 
UPD: The rating changes for Educational Codeforces Round 164 will be applied after this round.
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
Auto comment: topic has been updated by 0doO (previous revision, new revision, compare).
have mixed feeling of looking at pics.. registering contest written by literal 7-th grader (redcoder) from china which clearly 10^10 smarter than me.
why Chinese are so smart.
We are in grade 9 instead of 7
Well that makes me feel much better..
hhhhhha
that feeling when I saw my high school's uniform showing up on codeforces...
hhh, Hua Fu is very famous in Guangzhou.
We are both in the same grade. One is cyan one is red. How are you guys so good? Teach me the ways please.
super DNA :)
I think it's super mentality
No it's super involution :)
super juan hah
When author of this competition in such age made problems in codeforces, than I can't even imagine about our compare (He is my age)
RESPECT FOR HIM!!!! MY ADMIRES!!!
But why one auther comes from Japen?
Or it just a joke?
Looks like the author's new account
Maybe because he favors anime, since he uses those pictures as profile photos
Apparently he's a fan of yuzusoft.
anime
They don't all have top talent (although they are generally quite talented), but it's more because of their strong interest in programming. In addition, they join the school's training camp during middle school, where they are trained by teachers and sometimes even skip classes to train.
Intersting is a gd teacher
I think that it may be because of China's huge population. You know, China has about 20% of the population on Earth. It is common that some of them are gifted. Besides, a big population also means that you can easily find friends who share common interests and dreams with you, just like on Codeforces or in Competitive Programming. By chatting with those friends and exchanging learning experiences, people can learn more from each other.
And that is why I really appreciate the communicating platform, various interesting problems and their corresponding tutorials that Codeforces provides to me. It offers equal opportunities for every one to contact with peers and learn useful skills.
An old legend says: "Being chinese is a cheatcode"
Chinese is not smart, such as me.
Redcoder's rating is 2400 and yours is 1411. dude! He's less than twice as smart as you, don't worry.You could be a Redcoder in the future.
As a tester,Otomachi_Una is very cute :)
As an author, give me Contribution!
an author
Huge thanks to everyone who contributed! Let's jump into the fun of problem-solving together!
Me looking at the pic and wondered which rock had I been living under when I was grade 9 i.e. 11-12 years ago...
Kudos to the youngsters, and hope the contest run well.
So true. :(
Bro says this while being in 9th grade himself
doesn't make it less true
wait how'd u know he is in 9th grade? Is there a secret society of codeforces who are in 9th grade? /s add me too
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo~（∠・ω< ）⌒ ★
Ciallo～(∠・ω< )⌒★
Ciallo~（∠・ω< ）⌒ ★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Why there are Ciallo with negative vote?Just because they have relatively low rating?
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
HaoKePa NiMen YouZi Chu
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
666
bu fa nv zhuang jiu ai ca
Yes, sir.
Ciallo～(∠・ω< )⌒★
hai bu geng xin
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo~（∠・ω< ）⌒ ★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
qrz
UWU
As a big fan of yuzusoft(see my id), i will definitely enroll it though i have 3 college experiments tomorrow. Ciallo~
Why there is no Yoshino in problems ToT ... I supposed it was a party for all yuzu characters, while it turned out to be nene solo TwT, and I gained a rating drop due to be uncommon with mathematical induction....
Yu...Yuzu soft fan?
Wish everything goes well!
Wish everyone gain more ratings, and me too :)
As a tester, I can confirm that round has some nice problems.
Every round , always say. Div2 is hard for me , hahaha~~.
Cute pfp so I'll take a chance ^^
As a tester, I ask you to:
Play Omori to be as op as Yahia_Emara
Play Hollow Knight to be as op as Octagons
Downvote Heap_OverFlow for farming contribution
Give me contribution
Hi! From Vietnam with love <3
i need to study more
Nice picture! pretty sure it will be a good contest:")
OMG! Unrated tester yurongyi0504
As a tester, I hope everyone enjoys the contest!
"unfortunately, I can't come, so my profile is shown in the picture" sad
Otomachi_Una round. les go
Ciallo～(∠・ω< )⌒★
yuzusoft round(
clear and short description we like it ...Ciallo～(∠・ω< )⌒★
It seems to be the same account.
Also, the only reason why there isn't a "star" button next to the name of both the two profiles is that someone logged into these accounts.
MikeMirzayanov please ban him.
Please I need cm :)
Ciallo～(∠・ω< )⌒★
OMG Huafu jvxue!
when i see ciallo i know it's an uncommon round
I think I need to go to the library and play this round. Ciallo～(∠・ω< )⌒★.
Now imagine what the comment section will be like if it was a girl
wut
Having a photo in public without getting any nasty comments on appearance is very nice. I never got that as a female on algo community online which made me kind of jealous tbh
Admins delete those comments and put commenters in read only mode.
she didnt say whether she got them here, or somewhere else.
oh. im sorry you had to face that
Who is this anime cartoon characters?
Ayachi Nene(left) and Kariya Wakana(right).
Ciallo～(∠・ω< )⌒★
我真是服了你们这种柚子厨了。
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
What if my rating is now < 2100, but if they give me a rating for the previous round, it will become > 2100 and I will not re-register for this round, will I write a rating or not?
As far as I know: you won't. See https://mirror.codeforces.com/blog/entry/127177, although that could be for only combined rounds, and not Div. 2s.
thank you, I think it will be as it is written there
Ciallo～(∠・ω< )⌒☆
score distribution?
Ciallo～(∠・ω< )⌒
wow
It is getting late to publish score distribution!
upvote!!
I hope the problem statements are short and clear.
Short: not sure Clear: Yes
西亚洛～(∠・ω< )⌒★
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
cute/qq
/qq
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
Hope this contest will be best for everyone. Best of luck guys.
operationforces
Constructiveforces.
A question regarding problem D sample cases, did getting WA on test 2, 3 which are given in the statements used to always give penalty ?
C is not a good problem.
It actually was a great problem because it penalized the guessforces squad.
I am confused what is the correct way to come with a solution then ?? What I usually do is based on the problem statements and output I try to figure out any pattern, and once I find it, I dry run it on several testcases to check its validity. But since you are pretty experienced so would you like to explain me the correct way of solving the problems and coming up with correct solution ?? Thanks.
it's easy to guess the wrong answer i think.
Because your "beating around the bash" didn’t work, doesn’t make it a bad problem
the worst C i have ever seen
Such tasks provide basic ideas and constructions for an inexperienced person. Stop thinking about the rating lol
no worries about the rating just an opinion
whats the basic idea here ?? Is it that to make a matrix sum maximum, fill it with row-column manner ??
D is actually not too hard, but it's somehow painful to implement
Wtf is the solution to D? I thought about bitmask dp, but no idea tbh.
Just use backtracking LOL. Generate all subset and try to use the operation on those subset. It's easy to see that for each consecutive subset, its maximum sum is the sum of that subset itself, or (size of subset) ^ 2
Generate all subsets of what?
Sorry, I forgot to say. Generating all subset such that you will only use operations on those subsets. The key idea is that for example, you have an subarray with x elements, you can always make the sum of this array to be at least x * x by making all the elements equal to x. The construction is not hard to think if you write on the paper, but the implementation is... I don't know
It is cubic dynamic programming on ranges (segments), but construction of answer takes exponential time and space since size of answer is exponential
I only come up with the DP implementation when the contest has like 5 minutes left :(. At first I'm going to do it recursively
that's right, my idea came in 5 minutes after reading this problem.
problem C in a nutshell : Wrong answer on pretest 2
for real.. made 7 submissions :)
I did 6 submission increasing closer to optimal construction but was not enough...
yea same here. Figured that I had to do Type-1 operation till (i think) n/4 rows. But still pre-tests failed :(
ok, what was the edge case for C?
what's your solution
nvm turns out my dumbass got the wrong approach lol
https://mirror.codeforces.com/contest/1956/submission/256521913
Can someone please tell me why do i get wa on pretest 6?
Basically my idea is that we can construct a sequence of operations that sets everything on interval of lentgh n to n
Then i do dp to get the best division
why does this retarded code for F runtime error i will kms 256536946
Feedback on the problems:
In all, this round seems to be a good one (if the pretests are strong). Thanks to the authors!
For D, I think the $$$5 \cdot 10^5$$$ upper bound on operations made it too IO-heavy for checker to make multitest.
Actually we come up with the idea of E2 first, but it was too difficult to solve without the hint E1 provide, so we just add an easy version. In fact, it can be proved that brute-force only need $$$ O(nV^{\frac{1}{3}}) $$$ to solve the problem, so it's possible to solve E2 by using code of E1.
Figured out a solution for c, but contest is over by 1 minute.
Too large problem statements for A and B. And difficulty gap between B and C is huge. Getting big negative delta :(
it took me 8 min just to read and understand what the statement is asking...
and solution was pretty easy but statement is too long
C made me played like a fool. Haha, being outsmarted by youngsters...
Late submissions were when I realized how beautiful and simple the solution was, and I wished I solved it sooner.
Can you explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??
Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??
I actually got into the same mental trap as you, and took a very long while testing locally and observing my own output to figure out my errors.
At first I just simply checked if my own code is functioning correctly, assuming what I did was optional. What I got at first was something like this...
You see that
3at the bottom row? Yeah. It took me way too long to figure out there was something abnormal in my output, and a little more while for me to conclude that it could be fixed better. The thing here was that the actual solution was logical and symmetrical in a way, you might have not seen it at first, but you would know it was the solution when you did.No advice on constructive problems as a whole either. I'd just say that let your imagination grow wide, experiment with many things, and also simultaneously hone your instincts at detecting things going right.
Sorry, I by mistake downvoted you. You really helped me. Thanks.
Mistakes happen, I won't mind that. Glad I could help.
For what it's worth, I also got WA at first, and with the same strategy as you. But, after getting WA, I tried the case of $$$n = 3$$$, which gives useful intuition for the other cases (the optimal final matrix you want to get). Then, I tried $$$n = 4$$$, but couldn't do it in $$$\le 8$$$ operations. Then, I drew out the entire thing for $$$n = 4$$$, and stared at it for 5 minutes or so before finally realising that "oh I can just overlay stuff". In my opinion, the last part was the hardest one, because everything before that can be done using trial and error, but this requires a "flash of inspiration", so to speak.
I hate the long story statement of A. long statement is ok in long contest only (:
Exactly!
Agreed. Bro it made my mind so fuzzed up that I had to solve it by ITERATION! And that too in 17 mins. I was like: this contest is OVER for me until I saw C :(
Ah I got the idea of C but couldnt implement it because of time.
Just a summation of (n-i)*(2*(n-i)-1)
.
any idea how to solve C ? was stuck on it for the whole contest :(
Hint: For a square of $$$n \times n$$$, swipe the last line and last column, then solve the problem for a square of $$$(n-1) \times (n-1)$$$.
^let's stop thinking of every iterative problem recursively. Please avoid giving misleading hints,
It's not that recursive. I think I oversimplified my thoughtstream in the comment, but I meant that hint when typing it out, and even thinking that it was more of a solution than a hint.
Perhaps the only mistake I made here was giving the swipes in reversed order.
It is not a misleading hint at all, just because the idea is recursive doesn't mean it cant be coded up iteratively. It is a great hint and I also solved it that way.
You will get matrices like
1 2 3 4 5
2 2 3 4 5
3 3 3 4 5
4 4 4 4 5
5 5 5 5 5
I did find out the pattern during the contest but after messing around for an hour I thought it was impossible to implement using only $$$2n$$$ moves. Can you tell me how to construct the pattern?
for i from n to 1 do
1 i 1 2 3 ... nand2 i 1 2 3 ... n0 0 0 1
0 0 0 2
0 0 0 3
1 2 3 4
0 0 1 1
0 0 2 2
1 2 3 4
1 2 4 4
0 1 1 1
1 2 3 4
1 3 3 4
1 4 4 4
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4
I see it now. Thanks a lot!
0 hack attempts among 20k+ people :(
Can someone explain why iam getting wa on my submisson for C :256512434
should be this when n = 4
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4
is your solution get this?
wait, how are you replacing the 2 with 3 in the second row?
try this
every time use same permutation 1, 2, ..., n
use operation 1,2 and select i = n, n-1, ..., 2, 1
yep now i've got it,should've seen it because i kept wondering what to do with the extra opration...thanks anyway
is C basically build this pattern in 2 * n right? cannot prove but it seems impossible
Yes
yes It is possible in 2*n order of operations is 1 1 1 1 2 2 1 on row/col applied 1 2 3 4 1 2 1
i tried it for 30 min but i thought it was impossible.
every time use same permutation 1, 2, ..., n
use operation 1,2 and select i = n, n-1, ..., 2, 1
does this shape have a formula to calculate its sum ?
sum from 1 to n where ith term is i*(2*i-1)
hence sum = (n* (n + 1) *( 4*n -1))/6
submission_C I tried the implementing the same. can someone help me understand ? what's the correct approach to maximize sum in this
You can see that you have $$$4$$$ at the end of each column and row, hence, probably, you should start from them. Replace first row with $$$4$$$, $$$3$$$, $$$2$$$, $$$1$$$, after that replace first column with same permutation, now replace second row with this permutation, after that replace second column and so on. You will get this:
But it is the same.
the idea is always chose the line/column that contains the 1 to put the permutation, then construct the algorithm is not that hard.
I don't really know why C took so long to solve for me... Actually, solved D much faster, lol.
Really great contest, I especially liked problem D. Unfortunately I couldn't code it up in time.
Me too. I came up with a solution but missed it by 2 minutes. Will validate my solution after system testing is over.
Not sure why people are liking problem D, but the brute force with bitmask was very intuitive and very well fitting the complexity given the constraints.
Usually D is harder than normal brute force, or did I miss something?
https://mirror.codeforces.com/contest/1956/submission/256577486 (Although I couldn't make it up on time for contest because of one bug), but here in brute force I just tried all possible masks and chose the one with best ans & least changes.
I you only care about the answer, you can solve it in $$$\mathcal{O}(n^2)$$$ time complexity with a really cool observation, which is the reason why many people like it I guess. The reason why problem author set $$$n \le 18$$$ is because there could be $$$2^n$$$ steps in the construction.
Can you share how to find the answer in O(n^2).
By noticing for every subsequence of length $$$L$$$ you can turn it to $$$L,L,\cdots,L$$$.
Thanks for the reply.
I also made an observation during the contest and it got AC but am unable to prove it-
if f(l,r) denoted the ans for subarray a[l,r] then
f(l,r)=max((r-l+1)^2,f(l,i-1)+a[i]+f(i+1,r))
where i is the index of the maximum value in the subarray. Can you help prove it or find a conuterexample.
It's easy to prove. First you need to observe that you only need to prove the case that all elements are 0.
And then you can do it recursively, assume you can set the $$$a_i$$$ to $$$i-1$$$. If you want to set $$$a_{i+1}$$$ to $$$i$$$, all you need is to first let $$$a_i = i-1$$$, then $$$a_{i-1} = i - 2$$$, $$$\dots$$$, $$$a_1 = 0$$$. Now you can operate on $$$[1,i+1]$$$, and $$$a_{i+1}$$$ is $$$i$$$ now.
So at the end, you can set every $$$a_i$$$ to $$$i-1$$$, and operate one more step $$$[1,L]$$$, you can set every element to $$$L$$$.
I wasnt asking about that actually i wanted to prove or disprove the observation that i mentioned in my prvious reply that its always optimal to either make the whole array eqaul to r-l+1 or partition the array around the maximium of the array that is leave the maximum of the array as it is and maximise the answer for the subarray that is to the left of the maximum element and also the subarray that is to the right.
refer to my previous reply for the transition im talking about
I don't know what is needed to be proved.
Because looking at every longest subsequence that is being operated, the maximum value that every value could be is the length of the subsequence, so if you want to operate something, the optimal way is to do this.
you can solve it in O(nlogn) time
dp[i] = max(dp[i — 1] + a[i], dp[j] + (i — j)^2)
You can use Convex Hull trick to handle the second transition
Oh you are right, I forgot this
very bad C, and nice D
Pretty good contest!
I liked D so much (the limit on the number of operations is chosen carefully!).
don't let these authors make contest Mike.
it's better to not let you write comments
it's none of your business
keep crying
as you kid
For my 1st contest i only managed to get A and B right lol
Can someone give me an hint for E1 pls ? It kept reaching the time limit on pretest 11 and I had no idea on how to reduce the time complexity. https://mirror.codeforces.com/contest/1956/submission/256528779
My guess is that pretest 11 being something like this:
Think about a sequence of 4 that looks like this: 0 1 100000 0. On this case you can just put the 3rd number on 0 and move forward saving a lot of time.
C is really great, it took me so much time tho, but I love this one.
10**100 is quite ridiculous.
Interesting problem description.
10^100 means it'll probably give the same answer as "infinity". It made that task fun, for me
It's just to avoid explaining "what infinite turns of operations means"
A: If number of players is not greater than a[1], the game is end, otherwise it will continue. Then the answer is min(n, a[1]-1).
B: Assume we have t pairs and n-2*t single cards, then the opponent will also have n-2*t single cards, and then, they have (n-(n-2*t))/2 = t pairs. Since we can always get t points from pairs, and we can only get other n-2*t points if we play these single cards after opponent plays the corresponding cards, we need to play pairs first and single cards later. So for the first 2*t turns both players will play all pairs, and then we can't get any point because the opponent will play the card we've played last turn. So the answer is t.
C: From the example for n=2 we can see we can't get {{2, 2}, {2, 2}}. In fact, for any n and pairs (i1, i2) and (j1, j2) with i1<i2, j1<j2, we can't make numbers on the 2x2 submatrix determined by row i1, i2 and colomn j1, j2 be the same. So there can be at most 2*n-1 occurences of n (they can occupy a row and a column), and for the remained n-1 rows and columns, there can be at most 2*(n-1)-1 occurences of n-1 and so on... Therefore, the maximum sum we can get is sum(i=1...n)(i*(2*i-1)=i*(i+1)*(4*i-1)/6. To achieve this value, we can make operation on the i-th row and column, from i=n to i=1, with p[j]=j.
D: Let f(L, R) means we want to make a[L]=0, a[L+1]=1, ..., a[R]=R-L. If L==R, we can achieve this by do operation on [L, L] if a[L]>0. Otherwise, we can first do f(L+1, R), then do operation on [L+1, R] to make a[R]=R-L, then do f(L, R-1). Therefore, for any range [L, R] we can make the sum on this range be (R-L+1)^2 by operations, which is also the maximum possible value if every element on [L, R] have been modified. So we can solve the problem by dp.
E1: Assume i-th to (i+2)-th monster survived for T turns. If in the last turn (i+2)-th monster takes D damage, then at j turns before, it takes at least D+j damage, so the total damage it take will be at least D+(D+1)+...+(D+T-1) >= T*(T+1)/2, which means T*(T+1)/2 <= a[i+2]. Therefore, if we let A=max(ai), then after O(sqrt(A)) turns, there will be no more than 2 consecutive alive monsters, then for any pair of adjacent alive monsters, the left will be alive the the right will die. So we can brute solve the problem by brute force.
E2: Similar with E1, there will be no more than 3 consecutive alive monsters after O(A^(1/3)) turns, but we need to calculate the total damage of the second monster, in order to determine whether the third monster alive for consecutive 3 monsters.
typo in solution for D, if L!=R, first do f(L+1,R) then f(R,R), not f(L+1,R) again.
For problem D, why we do we even need DP (we can) but isn't easier to brute force on all possible masks?
(I just want to understand I'm not missing something because of weak test cases, because I did this using normal brute force & everyone else seems to be doing DP)
In the D problem, when we realize that a segment of k elements can be filled with all value k, the problem is much easier. But I think it's quite hard to realize it, can you share your thinking flow to come up with it. Thank you
in E2 . what are u doing in this line of code.
how u derive the formula of dmg variable
``
upd :- understood . but my code is giving tle on tc 54. :( . anyone tell me what bug is there
https://mirror.codeforces.com/contest/1956/submission/256603484
In problem E1, how do you prove that we need O(sqrt(A)) turns ? I was able to come up with the idea but i couldn't figure out how many times i should run the simulation
Only needed 3 point for EXPERT but here C depressed me with 6 WA and will now get a negative delta :), my bad luck is really good :)
In problem c didn't we had to make matrix as
~~~~~ Your code here... ~~~~ 1 2 3 4
2 2 3 4 3 3 3 4 4 4 4 4 ...
For that first we will fill rows 1 to n with Permutation 1 2...n and then set n=n/2 and do the same with columns This was my approach why did it fail
Matrix should be:
your matrix is correct. you probably did something wrong with your construction of matrix. you can always go in either descending order or ascending order with descending permutation.
Here's how it would be constructed
0 0 0 1
0 0 0 2
0 0 0 3
1 2 3 4
Next Step:
0 0 1 1
0 0 2 2
1 2 3 4
1 2 4 4
and so on.
so use a $$$ lastRow $$$ and $$$ lastColumn $$$ and solve this with decrementing both of them.
Very nice problems. I am waiting to see the pretest number 21 on E2 :D. Maybe 15 more minutes would have been nice but maybe its just me that i am slow at finding solutions for problems like C.
very good round,make me back to expert AGAIN!
I love yuzusoft ans it's fans,because of u my friend.
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
Ciallo～(∠・ω< )⌒★
couldn't solve C 💩 bye bye rating
Not Gona Lie , Problem C really Sucked
C is beautiful, was stack for whole contest because was trying to construct
instead of
It's also easy to construct. Just use:
both can be constructed easily.
It would have been neater if C only outputted $$$\sum a_{i,j}$$$, and if D were given as $$$a_i\le n$$$. Personally, I found it a bit cumbersome to write unnecessary subroutines.
I think the hardest part of C was figuring out what operations it took to get to the intended sum, so it would've been way easier if we just wanted the intended sum.
same here
so basically you want guessforces; printing that the sum was n(n+1)(4n-1)/6 and was doable in 2n operations is something that could be guessed without needing an actual solution.
Coming up with a construction is what makes the problem a C problem and not a B problem
I thought it wouldn't be easy to guess just the value n(n+1)(4n-1)/6 without any specific process.. I see.
By the way I thought there would be some consensus on my opinions on C and D, but there are only downvotes lol
People can accidentally stumble into it if they go for the bad and non-generalizable method for $$$n=3$$$ and assume there must be a way to do it for $$$n \geq 4$$$ (the bad process being do all rows to set all rows to 123, do 1st and 2nd column setting those to 123, and then finally fix the top row again setting it to 123).
The C is too difficult for me to come up with the correct construction of the matrix. Huge thinking traps！ I determined to use the permutation to fill the matrix in the first n steps and all my attempts were on modification in the rest of n steps, which meant I will never get the correct answer!
Seeing the terrible rank and the very few people solving D I was regret giving up C at first,but regret giving up C too late after I know the solution. It's just impossible to think of this strategy if you start in a totally wrong way.
totally right, If you see my submission, I was making a WA attempts and realizing my mistakes, I solved the problem in a feedback loop of what I am doing currently wrong and before 5-10 min of contest realized what author wants
had exactly same thought from the constraint 2 * n, since n + n / 2 + n / 4 ... + 1 < 2 * n so it MUST has something to do apply operation n times on row, n / 2 times on col and so on. kek
same happened w me, i also used my first n steps in filling the matrix and ended up being stuck in a matrix
Can anyone explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??
Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??
Brick on random C again. Now you are my new nightmare photo boy.
When a person has a anime girl DP, Run as fast as possible XD
TLE on A on system tests. Nice Update: WA on E1 on system tests. Range of emotions throughout the contest xD
Now WA on E1
I sense weak pretests
Weak pretests for E2
What an excellent contest — well done!
TLE systest on A just for using maps instead of linear soln?
The intended solution is O(1) for each query
D is a really cool problem!
The lesson you should learn from problem C: Don't touch your f*cking keyboard if you're not 100% sure about your solution.
True
Newbies After Solving A & B :')
Lengthy statements even for A, B. Weak-pretests for literally every problem on the contest (A, B, D, E1, E2)
what does weak pretests mean
When you submit a code during a contest It does not get tested on the full tests instead some of them which are called pretests (This saves some time so that submissions don't get stuck in queue for a long time). After the contest the submission gets re-evaluated on the full tests.
Some times the pretests lack an important test case that a lot of people may fail because of it, Thats' why some people call them weak pretests.
i get what pretests are.. why are people calling them weak
Sorry,
Edited the comment.
meaning the solution passes for pretests but fails at system testing?
Yes
where is the rating update -_-
rating changes when? 2 contests have pending changes
look upd
edu rating change should be right after this round.. but still no updates. . tsk tsk tsk
...
My D received runtime error in the System test. I submitted it using C++17 (GCC 7-32). After system test, I submitted the same code using C++20 (GCC 13-64), and it was accepted.
Whe the rating changes for Educational Codeforces Round 164 will be applied after this round?
Leaving aside the weak pretest of E, it's a very good contest!
Ciallo～(∠・ω< )⌒★
what does weak pretests mean
During the competition, only the results of pretests will be displayed, and not all the tests will be displayed. However, the pretest for problem E in this contest is not comprehensive enough. That's what weak means.
it didnt work in O(n2) , i dont think it has weak pretests :/
what is the meaning of last announcment about rejudging ?
C is a beautiful problem with a simple solution. I have to accept that I am simply not good enough to solve these at my current level. One day hope to be able to solve problems like these fast.
Yes bro, Like it is very simple but we need make observation then it is very easy. I also not able to solve this.
Finally CM, thank you all!
those who solved C be like
``
I believe my solution idea 256566371 to E2 can be adjusted for much higher values of a_i, tho it's not too different then what seems intended by other comments (also my submission is current fastest btw).
As others, I use it will take A^(1/k) rounds for there to be at most k in a row. However, I can also solve for small k in a row in O(k^3 * lg(A)) time. To do this, I found formula for how much each previous value will change current one after exactly x turns (just analyze pattern by keeping values as variables). Now you just use binary search for how many turns rounds until they one becomes 0.
Now just find optimal k where brute forcing initial rounds is as fast as solving remaining small sequences, and using wolfram it seems that for n=2e5 A=1e18 having k = 8 will solve in reasonable time.
My solution for D (which I believe is intended) reminds me a lot of the tower of hanoi, which can be solved using a similar recursive idea.
Yeah, exactly my thoughts after reading the solution of YocyCraft. I thought it was some dumb bruteforce/bitmask dp and got stuck on that idea for a while, but that observation was beautiful.
Were the pretests for problem E1 and E2 purposefully made weak, to stop people from guessing the solution?
Well, I wrote the same solutions as intended. However, I got 2 FSTs in both E1 ($$$\mathcal{O}(nV^{\frac{1}{2}}$$$, TLE on 24) and E2 ($$$\mathcal{O}(nV^{\frac{1}{3}}$$$, TLE on 54) ...
Is this your submission for E1? 256524095 So you are sure the set does not add another log factor? (Didn't look too closely at the code). Even if it were true, sets are known for quite a big constant factor.
Is it intended that people who became orange from the edu round had the contest rated for them? Of course, I'm only asking because I did poorly ;)
Editorial?
Why weak pretest?? I made a very stupid mistake on D,but it still pass the pretest???
Codeforces Hot News! Wow! Coder bro_jie competed in Codeforces Round 939 (Div. 2) and gained ??? rating points taking place 1,151!!!!
WDF D>>>>>>>>>>C
Stuck on Div.2C for the first time ever!
good contest it is,nooooooooooob I am!
Why so many downvotes? I couldn't understand lol
How to solve D ? Can someone explain in simple words ?
what's the point making the limit of problem F so tight
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
There's a typo in the hyperlink for the editorial. it says codeforc.es instead of codeforces
correct editorial Link: https://mirror.codeforces.com/blog/entry/128426
there is a little typo in hyper link
My favourite contest so far. Unfortunately, I was not able to participate during the contest itself :(
Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).
I have a rather off-the-topic question.
I am fairly new to codeforces, having given only 4 contests so far. From what I read about the rating system, pupil ends at 1199 and apprentice begins at 1200. My rating after this contest got to 1200. Why am I still a pupil and not an apprentice? Apologies in advance for the question not being related to the contest.
I took the reference for the ratings from this blog: https://mirror.codeforces.com/blog/entry/68288
ig it was old rating system. now it is
Newbie < 1200
Pupil 1200 <= rating < 1400
and the other ones are mostly same.
very badly worded problems.
The contest was good even though I didn't rank high
Ciallo～(∠・ω< )⌒☆
As a grade 10 student, I must said that you are really talented. The best student in my school (my classmate) only reach master.
Oh well same here
Can anyone explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??
Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??
Authors did correct thing only including $$$n = 1, 2$$$ testcases. I am sure, that there are two ways how to come up with the solution. $$$1.$$$ I tried to solve $$$n = 3$$$ case and after getting one non-trivial result i sent it and get AC. The second way is try to prove bounds, but it's not necessary during contest
I agree with solving for higher n like 3,4. But even when solving for n>=3, I would have followed the same pattern as n = 2. So I don't think I'd have come up with the correct approach anyway. So I am more interested in the idea itself, and you being a master what do you think is it due to my lack of knowledge about different concepts, or due to lack of problem solving skills and observation skills like I should have observed this pattern? I really really want to improve but problems like this just exhaust me completely and this feeling is worst.
my account is public so that my code is accessible to everyone. It's not fault. Please save me for this time. It will occur again in the future
Upsolved E2, shouldn't it be "Meguru VS. Monsters"?
That way C can be renamed as "Touko's favorite cake". So where can Tsumugi and Wakana show up?
well I got to %%%
I think it's super mentality
Wish I started at his age, wow