Hi Everyone :)
I would like to invite you to my first Codeforces Round, which I set with my friends JaySharma1048576 and mexomerf — Codeforces Round 921 (Div. 1) and Codeforces Round 921 (Div. 2) which will be held on Jan/27/2024 17:45 (Moscow time). This round will be rated for both divisions.
Both divisions will be given 6 problems and 2 hours to solve them.
One of the problems may be interactive. So, you are advised to refer to the guide on interactive problems in case you are not familiar with them.
We would really like to thank:
- Aleks5d for coordinating our round.
- jtnydv25, dario2994, IceKnight1093, oursaco, satyam343, Riladavin, magga, peltorator, _Enigma__, Makcum888, ItsNotMeItsYou, htetgm, 18o3, sezal, alwyn, somplz, nor and kevinsogo for testing and improving the problems.
- abhidot for listening to our problems even before we proposed them.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- You for participating.
Good luck, have fun!
UPD: Scoring Distribution
Div. 1: $$$500 - 1000 - 1500 - 1750 - 2500 - 3000$$$
Div. 2: $$$500 - 1000 - 1250 - 1750 - 2500 - 3000$$$
UPD: Here is the editorial
UPD: Congratulations to the winners
Div. 1:
Div. 2:
First solves -
Div. 2:
| Problem | Participant | Time |
|---|---|---|
| A | jayeshkriplani007 | 0:01 |
| B | Ianlsam | 0:02 |
| C | rolandpetrean | 0:08 |
| D | Ignut | 0:16 |
| E | CoanCoan.com | 0:38 |
| F | HexShift | 1:13 |
Div. 1:
| Problem | Participant | Time |
|---|---|---|
| A | Geothermal | 0:02 |
| B | Benq | 0:15 |
| C | gisp_zjz | 0:13 |
| D | Rebelz | 0:28 |
| E | gyh20 | 0:32 |
| F | Szoboszlai10 | 1:20 |
good luck
I've been waiting for this competition for so many days!
Oh, it is my turn: 🥹
As a tester, the problemset is delicious and I hope you enjoy.
Also, ahmet23 orz!!!
Thief!!!!
ahmet23 orz!!!
ahmet23 orz!!!
How many problems are there in both divisions?
btw the duration of 2h is pretty nice :)
orz sir yash_daga
orz sir yash_daga
orz sir yash_daga
orz sir yash_daga Jai Maa Kaali
ISM Bhaukali!!!!
magga sir your dp is not cyan coloured, u are breaking the order
mexomerf orz
mexomerf orz
mexomerf orz
mexomerf orz
mangrove orz
sanjay orz
mexomerf orz
Where is the score distribution? Best of luck to all contestants!
Scoring distribution will be released strictly before Saturday, January 27, 2024 at 16:35UTC+2Can relate.
I Swear I think I solved it 30 seconds after contest ended, if it's correct i need 48 hours to rc this damage
Edit: it was correct, so sad
So why is the registration limit for Div.2 round changed to less than 1900?
It's always been that way in rounds with separated divisions. See for example round 908
tku, maybe I mistook the upper limit for 2100, just like the last round
The upper limit is 2100 in Div 2 (and Edu) rounds without a corresponding Div 1 round. The idea here is that Candidate Masters may find Div 2 A-C boring, so they may as well start from D2D = D1A (or D2C = D1A, depending on the number of shared problems)
got it! tku~
ok nice me also from jharkhand :) waiting eagerly
Jai shree ram
Guess Which problem will be Interactive for Div2
1.C 2.D 3.E 4.F
A
3
orz yash_daga sir!!!
orz stands for?
Opened CF after months just to upvote this, hail ISM!!!
All the three problem setters have solved most problems related to maths and greedy. So, I suspect Mathforces or Greedyforces incoming.
right before usaco :c unfortunate
Fortunately to you, Usaco's website is down rn.
its going to be my first contest written by indians and i am very excited for this.
I love the way he writes "You".
rp++
Claimer
There may be some pieces of paper harmed during my participation of this round :(
This is my first competition i have ever done, I'm not that good, but ill see what I can do lol
GLHF
This is my first contest after eight months away...felt so good back to this cf vibe again!
Seems like nothing changed lol. This 10 min delay feels like bringing me back to before
why delayed
One refresh costed me 10 mins of time
This is becoming a habit now.
Delayforces again...
Delayforces :(.
Waiting for love :(
Did anyone see the questions
contest not started there is delay
1 Refresh cost me 10 min.... :)
GoodBye 2023 is that u?
GLHF
why this website is being too heavy to reload in browsers??
As a Megaminion, I couldn't resist replying to Sparky.
You should have tried m1/m2/m3.
wow my CR friendss then
I could have finished my LoL ranked game, now I lost a star and 10 minutes waiting.
It was your choice to stop playing before you could check if the round is delayed. It's not like the delay was shown 1 minute after the round started.
I wasted hours on origami to do 1C.
Paperforces
Сейчас бы участвовать в раундах от Упирвицкого
What is wrong with question C
I dont get why my code is failing ahhhh damnn it !!!
WAForce
It took me 10 minutes to do Div2D while 75 minutes to do Div2C,i'm really bad at implementation.
hint?
Linearity of expectation of binomial distribution. Answer is: 1/nC2 * k * sum(f) + m * k * (k-1)/2 * (1/nC2)^2
Was I alone to do so? :D
As a Grandmaster...
I tried folding the paper without drawing any lines, but it ended up being not useful at all since I couldn't tell which creases were mountains / valleys ...
Wish I had a squared paper around me. The pattern was too obvious.
You can get a square paper from a rectangular paper. Just fold a vertex.
yeah, although at times the thickness of the paper from the resulting fold makes it harder to fold even more
Maybe I was unclear.
Was lazy segtree expected on E ? I got tle on pretest 32...243653603
I used ABI and got 823ms. I really hope authors have a good solution, and not this ugly implementation that almost everybody did
My code got ac after submitting in C++ 64 bits :/
I think they have an "easier" solution that is to store the sum between each pair of harbors and handle manually the harbors on the side but I think it's less convenient
I eventually used 2 lazy segment trees for E but still less than a second man (C++ 17 7.3.0)....
div1B is disgusting
disgusting == I couldn't solve it ?
no, disgusting == simple idea but solution very hard to implement correctly
no. idea is obvious, just implementation + data structures. nothing interesting.
Thanks for the round! Feedback on the problems:
A: Good problem, appropriate difficulty for its position.
B: Not my favorite problem (unless there's a better solution than just killing it with a segtree / a set?); all the ideas involved felt standard, but because DS was involved it still took a decent chunk of the round to implement. (Also, implementation would have been mildly less annoying if the array X was sorted; I also would have found it easier if the input was passed as (X, V) pairs and not as an array X followed by an array V.)
C: I strongly disliked this problem. It felt basically like a pattern guessing test--maybe some people had the visualization skills to solve the problem rigorously, but I basically guessed a pattern that seemed reasonable, checked that it works for small cases, and then got AC.
D: Realizing that the problem reduces to "find the number of sequences of A balanced bracket sequences with total length B" was pretty nice. The rest of the problem was damaged by the constraints in one of two ways. After thinking of smart ways to count these sequences since the mod suggested FFT was unintended, I ended up just throwing in the KACTL FFT with arbitrary modulus template, which got AC, though running somewhat close to TL (800ms, not slow enough that I was worried about FST but definitely slow enough to TLE FFT templates with bad constant factors).
I don't know whether this solution was intended or not. I suspect not because of the choice of mod, but if this was intended, then I strongly dislike the choice not to use 998244353 as the modulus, and I also don't like the TL (I would have set something like 3s if FFT/NTT was intended).
Assuming this solution was not intended, it's a tougher situation, especially if the intended solution takes O(n^2) memory or O(n^2 log n) time. If one of these is the case, I honestly might have just let FFT pass anyway (and set a more friendly modulus and TL) since I think it'd be really hard to cut FFT cleanly and the first observation is nice enough to justify the existence of the problem. If there was room, though, I would definitely have set n = 5000. As is, I think "FFT works, but you have to use a slightly unconventional template and it runs close to TL" is a very bad state for the problem.
E: Probably my favorite problem of the round (though I'm biased in favor of EV problems). Not hard enough for its position or point valuation imo.
F: Interesting problem, I had no nontrivial ideas. I think the story got in the way of the statement, and you could state the problem more formally in a shorter and more readable way. I think something to the effect of "there exists a hidden integer x from 1 to n, you can query ranges and judge will output 1 if x is in the range and 0 otherwise, judge is guaranteed not to tell the truth or lie three times in a row" would work, without all the flavor text about the students or explicitly enumerating the four cases.
Will You stream solutions? How did you do C?
I don't plan to do a stream. This solution seems likely to TLE, as with x = 1e8 and n = 1, your solution loops through 1e8 values per test case, which will TLE when t = 1000.
Bro Can you explain C
2C: We construct the shortest string T that is not a subsequence of S as follows. Iterate through the characters of S and maintain the list of characters we've seen so far. Once we've seen all k characters, add the last character we reached to T and reset the list of characters we've seen. Once we finish going through S, add any character we haven't seen yet to T. Any shorter string can be found in S (we can find the first character of such a string in S before the first character of T, the second character of the string before the second character of T, and so on); I'll leave it as a (simple) exercise to prove that T cannot be found in S.
If T has length at most n, add additional characters until it has length n and output it as our answer. Otherwise, no answer exists.
During contest I submitted this just as a pure guesswork, totally no clue why we should add last char from each T. Now after some thinking it's a becoming slightly more evident, but still very vague. Something like if it wasn't the last char that is missing, then it should've finished T earlier.
Thanks for the explanation. Very helpful.
I think D might just be https://en.wikipedia.org/wiki/Catalan%27s_triangle. I just checked some smaller cases and didn't prove though.
Hi, Thanks for the feedback!
Nice, figured there was likely something like that :) In this case, I would have just set n, m up to 1e6, which clearly passes your solution but fails FFT and other such nonsense.
Yeah, it was a trade-off we did to make the solution less guessable. I initially proposed it as div2D but the testers feedback made us feel that it's harder.
The model solution of Div. 1F does require some non-trivial ideas. I will release the detailed editorial shortly but till then, here is one of the ideas that you may have missed.
You do a ternary search but in cases where you eliminate the middle segment, you use 3 queries and in other cases, you use 4. Dividing the search space into equal segments won't work (almost works, just 4 queries more than the limit). The trick is to divide the search space into segments of size nearly $$$36\%$$$, $$$28\%$$$ and $$$36\%$$$ so that you eliminate more with more queries and less with less queries.
Thanks for the feedback. From next time, I will try to keep the statement concise.
Thanks for sharing! I'll give it a bit more thought :)
One way to improve the ternary search solution is to note that if all the remaining candidates correspond to the same type of last answer (all honest or all dishonest), then you can save a query in the future. So actually for two of the segments you can save an additional query:
This achieves $$$\approx \log_r N$$$ queries, where $$$r\approx 1.1471$$$ is the solution to $$$(r^{-2}+r^{-3}+r^{-4})/2=1$$$. For $$$N=10^5$$$ this performs $$$83$$$ queries in the worst case (whereas the problem statement allows up to $$$104$$$ queries).
243674865
To further improve $$$r$$$ you can split into more than three segments.
On Div2D I figured out the correct fraction quickly but wasted the second half of the contest on figuring out WHAT IS A FRACTION MODULO 1e9+7. Also on trying __int128 or Python, because the unreduced denominator can reach 10^20 and goes beyond the long long limit. Could you please tell if this is avoidable?
Store all numbers $$$p/q$$$ in the form $$$p \cdot q^{-1}$$$ mod 10^9 + 7. It can be shown that addition, subtraction, multiplication, and division (where $$$a / b$$$ is computed as $$$ab^{-1}$$$) all work normally under this representation of fractions. Since all numbers are less than 10^9 + 7, the arithmetic operations can be performed using long longs.
Thank you for the clarification!
I googled this explicit formula for the convolution of Catalan numbers: https://mirror.codeforces.com/blog/entry/87585
I have a solution for C, based on capes of paper, once you fold the paper once there are the same number of capes upward and downward(this mean that all steps before that increments both values equally) so you have V=M + 2*sqrt(2). So in every steps the number of capes get multiplied by two, while the perimiter of the square is multiplied by 1/sqrt(2) then you have a geometric progression.
Too curious to know where I failed on C. T_T
m v bhai, curious and angry at same time
abcccabab?how did you came across this test case ?
By solving Div2A
For d1C, was anyone able to reproduce N = 7 irl? The most I could get is N = 4.
You might find this interesting: https://www.wtamu.edu/~cbaird/sq/2012/12/07/what-stops-a-piece-of-paper-from-being-folded-more-than-seven-times/
Paper gets hard to fold very fast due to the thickness exponentially growing.
Was submitting C in last 30 seconds, but Checking if the site connection is secure take a minute
Is it the problem setter of d1B in a loss of loved ones that he doesn't even guarantee $$$x_i$$$ is in an ascending order but doesn't even show it in the sample either?
btw, i don't understand what the data range is for for d1D.
How the hell to mod a rational number? I've managed to get a working solution for d, getting nominator and denominator, but i still don't have an idea how to convert them into valid answer...
check this
Damn, I shoud've learn this earlier... Thanks.
took me 20min to find the solution exactly there. For those still confused:
For me it took 20 minutes just to read the problem statement.
when p is a prime number, inv(a) can be calculated by a^(p — 2) mod p. (^ means power, not bitwise xor)
Link
hello
I find it hard to call problem nice when 60% of input is not even used.
I suppose writers originally had this as a much harder problem, then realize they need something for d2d, so they just go fkk it and repurpose it without removing the now reduntant part
If you consider the problem without the useless information it's not bad.
Agree, overall it's a nice intro to modular arithmetic
Can you please show me your code?
mathforces...
Anyone thought the position of harbour in div1B/div2E is sorted and keep getting WA at pretest 5?
couldn't solve Div2C(Div1A) in 100 minutes
I'm such a brainlet
Too much implementation for a div1 B ...
My rating gonna drop due to C. Fuck C
C anyone?
I think the point was to check for all intervals of length n if every one of the k letters are in it, if not then the answer is no. Again I'm not sure but if that premise is right you can easily think of a way to construct a string that is not possible.
1 3 3 11 aabbccabac
test case where you can fail.
Can you tell where does this code fail??
1 3 3 11
aabbcccabba
Straight DP:
Find first position of all k letters. It would base for len = 1.
Then for each
i = 2..nyou must have all k letters after all k letters positions fori - 1. If you keep it properly with reverse link, then construct answer should be easy.WTF I didn't submit 1D just because of this 'Just a moment' thing!!!
How can I get rid of it?
Task C is a very funny task. 10 sheets were damaged
I tried to solve problem B using segment tree. But I couldn't do it in integers, because I was required to combine several multiplications; and I couldn't also pass it using floats. How to pass segment tree?
I used Segment Tree and I passed. You store the answer of each position, and operation 1 is range equal to zero and range add an Arithmetic sequence.
My code
Ough, I did other quieries. When I'm adding a harbour $$$p$$$, there are closest to the left harbour $$$l$$$, and closest to the right $$$r$$$. Then I add to segment $$$[x_{l+1}, x_{p-1}]$$$ value $$$-(x_{r}-x_{p})*v_{l}$$$ and multiply to segment $$$[x_{p+1}, x_{r-1}]$$$ value $$$\frac{v_{p}}{v_{l}}$$$
I used lazy segment tree, but instead of multiplying when pushing y just maintained a vector of push's, bit it gave WA on test 8 :(
how D?
I felt statement of Div2D to be ambiguous and misunderstood several times. I initially thought once a pair is picked, then its value keep on increasing by one for every next excursion irrespective of what pair is chosen next.
Exactly I wasted a lot of time figuring out the logic for the misunderstood problem, they could have atleast explained a normal test case.
I somehow liked Div1C and Div1E, disliked Div1B, but anyway: Please polish the problem statement before the round (Div1B: "next harbour" concept is strange, Div1D&Div1E: two variables are interchanged, etc.) and please check it carefully for the clarification (I got two wrong responses in this round...).
Sorry about that, will take extra care in future.
Maybe consider sacrificing some pieces of paper in favor of making round even more ideal? :-)
I solved 3 problems, I am enjoyed this contest. Thank You
why CF doesn't let us submit code to check after contest ends :( Just missed submitting E by few seconds and now waiting to see if my solution is correct. Pretty frustrating to wait more.
It's because of system testing
They aren't even started yet... :(
I had fun in this contest. The D reminded me of JEE days. Thank you for fun contest.
what is wrong in my solution for question C. My Submission
what I was doing to divide string s into a complete chunk of k alphabets and if someone is missing in last chunk I take this character to form a valid subsequence not present in s.
counter_eg: 2 3 6 aabcbc
Why is it counter to the described idea?
2 chunks: aabc bc
ais missing in last one, socais final answer.I submitted exactly the same idea and it passed pre-tests.
consider 3 chunks and according to your approach, it will give NO, and output "aa" but "aa" is present in the string
I've posted the link to my submission, hack it if you are sure about your counter. To me it seems you misunderstood the proposed idea
Cloudflare is horrible
div2B O(n^0.5) with n = 1e8 timed out in python :(
What is "orz" btw?, I saw some people saying that?
this
Waiting for tutorial :)
How to know when it will be released?
The test cases are very weak for Problem Div2 B. some solution of complexity 1e10 also passed
yes my solution passed with the same problem I'm sure it will TLE now I should have iterated till sqrt(x)
Lol, spent last 33 minutes of the round debugging Div.1B, only to understand after the round that coordinates are not guaranteed to be sorted.
In my opinion, such problems problems should contain coordinates already in adequate order.
Div.1B/Div2.D should check participant's ability to invent and implement solution, not ability to carefully read problem statement...
Otherwise, problem is quite nice
wtf i spent 90 mins on B and still didn't figure this out :ded:
Happened to me as well. Noticed after the contest (;-;) hurts
speed forces yet bricked
I might be risking losing all my testing privileges here, but I would like to point out that div1A (or div2C), as well as div2A, were pointed out by me during testing to be very close to a certain CSES problem. According to the judgment of the coordinator, "D2A can be not really new," so I kind of assumed they'd be removing the div2C (it was A2 earlier) but not the div2A (which was A1).
My question is — is this expected by contestants? My perception is that it is not, and I feel there should definitely be some more originality in problems that are supposed to be around D2C in difficulty (D2A being unoriginal is probably arguable, so I won't comment on that).
This problemsetting trick is also well known in Romania.
I don't think they are very close
Meh, I think it's different enough.
It took me changing only a couple of lines in my submission to the CSES problem, so it was pretty similar for me.
A: It is easy to find out, that size of our answer is $$$nk$$$ (at least because it must contain all $$$aa...aa$$$, $$$bb...bb$$$, etc). So, we can just break our answer into $$$n$$$ blocks of length $$$k$$$. Each block will contain all first $$$k$$$ letters of the alphabet. So, our answer is $$$"abc...$$$($$$k$$$-th letter) $$$"$$$ repeated $$$n$$$ times. $$$O(nk)$$$ per test.
B: Basically, we need to find such array $$$a$$$, that $$$a_1 + a_2 + ... + a_n = x$$$ and $$$gcd(a_1, a_2, ..., a_n)$$$ is maximum ($$$a_i \gt 0$$$). If $$$gcd(a_1, a_2, ..., a_n)$$$ is equal to some $$$k$$$, that means, that each $$$a_i$$$ can be represented as $$$k * \frac{a_i}{k}$$$, so our sum will be $$$k * (\frac{a_1}{k} + \frac{a_2}{k} + ... + \frac{a_n}{k}) = x$$$. From here we can see, that $$$k$$$ will be divisor of $$$x$$$, so we can iterate over all divisor of $$$x$$$ (let it be $$$d$$$) and check if $$$\frac{x}{d} \ge n$$$, as we want to make each $$$a_i \gt 0$$$. $$$O(\sqrt{x})$$$ per test.
C: We can do a greedy approach to find such string, that doesn't occur as a subsequence. The algorithm is basically the same as when we solve "Does string $$$t$$$ occurs in $$$s$$$ as subsequence?", but we want to shift our pointer as further as possible. So, we will pick the furthest first occurrence of some letter starting from our current position, after that we will shift our position to the right of that picked one and remember letter on chosen position. If we didn't lack any letter during $$$k$$$ iterations answer is $$$YES$$$, otherwise we can construct answer as follows: we write remembered letters one by one, after that we add letter, that we lack and until size of our answer $$$ \lt k$$$ we will add letter $$$a$$$ to the end of it. $$$O(nk)$$$ per test.
P.S: Funny, that C is a checker for A.
After solving D2A D2B I thought D2D would be easy and got the right answer within O(1), but THIS IS THE FIRST TIME I come across fraction representation like "Calculate p⋅q^−1 mod(10^9+7)" and didn't know how. Also the unreduced denominator can be n^4 which is 10^20 and goes beyond the long long limit. That left me stuck trying python or __int128
:(
Problem E basically have the same solution with this atcoder problem ARC114E.
Atcoder
Though it seems this did not affect the standings, as I did not found many others solving this lightning fast. (Not that this particularly affected me as I solved this problem pretty quickly when practicing)
Hi, I thought of the problem after solving the atcoder one and mentioned in the round proposal that my problem is inspired from this one.
According to me, my solution is very different from the solution of that problem. Only the concept of linearity of expectation is common.
To me, there are two key components of the solutions, aside from linearity of expectation.
Exchange the situation into a random permutation of the (n-1) + (m-1) lines
The required probability is exactly when a certain line must occurred before k other lines, which gives a probability of 1/(k+1)
With these two key concepts the rest of solution should be basic calculations.
But by far, the first part is hardest one and take the longest to come up with. Unless the intended solution is very far from what I described then I can see your reasonings.
Yeah my solution is slightly ugly and doesn't use the first concept mentioned by you.
Basic Concept Needed: Expected number of cuts for any case is the same as the sum of probabilities of being cut for every line.
First we handle the cases where we complete our objective with the help of only one type of cut(horizontal or vertical).
1)i)Only Vertical Cuts:
Let the largest integer y for which (n*y)<k be reqv. The probability of achieving the goal using only vertical cuts is (reqv/(reqv+n-1)) since one of the reqv lines needs to be cut before all the horizontal lines. Now we will multiply this with the sum of conditional probabilities for each of the vertical line. Sum of conditional probabilities of being cut for all lines from 1 to reqv is exactly 1, since for area to be smaller than k one of them needs to be cut and as soon as one is cut the area becomes less than k so no further cuts are required. Now for the lines from reqv+1 to m-1 their conditional probabilities will form the following harmonic progression:
1/(n+reqv) + 1/(n+reqv+1) + .... + 1/(n+m-2)
This is due to the fact that for a line to be cut it needs to come before all horizontal lines and all vertical lines smaller than it.
1)ii)Case with only horizontal cuts can be handled similarly.
2)i)Case when the overall last cut is a horizontal one and there is at least one vertical cut:
For this we iterate over the last cut among all the vertical cuts. Let the last vertical cut be x. We now find the largest y such that (y*x)<k. Let this value be reqh. The objective can be achieved using this case if the vertical line x comes before all the horizontal lines from 1 to reqh and all the vertical lines from 1 to x-1, and after that any one of the horizontal line from 1 to reqh comes before all the vertical lines from 1 to x-1. The probability of this happening is (1/(x+reqh))*(reqh/(reqh+x-1)).
Now we just add the the conditional probabilities of being cut for every line and multiply this with the above probability to find the contribution of this case to the final answer
2)i)a)Firstly the conditional probability of the vertical line x being cut is 1. 2)i)b)The sum of conditional probabilities for horizontal lines 1 to reqh is also 1.
The order of the first x vertical cuts and the first reqh horizontal cuts for the given case would look like:
x_v, y1_h, ((x-1) vertical lines and (reqh-1) horizontal lines in any relative ordering) [Total x+reqh elements in the sequence] x_v denotes the x-th vertical cut y1_h denotes the horizontal cut which comes first among all the first reqh horizontal cuts.
2)i)c)Vertical cuts from x+1 to m-1: For the (x+1)-th cut we can look at this like it needs to come before the x-th vertical cut (or it has one gap in the sequence to choose from a total of (x+reqh+1) gaps) So the probability is 1/(x+reqh+1) For the (x+2)-th cut we can first place the (x+2)-th cut with probability 1/(x+reqh+1) now we need to place the (x+1)-th cut after of this which will happen with the probability of (x+reqh+1)/(x+reqh+2) So the overall probability is the product ie. 1/(x+reqh+2) Similarly, the probability for (x+i)-th cut is 1/(x+reqh+i)
The sum of this HP can be computed in O(1) using pre computation.
2)i)d)Horizontal cuts from reqh+1 to n-1 (Trickiest Case imo) Let us see the case for the (reqh+1)-th cut -> It has 2 optimal gaps (before x_v and the gap between x_v and y1_h) so the probability is 2/(x+reqh+1)
Now for finding the probability for (reqh+i)-th cut we first place this cut into one of the 2 gaps and handle both cases separately.
Gap before x_v: this case is similar to 2)i)c) and the answer is just 1/(x+reqh+i)
Gap between x_v and y1_h Here we again have to ensure that all lines from reqh+1 to reqh+i-1 come after reqh+i so we multiply (reqh+x)/(reqh+x+2) * (reqs+x+1)/(reqh+x+3).... since after we place the (reqh+i)-th cut we have (reqh+x) good gaps among a total of (reqh+x+2) and so on for all the other lines we place (Their relative ordering does not matter since we are only concerned with (reqh+i)-th cut) The final term for (reqh+i)-th cut comes out to be: ((x+reqh)/((x+reqh+i)*(x+reqh+i-1)) This forms a quadratic HP the sum of which can be computed in O(1) using precomputation.
2)ii)Case when the overall last cut is a vertical one and there is at least one horizontal cut:
This case can be handled in a similar way as the previous case.
O((n+m)log(n+m)) Code: https://ideone.com/V2vGBp
div2D was one of the easiest problems I've aeen in a while, and yet i spent four tries, first because i summed without modulo, then because i divided by 2 and not multiplied by 2^-1. i should really get a modulo template
what was your approach for div2 D?
well the base expected value is just sum(f_i)/(n choose 2), and then there is exactly m/(n choose 2) probability to add 1, so in expectation it adds 1 * m/(n choose 2), and that's true for all the stages, and it carries over to the rest. so it's ((k-1) + (k-2) + ... + 1) times that m/(n choose 2).
Here is my advice about the problems (Div 2):
Amazing A problem, clear statement, there is a little idea, it's not A + B, bonus point for the link with problem C! I feel like div2 AB this days are really good
Pretty good div2 B too, I feel like it's perhaps a bit too easy ? But it's cool anyway.
The implementation was a bit tedious but overall it's a great problem, perfect for it's position (and I liked the fact that it was "implem checker for A")
I found the implementation a bit tiring (but I think that's my skill issue for not having any template for modints). Overall the problem would be great as an educative EV problem but I think it is too easy for a div2 D (and what makes it ""difficult"" is mostly that it is probabilities).
I strongly disliked this problem. It feels like a very standard ds bash problem. It would be a nice educative problem but I don't think it was good to put it in this problem set
By the way, I feel like the time limit very tight ? I got tle on pretest 32 243653603 with something that should have passed I think ?
Anyway, kudos to the authors of the round, it was still an overall good contest
Implementation of C felt easy to me, you can check my solution, My logic was to check if i can make n or more continuous substrings of the strings or not with every substring satisfying the condition that it contains all the characters from 'a' to 'a'+ k at least once
oh ok that's equivalent to my construction 243596134 except it's less tedious to implement, nice
When I submit solutions after the contest is over ?
after system testing is finished
Why is this giving memory limit exceeded for Div2,C? 243648118
I even tried using map instead of set, yet ntg changed. 243653296
For some reason size of your answer is $$$ \gt n$$$ before last while loop, so it becomes infinite.
Right. The variable
cntwhen goes beyondn, it goes in infinite loop.Thanks for the help.
FST on test 24 of B... Please, let me get a huge negative delta then I can farm the next div 3
approach for Div2D ??
FST Div2B, fail to solve C, endup solve A only
going to buy rope today
I don't have the money to buy it. Would you be so kind to get one for me as well?
for DIV2 C
What should be answer for this?
2 2 4 cbbc
According to me it should be NO. I thought problem states first k lowercase characters.
The problem statement says that the string s will contain only the first k characters, so your test case is invalid anyways.
Oh yeah thanx.
failing System Tests has got to be one of the worst feelings
I got used to it
My submission for div.2b got tle on tc 23. Although I had this feeling that it might get tle still I overlooked as it passed the Pretests.
Atleast they could've provided strong pretests :(
me too, damn it hurts
same
for small n it is much higher than 10^4
12 fricking FST's in B in my room which were so easliy hackable 😢
Lesson learnt
why test cases are not visible now???
My submission 243558996 passed pretests but wasn't evaluated in the final submission. Coordinators, please investigate.
Upon resubmitting the same code in the practice section 243664978, it successfully passed the evaluation.
Rare event. Reevaluation needed.
Test cases of div-2 B :(
Easy and elegant solution for E using only fenwick tree and std::set: https://mirror.codeforces.com/contest/1925/submission/243668425
Can anyone tell what is wrong in my submission? https://mirror.codeforces.com/contest/1925/submission/243671686
1 3 3 13 aaabbbcccaabb should give No(ex bac)
Why this solution doesn't work for Div2C, I've tried to find testcases where it might fail but cant seem to do so. (I know it might TLE I just wanna get the logic right).
https://mirror.codeforces.com/contest/1925/submission/243668507
consider the following test case:
1
3 3 13
aaabbbcccaabb
Your Output: YesBut clearly "bac" is not a subsequence of sI feel soo good
for the first time i solved a question
and this is where my Journey started...
Lets goo :>
As a div.2 participant, I find it very strange, that problem creators decided to leave the link to the wiki page of modular multiplicative inverse in statement of 1925F - Fractal Origami but not for 1925D - Good Trip . I didn't manage to figure out how to restore the answer from rational number, even though i had completely correct solution.
What would be the rating of C?
Div1D one-liner?
Use the usual interpretation of sequences as walks of $$$(+1, +1)$$$ and $$$(+1, -1)$$$. WLOG $$$n \geq m$$$, then the longest subsequence has length $$$(\min y) + m$$$ (minimum y-value plus down arrows count). Using the well-known catalan reflection argument gives a final answer of $$$\binom{n+m}{k} - \binom{n+m}{k-1}$$$, with an edge case at $$$k \gt \min(m,n)$$$.
243676528
Can C be done with DP?
yes :
https://www.geeksforgeeks.org/shortest-uncommon-subsequence/
I guess people don't like to see what I wrote, and unfortunately I can't delete the comment (no option to do so), Treat this as a DELETED COMMENT.
Finally, I could make use of my squared office papers
Tilting round :/
A was a good & funny problem. I only got the greedy after thinking through the naive DP over and over and realizing that it can be transformed to greedy.
B, I knew that the problem was basically just this, but it seemed like overkill. Plus, I hadn't actually solved it so I didn't feel like copying somebody else's code. So I over-engineered a terrible set + segtree solution with 5 WA's under my belt B)
C, I literally got the main observation within minutes, and worked out the formula shortly thereafter. Spent 30-40 minutes not being able to implement goddamn complex number arithmetic.
I asked ChatGPT this prompt:
and it AC'd first try.
For comparison, this was my upsolve: 243684462
and this was ChatGPT's library: 243685245
Lesson of the day? I don't know, massive skill issue :(
Hi, my problem B during the System test doesn't test again for the main test. After I woke up this morning, I saw my score had been minus but problem B wasn't in the main test. I tried to submit again with that same code and the code seems to be AC (I didn't get hacked or sth). MikeMirzayanov yash_daga Can you help me please?
WHERE IS MY B? ⚈₃⚈
It's looks like your code gets TLE in the main test
My mistake
B was the only problem hacked by anyone ...
The pretest of B is weak resulting in many people got hacked and fst.
243558075 I solved question A, the pretest passed, and didn't get hacked, but the final settlement showed that only BCD was done, A didn't show "Accept",. I then handed over the same code, which was Accept, why?
MikeMirzayanov In the last DIV2 921 my submission for C shows pretests passed , but it neither shows AC nor FST on the final standings . Can you please check once . I solved 3 problems but it shows only 2 problem solved . https://mirror.codeforces.com/contest/1925/submission/243641450
I've got abrupt rating changes in this round 912 div2. kindly see to this image
yash_daga please solve this issue
I do have same issue, unexpected rating change for my result. Hope this will be fixed.
Simple solution for DIV 2D
Anyone using sqrt decomposition to solve div2 problem E? I divide the sequence into $$$\lceil\sqrt n\rceil$$$ blocks, with each block at most $$$\lceil\sqrt n\rceil$$$ length (the last block is cutoff to a lower size). Then for each insertion of harbour, I find its left harbour $$$l$$$ and right harbour $$$r$$$ and then update the blocks in $$$[l,r]$$$; for each query $$$[l,r]$$$, I also retrieve the information in blocks in $$$[l,r]$$$. I think it should cost $$$O(q\sqrt n)$$$ and should get passed. However I got time limit exceeded: https://mirror.codeforces.com/contest/1925/submission/243770890. Could anyone help?
yash_daga, JaySharma1048576 sir orzzz
The fact that X was not sorted in B is pure evil. Why would anyone create and approve such a version?
can someone tell me in which test case my code is failing?
void solve(){
int n,k,m; cin>>n>>k>>m; string s; cin>>s; int a[k]={0}; for(int i=0;i<m;i++){ a[s[i]-'a']++; } for(int i=0;i<k;i++){ if(a[i]<n){ cout<<"NO"<<endl; for(int j=0;j<n;j++){ cout<<char('a'+i); } cout<<endl; return; } } vector<int>b(k,0); for(int i=0;i<m;i++){ int c=s[i]-'a'; b[c]++; a[c]--; for(int j=0;j<k;j++){ if(a[j]<(n-b[c])){ // cout<<j<<" "<<c<<endl; cout<<"NO"<<endl; for(int idx=0;idx<b[c];idx++){ cout<<char('a'+c); } for(int idx=0;idx<n-b[c];idx++){ cout<<char('a'+j); } cout<<endl; return; } } } cout<<"YES"<<endl;I don't really get why I was being downvoted.
because of the way you wrote the code in your comment, the first few lines have a very large font size , and the rest are very small with no ne lines for each statement , it's not readable and it takes up a lot of space.it's a common practice to put your code in a spoiler
And also you can send your code as a link
Thx buddy for pointing it out.
maybe sample of div1F should be t=2 yash_daga
Yes, it was a typo. Thanks for pointing out.
Hey folks, here is the solution video to the problems A to E (Div 2) of the above contest for those of you who'd like to upsolve them or reflect upon alternative techniques to solution etc. The video stresses upon the intuitions to solve the problems mostly from scratch. I believe this will benefit budding CPers who're trying to level up, and it shall inspire them to do better in upcoming contests. I'll try to consistently post videos on some of the upcoming contests and would be excited to see the community grow together! See you all! Feel free to write to me about any doubts/issues/feedback. Thanks!