Salam, Codeforces! $$$\color{white}{\text{ «Be attentive about your thought that becomes your behavior» «Be attentive about your behavior that becomes your speech» «Be attentive about your speech because it becomes your habit»«Be attentive about your habit because it becomes your personality»«Be attentive about your personality because it becomes your destiny» Said by: Imam Ali}}$$$
We're so excited to invite you to take part in our round Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) which will start on Aug/26/2023 17:35 (Moscow time). The round will be rated and open for everyone.
The problems were prepared and authored by amenotiomoi, Dhruvil Psychotic_D Kakadiya, Han wuhudsm Jinlong, Amir Hossein Amir_Parsa Farhadi, Matthew chromate00 Roh, JohnVictor, ODT, ugly2333, EternalJourney, RiverHamster, MagicalFlower and AquaMoon.
We would like to thank :
- irkstepanov for coordinating the round;
- aaaaawa, BurnedChicken, p_b_p_b and Sugar_fan for LGM testing;
- hibye1217, alireza_kaviani, errorgorn, JianfengZhu, AmShZ, Crying, Huah, bthero, fengzhengwei and Ecrade_ for GM and IGM testing;
- Kieray, k1r1t0, Arpa, triple__a, blxst, leukocyte, ITO and NemanjaSo2005 for M and IM testing;
- tbank, StelIawinD, callmepandey, Mkswll and uuku for CM testing;
- WrongAnswerOnTest3, KitasCraft, aayushdhankecha, Qualified, Nanani, KINAN and tllwtg for Expert testing;
- Hex-willappear, Savani004, AkibAzmain, Visrut_, Banis and Harshil4442 for Specialist testing;
- strange-creator for the only Pupil testing;
- Valenz for the only Newbie testing;
- MikeMirzayanov for the great Codeforces and Polygon platforms;
- And at last but not least, You for participaing in the round!
You will be given $$$9$$$ problems and $$$3$$$ hours to solve!
Score Distribution:
$$$500-1000-1250-1500-2000-2500-3000-3500-4250$$$
UPD1 : Editorial is out.
UPD2 :
First Solve
| Problem | Name |
|---|---|
| A | qiuzx |
| B | noimi |
| C | SSRS_ |
| D | Um_nik |
| E | Geothermal |
| F | MysticPanda |
| G | Radewoosh |
| H | maroonrk |
| I | Radewoosh, One and only Orz |
Top Performers
| Rank | Name |
|---|---|
| 1 | Radewoosh |
| 2 | maroonrk |
| 3 | EvenImage |
| 4 | Benq |
| 5 | Um_nik |
| 6 | jiangly |
| 7 | SSRS_ |
| 8 | noimi |
| 9 | hos.lyric |
| 10 | Brewess |
GL & HF ;)
This round wouldn't have been possible without Harbour.Space University's support.
This contest is for all interested eligible programmers who want to start their bachelor and master studies in Barcelona, Spain or Bangkok, Thailand, and join ICPC team.
For the next academic year (2023/24), Harbour.Space University is recruiting a fascinating community of competitive programmers from the top prize-winners of international Olympiads to join one of several competitive programming teams at the university.
In the next few years, their goal is to continue winning SWERC and competing at a high level in the ICPC globally. Therefore they want to invest a serious amount of energy, resources, and talent into these activities.
That’s why you are invited on an exciting journey in the company of like-minded people, outstanding coaches, and ongoing partnership Harbour.Space University with Codeforces.
Over 100 educational rounds were already organized, so the time has come to test our joint efforts and reward the most diligent.
Here’s what you win if you place in the contest:
The monthly living allowance throughout the entire duration of studies may vary depending on the overall performance of the students as measured by their GPA, professional achievements and official ICPC competition results. As a guideline, it is in the range of 700-1500 EUR (it might be applied to the contestants who win 4th-10th places).
No application fee is required for any of the awards listed above.
Good luck, and may the code be with you!
Finally the first official round of TheForces, I am so happy at this moment and looking forward to your wonderful feedbacks and participation, Good luck!
TheForces Orz...
"I did nothing for this official round, but I did most things for TheForces"
O--O
Excitement limit exceeded !!
This is my first time as an author. I hope you will enjoy the problems.
Orz Radewoosh.
There is an inconsistency, Round says (Div 1 + 2), 9 problems and 3 hours whereas the scoring distribution is for a 7 problem split Div 1 and Div 2
Thanks, updated!
Thanks, combined rounds give me immense joy <3
It was my first time testing codeforces round, I am so happy!
Orz k1r1t0
Excited for your first round as an author my friend amenotiomoi :)
😎
Welcome to the first official contest of theforces, hope you enjoy our problems (including my problems)! (≧ω≦)
As a problemsetter, I hope everyone enjoy the experience in the contest!
Orz chromate00 round!
OMG Psychotic_D round!
Thanks.
As a Tester, I am here to comment :).
As a tester, I am also here to comment :))
As a tester, I enjoyed the round and found some very nice problems! I recommend you to participate.
As a tester, I recommend all of you to participate in the contest. It's a classic one.
First time as a tester I recommend you to take part in this round!
definitely sir!
callmepandey Orz
TheForces to Codeforces... orz!
as a first time tester, the problems are very nice to do :]
As a non first time tester, the problems are quite nice and I hope you have fun solving them.
AquaMoon + TheForces contest , can't get better than this
Thanks for your support, have fun and good luck! (●'◡'●)
As a tester, I wish you good luck and have fun solving these cool problems :)
First time as a tester! I hope you can enjoy these problems.
it's my first time being a tester ~ hope u enjoy the round
How can I be as good as you, Nanani. You are already a test for a codeforces round which is a achievement I've never reach. I hope I can one day be as 1% good as you, Nanani.
Just DM problem-setters lol, you can be our rounds tester next times if you wish ...
Orz ODT round!
As a first time tester, hope you all can have fun and also get positive delta.
As a tester i did not realize the blog has been posted xD
Are placements calculated from everyone who participated in the contest, or from those that applied for the university? As it says "Awards are distributed to those who are interested in pursuing..." in the picture, but the description says "if you place in the contest".
So many testers that none of the comments are participants
First time seeing score of any problem is 4250. Interesting to see who is able to solve it first
By the way, for reference, there once was a task with 5000 score in another round.
The last Harbour.Space Scholarship Contest had a 5250 score (The score does not mean much though, the problem had 13 solves)
AkibAzmain bruh how were the problems ?
You'll enjoy them for sure.
TheForces Orz
I got impressed by your creativity in indicating 'You' as legendary grandmaster colour( in last point of thanking ) .❤️
Lord spotted of TOAS
As a tester: the problems are cool!
Very good, I need to sleep well before the contest starts
If these turning epochs do not move with aw will today, the spheres of time are not constant do not grieve, Poem by Hafez Shirazi
Nice poem in the announcement :)
As a tester, I tested the round.
OOOh, thank you very very very very very much.. I don't know what would have happened if you didn't tell us. Now, I started thinking of searching for another CP site.
You do know that CP sites are illegal, right?
Hello Contest Organizers, I'm new to the platform and have never tried Div1 + Div2. Should I register ? Would this make my rating fall bad if I could only solve 1 or 2 problems?
As a first time Codeforces round tester, I'm pretty much sure that everyone will enjoy solving the problems.
is score related to rating range of a problem?
It is related to the team's (setter/tester) subjective thoughts about the proportional difficulty compared to other tasks. It may or may not correlate to absolute rating, but we do aim for it to.
As a participant, I am writing this comment just to comment :)
Loved that you... That was precious... Few people know these things...
Thanks MikeMirzayanov for black testing
First time testing an official round.
The experience was awesome and I've learned a lot of things.
As a tester, I can say that the problems are really interesting. GL&HF
Congrats to TheForces for having their first official round!!!
220364168 what is wrong in it for 1779C - Least Prefix Sum
As a tester, the problem setters are not retarded.
I may be able to solve problem D this time.
"If these turning epochs do not move with aw will today, the spheres of time are not constant do not grieve, Poem by Ha"
All the best
Is it rated for codeforces rating??
yes
TheForces Orz...
Eligible for what?
Hope a good round! Hope I won't become expert today :(
Should I participate this contest to become pupil? Or even after solving question i will get negative delta?
You should not think about neg delta. If not in this contest, then in future you will become pupil. But , if you miss this good contest which is even rated for LGMs then, you will miss a good experience that you could have done.
Indeed its true i will participate for sure, but im really frustrated with my progress
If you are frustrated by your one then have a look at mine :)
dude ur graph is amazing
VivaciousAubergine, for not testing.
It's been 8 months since my last (Div. 1 + Div. 2) Contest. I'm eager to reclaim my BLUE rating once more.
any 「Chtholly」？ or at least one block-divide algorithm problem，right？XD
In my mind E is always a DP problem. Will it...?
Nope! Well, maybe it might be, but my approach (please don't FST) was limited to MSD-RadixSort, bit manipulations, and basic combinatorics.
Me too. I'm surprised that there are no DP problems from A to E...
I thought D is a DP problem. What's your approach?
No.
isn't D dp?
I think it's a greedy & brute force problem. :)
i solved it with dp idk how to solve it greedly
I saw your solution by adding you into my friend list(and see your code in "Friend standing"). I think what you were doing can be classified as DP.
EDIT : I misunderstood your solution. I am too stupid,.
220542661
How? Do you mean
down/sumto/difftoarrays? I think it should be from the lazytags in Segment Trees..9 problems & 3 hours! Amazing! Good luck!
Looking forward to solve 2 out of 9 problems.
Good luck! Hope u can solve 3!
I liked problem C.
Nice problemset. how to solve D i am thinking like a range for each one then crossing out the zeroes in that range ?
greedy
Iterate over rows from top to bottom. Notice for each 1 that remains in the current row, you are forced to use an operation.
Thus, the idea is to loop over rows from top to bottom and count the number of ones. Then, you have to find a way to efficiently store the effects of the operations on future rows.
This can be done by keeping track of the number of operations performed on each diagonal and using prefix sums for each row.
My submission: 220552191
How can I get abdnp from this input? in Problem B
Thanks!
I thought for 2 hours that the right solution was wrong because I did not found a way to do it.
In a case like that you should implement brute force (takes less than 5 minutes) and run it locally. It's instantaneous to BFS all possible operations for small strings.
.
abndp -(2)-> apdnb -(1)-> dpanb -(2)-> dbnap -(2)-> anbdp -(1)-> adbnp
So all downvoters, can you please explain, what made you downvote my comment? It answers the question.
The original question was:
How can I get abdnp from this input?
But you showed how to get adbnp, not abdnp.
So no, your comment actually didn't answer the question.
Ah, didn't notice it. Yes, you are correct.
10 more minutes and I'd have E, :(
10 more seconds and I'd have F, :(
5 more seconds and I'd have C.
for B how to prove that even window = sort the whole string?
If the window length is even then reversing the string will change parity of all values,thus each value can be positioned at any index(both odd and even) using two types of operations.
Because of the first kind of operation you can sort all the odd indices and even indices separately. Now if the other kind of operation allows to swap characters at the end of an even window then you can use it to send any odd index element to even index. This allows us to sort the whole array.
you can swap the parity of the indices with even k, but then you have to change the parity of k/2 odd,even pair at the same time. How do you get from this to sorting the whole string
Suppose if you sort the whole string you know which characters are at odd and even indices in the final sorted string. Then you can use the second operation to change the parity of any character that is not in it's correct parity list and finally sort it using first operation.
Assuming you got the part when window is odd. position 0, 2, 4 .. will be sorted position 1, 3, 5 .. will be sorted
Now, you have arrived at this, then you can change the parity of any element with even window which again can be sorted with i, i+2 swapping,
what i don't get is you have to sort the entire window of k.
Like k = 6 and s = 231564 in this case all the odd and even indices got swapped at the same time, so 1 and 2 would always have the same parity, but what you want is 12...
In the constraints it is given k<n every time all odds and even wont get swapped
Think of it in this way, let's say you have $$$2$$$ components (graph) of even indexes and odd indexes. Reaching from one node to another means you can swap these $$$2$$$ indexes in the original string. Now if, $$$K$$$ is even that means you have an edge between the $$$2$$$ components of graph making it a single big component, while if $$$K$$$ is odd, parity of swapped indexes will not change, and they will still lie in the same component as their original one.
.
Let
1represent a character than belongs at an odd position ($$$1, 3, 5,\dots$$$) in the sorted string and let0represent a character that belongs at an even position ($$$2, 4, 6,\dots$$$) in the sorted string.Lemma: If we can make the string
011010...10101equal to101010...10101, we can always sort the original string.We can rearrange the elements on even positions in any way we like, same for odd positions. The operation described in the lemma swiches the parity of position of two characters — one odd position changes to even and vice versa.
If we find a construction for the operation in the lemma, there must be two indices $$$i_\text{odd}$$$ and $$$i_\text{even}$$$ such that the parity of positions of only these two characters changes. If we wanted to swap two specific characters (on different parities of position), we can move one of these to $$$i_\text{odd}$$$ and the other one to $$$i_\text{even}$$$, do the operation of the lemma, and rearrange all even characters and all odd characters to their original state, with the two chosen characters swapped. Thus, this allows us to swap any two characters we like.
This means that we can reach any permutation of the characters, and the answer will be the sorted permutation. $$$\square$$$
Construction:
Start by moving the incorrectly placed
0(first character) as far back as possible. Now our string is111010...10100.Now, reverse the first $$$k$$$ characters. Now our string is
[0101...010111]10...10100([]contains the reversed part).How many incorrectly placed ones
0's our string currently have? Before the operaiton, we had one such0. Every0included in the reversed segment was good, so now they're all bad. The reversed segment included $$$k/2$$$ elements at an even position, one of which was a1and the remaining $$$k/2-1$$$ were0's. These now became bad, so we have a total of $$$k/2$$$ bad0's.The above is true if and only if the bad
0we moved to the back of the string is not included in the reversed segment. If $$$n$$$ is odd, the0was moved to position $$$n$$$ and definitely wasn't part of the reversed segment, because $$$k \lt n$$$. If $$$n$$$ is even, the0was moved to position $$$n-1$$$. Because $$$k \lt n$$$ and $$$k$$$ is even, $$$k \le n-2$$$. Thus, the0wasn't part of the reversed segment. $$$\square$$$Now, we have $$$k/2$$$ incorrectly placed
0's. Thus, we also must have $$$k/2$$$ incorrectly placed1's. We can move all of these to the first $$$k$$$ positions of the string and reverse that segment, making all of these good. This concludes the proof that it is always possible to do the operation required for the lemma, which proves that the string can always be sorted. $$$\square$$$Let A be the minimal set of odd index values we would like to be even, and B be the minimal set of even index values we would like to be odd.
Clearly |A| = |B|
By induction, we only need to decrease the size of these sets.
Place some value of A at index k-1, and some value of B at index k
Preforming the window operations [0, k-1] and [1, k] will only change the parity of the values at index k-1, and index k.
So the order of |A| and |B| decrease.
Loved Problem D AquaMoon, E was also good but i couldn't implement in time.
Thank you so much, i am so happy that you love my problem! (〃'▽'〃)o
As a small point of feedback, I wouldn't use $$$(x, y)$$$ to refer to row $$$x$$$ and column $$$y$$$, the $$$x$$$-axis is usually horizontal / $$$y$$$-axis is usually vertical. Maybe use $$$(r, c)$$$ instead. Otherwise thank you for the contest!
What is the pretest #3 of problem G?
Dunno if this is helpful, but I initially failed this because I multiplied by $$$k$$$ instead of $$$k!$$$ when rotating some subset of $$$k$$$ rows. Fixing that got me AC.
Dunno but my solution ended up being very simple — rotate all you currently can in one direction (horizontal/vertical), switch direction, repeat.
Since I'm doing this for both initial directions, I had to handle $$$A=B$$$ as a special case.
OMG genius implement, helps a lot
I like the contest for today D is so good i liked it so much C i got it too late , i was thinking of number theory soultion but it was bitmask
Nice contest, thx!!!
I become Expert)))
Congo!
Thx!!!
thanks to authors for the great round, simple problem statements and interesting problems
Plus a,b,c,d were very balanced. Slight sudden difficulty jump at e-but obviously nobody can optimise all the problems to be perfectly balanced.
I figured out how to do D when it was about more than 1 hour left, but couldn't implement it...
Expecting the solutions~
submitted E 9 seconds before the end but it showed contest is over. i will have a huge negative delta, if E is correct then i don't know what i will do.. i'm crying right now
If your solution for E is correct then it means you are able to solve it. The contest is over only means that it doesn't receive more submissions to judge for the standings and the rating which you can still earn whenever there is contest, it's not over for your journey on solving them.
For me I need about more 5 seconds to submit solution for C.
Cheer up bro! Let's get ready to revenge in the upcoming contests!
Thank you actually, after all if i deserve a certain rating I will get there no matter what happens, wish the same to you, and yes, i will certainly get ready for a revenge!!
Glad to hear!
Any hints to solve D? I tried 2D Fenwick Tree, but it gave TLE.
See my comment for my solution
Just do greedy?
DP, kinda like https://leetcode.com/problems/minimum-falling-path-sum/
AC with 2D Fenwick tree: https://mirror.codeforces.com/contest/1864/submission/220595323
Good contest overall. Thanks for this round! :)
C is sooo brilliant!! And how everyone is genius can be seen from the number of acceptances of C and E!
wuhudsm has always been orz in problemsetting
Can you explain c ?
What is the intended solution for F? My approach was for a query [L,R] first check if L==R if yes then only one operation is needed otherwise we need to bring all element in range [L+1,R] to L and then use one operation to reduce all to 0 but it gave WA on pretest 5. Submission: 220592550
I think it's the same as my solution — for every pair $$$A_i = A_j = v \in [L,R]$$$, check if the maximum value $$$\lt v$$$ that lies between $$$i$$$ and $$$j$$$ is $$$L$$$, if yes then it adds one operation since we can't make both $$$A_i$$$ and $$$A_j$$$ zero "together", there have to be operations changing that maximum $$$\lt v$$$ between them to zero, then some separate sets of operations changing $$$A_i$$$ and $$$A_j$$$ to zeros.
Yes my approach was also similar. For every a[i] I found the ranges it covers consisting of elements greater than or equal it then used a prefix sum array to calculate the total cost. Could you tell what was wrong in my approach?
Maybe you oversimplified things. That sounds like way less than I had to implement.
Ya ig i did oversimplify it. Thanks tho.
GapForces
I didn't expect G to have so few ACs during contest.
I could've tried to guess stuff. Instead I tried to figure out a rule, which was quite tough and wrong logic sent me in wrong ways a few times. In comparison, A-F was straightforward thinking (only difference being the amount of thinking), but more of writing down code and optimising it. When you have enough experience, that's a lot easier.
I think G implementation was quite painful (finding the shifts, then finding the ordering constraints, then doing a topsort), and there's special cases like all row/col shifts only (which I failed to recognise in contest)
Because $$$O(n^3)$$$ is allowed, the implementation isn't actually that bad.
You can just scan for all rows/columns to see whether you want to shift this row/column or not every time.
why still not start pending
I would like to know which problem is made by ODT
seeing the submission count of c question i think brains have evolved
I solved C and submit it and it got passed but I thought it could be give Integer overflow therefore I again submit the solution later and my score got decreased why? :(
I loved problem E, thank authors for the good contest!
someone could give me a code with B?
https://mirror.codeforces.com/contest/1864/submission/220551208
thank you !
C>>D
Can you please explain how to solve D?
The optimal way is to invert any element whenever you find 1 in the matrix starting from the 1st row.
yes i know that
The toughest part is implementation.How to do that?
220577176
C: In 20 minutes created, proved and coded solution
D: In 2.5h couldn't get with anything faster O(n^3) :D
true
As someone who is not good at math, I found Problem C much more difficult than Problem D. I spent too much time on Problem C and didn't pay attention to Problem D. That was a lesson learned.
It's interesting to think about math from a binary perspective :)
Nice round, thank you!
Beautiful problems. It's been a while i've seen problems like these. Though i think C and D could be swaped.
Was the 1000 used as the upper bound in Problem C deceptive or is there any solution intended?
Can anyone explain how to solve E ?
Let's understand how to count the number of turns for A and B. Alice looks for the first 1 in A|B (suppose its position is i). If A[i] == 0, she understands, that B[i] == 1, so A < B. Otherwise she can't say anything exact, because B[i] can be either 0 or 1, so she skips. Now it's Bob's turn. If B[i] == 0, he understands, that A[i] == 1 and A > B. Otherwise he looks for the next 1 in A|B and the situation repeats. In general, let's define C as the number of 1's in LCP of A and B. If C is even, the answer is C + 1, otherwise C + 2 (corner case A == B, the answer is always C + 1)
How to count the answer for the problem? We can iterate k = [1, n] and choose A = a[k]. We can use trie to count for each prefix of A the number of B's, such that current prefix is LCP for A and B (suppose this number is P). Then we should add (P × number of turns) / (n × n) to the answer.
My submission: 220583318
Consider the positions of the 1s in the OR value. When I refer to position, I am talking about these specific positions with 1 in the OR, skipping all the positions with 0 in the OR.
If Alice has a 0 in the first position, she knows the 1 came from Bob, so her value must be smaller, allowing her to end the game. Otherwise, if she has a 1, she doesn't know whether Bob has a 0 or 1 here (or about later positions, if any), so she answers "I don't know".
When Alice answers "I don't know" on her first turn, then Bob knows Alice has a 1 in the first position. Now, if Bob has a 0 in either the first or second position, then he knows his number is smaller, and ends the game. But if he has a 1 in his second position, then he answers "I don't know".
More generally, if both players have 1s in the first $$$k - 1$$$ positions, then the first $$$k - 1$$$ turns are all "I don't know".
Side Note: If Alice and Bob first differ at the $$$k$$$-th position, then the $$$k$$$-th answer depends on whether the person who is answering has a 1 ("I don't know") or 0 (smaller) in this position. So there are either $$$k$$$ turns or $$$k + 1$$$ turns, depending on who got the smaller value. This might sound annoying, but it's actually easy to handle when we deal with it later.
So how do we count the expected number of turns? We can first count the total number of turns for every possible pair. But there are $$$n^2$$$ pairs, so we cannot afford to consider each pair one by one. We need a more efficient way to count them.
My approach for calculating these turncounts involves MSD-RadixSort. We separate numbers based on whether their first bit is 0 or 1, then for each group, we separate them further based on the second bit and so on. At the $$$d$$$-th level, given a group, their first $$$(d - 1)$$$ bits all match and we can keep track of how many 1s are there to get the value of $$$k$$$. Then, if an unordered pair is formed by any number who has a 0 in the considered digit position and any number who has a 1 in the considered digit position, this will result in a turncount of $$$k$$$ or $$$k + 1$$$. Since we actually need to count ordered pairs, we add both $$$k$$$ and $$$k + 1$$$ to our total turncount (one corresponds to whether Alice gets the 0 and the other to whether Bob gets the 0, but we don't care which is which, and this keeps changing when $$$k$$$ updates anyway), i.e., multiply the number of unordered pairs with $$$2k + 1$$$.
Finally, we need to consider the base-case, when we have a group where all values are equal. The MSD-RadixSort stops here, but it is possible for Alice and Bob to get the same value, which would also be equal to the OR value. If this OR value has a total of $$$k$$$ 1s, then there will be exactly $$$k$$$ turns of "I don't know" and then on the $$$(k + 1)$$$-th turn, the player will realize there are no positions left, and that they both must have the same value. The number of ordered pairs is equal to the size of the group squared (recall that both players might get the same index), and the turncount is exactly $$$k + 1$$$. The case where one or both players get the number 0 is correctly handled here (no need for an exceptional edge case check).
Finally, don't forget to keep spamming the mod operation and to perform modulo division of the calculated total over $$$n^2$$$ (total number of ordered pairs) to get the final expected value.
My submission: 220592883 (may have to wait until System Testing is done to see it)
I think problem D is boring and easier then D from other contests.
yes but i the implment for D is hard
Just to mention, task D did not exist in the initial problemset. E was originally right after C, which made the gap very large between the two tasks. So, task D was added to alleviate the gap.
I think E >> F.
Both Alice and Bob are smart enough.It's quite hard to be as smart as Alice and Bob LOL.
Very unfortunate to have spent an hour writing a brute force solution to E and then 40 minutes looking at a computer screen. But the contest was good.
lol 暴力 is not 'violent' but 'brute force'
Sorry for that, thanks :(
Can anyone Explain How in E if a = 2 and b = 3 number of turns are 3.Like first alice think a|b = 3 so b can be 1 or 3 ,then turn will shift to Other person ,he thinks a might be 3 or 2 or 1 ,what ahead?
Third turn: Alice knows that b = 1 or 3.
If b = 1, then Bob would know that a = 2 or 3, leading to b < a, which stops at second turn.
So Alice knows that b = 3, then she knows a < b, which stops at third turn.
For problem D, I implemented a O(n^3) solution by greedily selecting '1' in row major order and updating subsequent rows using prefix sum array structure. How to solve in O(n^2)?
I did some sort of lazy propagation: updating only the next row, but keeping the information (that this update needs to be propagated further).
My solution (in Golang): 220584229
This changes the time complexity to (n^2).
Instead of updating prefix sum array in each row, memorize where should the increment + decrement in the array should happen if you were to construct the prefix sum array at current row. To be specific you can maintain two counter for each column index, specifying how many increment and decrement should happen in each square. Then, whenever going down a row, the increment counter would shift left by one square, and the decrement position would shift right. You can then use this information to construct that prefix sum array in O(n) for each row, and update the counter in O(n) whenever going down a row
Same as above, but using C++: 220587779
Can someone give a solution for C?
If x != lowbit(x): x -= lowbit(x) else: x /= 2
Thank You!
.
Because you are extremely strong.
Woohoo it starts!
220542661 I hope I won't TL...
Why I change my code a little and submit again,then get skipped?
We fixed the testcase with $$$n=1$$$, and rejudged all affected solutions. Your first submission on D was affected as well, and the rejudge made your second submission give a penalty due to resubmission. Therefore, we skipped the second submission to fix the issue. Our sincere apologies.
Thank you
Am I the only person who got mad at problem A because the input order was $$$x, y, n$$$ rather than $$$n, x, y$$$?
How does subtraction of divisor relate to turning off lowest significant bits? How does it even ensure that we never repeat any divisor of subtraction twice ?
I couldn't solve it, but this is pretty interesting. It is not that hard, just think about it.
I went about it like this:
If n = 2^k then we can at every step subtract it by n/2 to finally reach 1 using every number exactly once. Eg: 8->4->2->1
Now suppose the highest set bit in the binary representation of n is k. Then we know that we can reach 1 from 2^k. Now how to reach 2^k from n? At each step we turn off the LSB of n from it till it reaches 2^k since the number formed by the LSB always divides the number and using this operation we use each number only once.
Our construction will consist of two phases; we will show that each divisor is used at most once per stage.
Let $$$x$$$ be our current value, and let $$$k$$$ be the largest integer such that $$$2^k \mid x$$$ ($$$a \mid b$$$ means $$$a$$$ divides $$$b$$$, i.e. $$$a$$$ is a factor of $$$b$$$). If $$$x = 2^k$$$, we move onto the second phase. If $$$2^k \neq x$$$, then $$$x = 2^k \cdot q$$$ for some integer $$$q \gt 1$$$. $$$q$$$ must be odd; otherwise $$$2^{k+1}$$$ would divide $$$x$$$ and $$$k$$$ wouldn't be the largest such integer. If we choose $$$d = 2^k$$$ and replace $$$x$$$ with $$$x - d$$$, we get
$$$x_\text{new} = x - d = 2^k \cdot q - 2^k$$$
$$$x_\text{new} = 2^k(q - 1)$$$
Because $$$q$$$ was odd, $$$q-1$$$ must be even. Thus, the largest $$$k_\text{new}$$$ such that $$$2^{k_\text{new}} \mid x_\text{new}$$$ is at least $$$k + 1$$$, so we won't repeat the divisors during the first phase.
In the second phase, we have $$$x = 2^k$$$ for some integer $$$k$$$. While $$$x \gt 1$$$, we can keep choosing $$$d = 2^{k-1}$$$ and replacing $$$x$$$ with $$$x - 2^{k-1} = 2^k - 2^{k-1} = 2^{k-1}$$$. Thus, we won't repeat any divisors in the second phase and we will use each divisor at most twice, which is enough to solve the problem. $$$\square$$$
I used the concept of meet in the middle. Suppose x is 39, I define the 'middle' as the biggest power of 2 less than or equal to x. In this case, the 'middle' is 2^5 = 32.
From 1 to 32: 1 -> 2 -> 4 -> 8 -> 16 -> 32 (Each jump is using a different number)
From 39 to 32: 39 -> 38 -> 36 -> 32 (This has to do with the lowest significant bit.) (Each jump is using a different number)
I have a completely different solution for problem C.
For a given value of $$$n$$$, I assume that there is a solution only considering divisors of the form $$$\frac{n}{p}$$$, where $$$p$$$ is any prime that divides $$$n$$$.
Given that it’s not obvious which $$$p$$$ we should use in each step, I literally try every possible value with backtracking, keeping track of the amount of times I used each divisor with a map (to avoid using them more than two times). As soon as I found a solution, I stop.
Note that in each step of the recursion, I factorize $$$n$$$ in $$$\mathcal{O}(\sqrt{n})$$$ to get all possible values of $$$p$$$.
I have no idea why this solution works, and also why it’s fast enough.
Here is my submission: Link :)
Ruled it out, thinking it would/should TLE.
It passed systest with 139 ms :)
Yep, this similar solution appeared in the testing. It seems that considering the smallest $$$p$$$ possible is enough for the selection of $$$p$$$ in your solution.
If you don't understand why the solution works, do not worry. Neither did I
How to do B?
Sort the string directly when k is even, otherwise sort the odd and even positions separately.
My solution: 220536553
You mean when K is even? Can you explain why does it work?
First for operation one, he can change the odd and even parts of the string to any sequence respectively;
Then for operation two, it doesn't make sense if k is odd, otherwise he can swap characters in odd and even parts.
hi i did this idea but gave me wa can u tell me whats wrong? submission
Why did you use reverse at the end?
i thought i need to reverse the substring of length k when i find out that last char is less than the first char ( didn't think i don't need this operation back then) but doesn't that mean it shouldn't affect the code? because i already sorted the chars which in the same component ( so the condition won't never be true)
But reverse is left-closed and right-open, and the second operation in the problem is in the range $$$[i,i+k-1]$$$, note that $$$-1$$$.
Why am I still in queue...
Omg the queue is down...
Oh it works again!
Problem E teaches us all that when someone says "Mine is bigger than yours", this person is likely not intelligent and cannot be trusted to speak honestly.
Video Editorial For problem A,B,C,D.
Very quick, nice work!
Really liked the problem C. Unfortunately couldn't solve it during contest...
Great contest; felt like authors actually cared about the + Div.2 part of Div.1 + Div.2. Thanks guys!
Hey, why was my first solution for A skipped?
I submitted it after 11 minutes and it should be correct. My second submission was after 2h52m and got accepted but it gets 200 points less.
You submitted it twice, your second submission will be counted as the main solution
Yes, i know. But why??
It is almost the same code. If I had not submitted the second time, I would have gotten 200 points more. (i.e. resubmitting scores me lower, why?).
UPD:
https://mirror.codeforces.com/contest/1864/submission/220611176 This shows that my first solution was correct on system tests.
UPD2:
with ~260 points more i would place ca 5200 instead of ~5950.
You should not submit duplicate solutions, cuz it leads to penalty for you, please read codefores contests rules.
ok, i found it.
I want to apologize for my discontent. sry.
(its just the purpose of this rule... but thats how it is...)
Does anyone know why this submission TLEs for F on test 49 with C++20, but the same one passes comfortably with C++17?
Same with C++20 vs. C++17
It is related to this blog. I modified the input part of your solution (in particular, inputting all the values before pushing them into vectors) and it gets AC with C++20(64): 220609849
I tested a hanful of TLE49 solutions, including mine (unironically all are submitted with C++20(64)), and they all passed with C++17 or doing the modification above. I have no idea why that works...
Could anyone that knows python give me explanation why the time differ so much in problem E? I use Trie to solve problem E.
During my contest, In the submission 220592727
It gives me TLE many and many times, and cause me lose big rating. Then after the contest, when I read other's solution, make the submission:220607127), only change the node structure to:
It passed within 2 seconds. Why they are making so big difference?
Radewoosh congrats with winning scholarship in Harbour.Space!
All the problems I did were great, this is honestly one of the best rounds I've competed in. I solved A-D and almost solved E in the last 5 minutes but forgot to mod n^2 before calculating the mod inverse :(
Same error as me! Doesn't matter, still a good contest
The memory limit of E may be a little small because...
A poor guy is hacked!
In problem b, how this test : cdba will be abcd with k=4
K can't be equal to N
One of best contests ever thx guys
Happy that I solved first 3 problems in this contest , but could have solve little faster to get good rank.
I really like problem C. Thanks.
Nice Contest
Plag check going on ? After these many weeks Ratings are rolled back deyumn.
I got -1 when I was at 1599 Rating, now I hope I get +1 to 1600 and become Expert :)
Congrats!
Thanks Brother <3 !!
Congrats on Specialist mate!!
Thankss
Incorrect plagiarism in Question D: The approach to the question used by many people is quite similar due to the structure of the question: just 3 DP matrices, and because of this, the structure of the code of a lot of the submissions is similar. Please look into this.
nice contest