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, MisterReaper, 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
you too
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 :)
Eagerly waiting for this contest sir!
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
mexomerf orz
Edit : why so many down votes?
Too delighted and proud sir.
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.
Meanwhile ,the expert:
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
GOOD LUCK!!!
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~
m
ok nice me also from jharkhand :) waiting eagerly
Jai shree ram
Thank you guys for the info, I will try in my home town.
Guess Which problem will be Interactive for Div2
1.C 2.D 3.E 4.F
A
3
orz yash_daga sir!!!
Hail ISM !!!
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 am getting back with coding after a few years with the contest, with a determination to stick to it until I improve this time
All the best
I Hope to rank up to pupil :DD
Good luck!
I love the way he writes "You".
rp++
ORZ%%%
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!
what were you doing in these eight months ?
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
Delayforces
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
seems like it's going to be a hard contest :(
why this website is being too heavy to reload in browsers??
Too many active users
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 only good thing about D2F/D1C is the fact that you can play with origami paper while solving it :D (still, definitely an annoying problem lol)
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
Div2D was so nice.
For every excursion, our answer increases by (total sum of friendship values)/(# of pairs) on average, and the total sum of friendship values increases by (# of non-zero friendship values)/(# of pairs) on average.
This hand-wavy "average" logic works because of the linearity of expectation.
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
why does binary search not work in B?
it'll work, first stores all the divisors in array , then sort it , now find out that what can be the average difficulty for each sub problem , now we know that our max difficulty won't exceed this average, so use lower_bound on the array of divisors
C was definitely one of the problems ever.
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.
I thought of that too but there's some flaw in the logic. Take for instance the case when the string's length is greater than n * k. This gives you some 'buffer' characters to play around with, which means that the interval of length n may not necessarily hold all the characters.
Yeah, you're right
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.https://mirror.codeforces.com/blog/entry/125112?#comment-1110782
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?
That C..
why am i so dumb
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 was so close to solving Div2C or at least I hope I was T.T
Edit: nope, not even close
too much server problem, but overall good contest and good questions.
Hope I will become green this contest.
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
i was so exited to participate since this is my first contest lmao , until i spent all the time in the first problem and couldnt solve it lmao , any tips so i can improve ??
Can we use binary search to solve Div2 B ? i was trying it at first but i didn't understood where its failing here is my submission 243579415, then i just used linear approach.
I don't think binary search could solve Div2B. Because if K is the answer so every number that smaller than K should be all satisfied. However, if x = 10, n = 2 then all subsets we have are 1-9, 2-8, 3-7, 4-6, 5-5 => gcd of them are 1,2,1,2,5 respectively. So there is no way to split 10 into 2 numbers that have gcd equal to 3 or 4.
Thanks man ,I'm an idiot who forgot how binary search works
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
You can check the above submission, you will get your answer.
Cloudflare for the 87th time today, please I'm not a bot for fuck sake
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
Weak pretests on B, need n = 1 case
C is the opposite, yet another brutal pretest
speed forces yet bricked
DM, how to solve C of div 2?
u just need to count the number of times all the alpha occurs
sry for the misconception i realised the error but how can i del this comment
Welp... i did 1 problem at least. I didnt know that the contest was delayed by 10 mins, so I was confused and thought it was starting on the end time. I ended up starting like 1 hour into the contest, and did problem A at least. A lot learned! Hoping to be at the next competition as well
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
I think this is a good thing for newbies like me
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.
Really good contest! Very nice and fun to solve these problems. Thanks for the round JaySharma1048576 mexomerf yash_daga and all testers!
Solution for Div2C (if anyone needs):
-> After solving Div2A, you can see that to get all possible strings of length n using first k characters, the string s should have n groups of the first k characters.
Eg: if n = 5, k = 3 (a, b, c) then s = "abc abc abc abc abc"
-> so in the given string s, traverse from left to right and form such groups of first k characters and find how many such groups you can make (call it cnt)
-> if cnt >= n, ans is YES
-> else, take the last character of each group and combine it with the missing character of the missing group, this newly formed string will definitely not be a subsequence of s, because theres only one such character in each group and we combine it with the missing character.
Eg: if s = "aabbccabab":
the groups are "abc" "cab" "ab"
so taking last character of every group and missing character, we get "cbc" which is the answer
Submission for reference
Hey can you explain the intuition more clearly about this line "because theres only one such character in each group and we combine it with the missing character."
what I can get from solution is that since we are making blocks as soon as we get first entry of last remaining element that element will always be single. So it is deemed to be remain unique in pattern as opposed to elements who are repeating more than one time.
also I am thinking that any single element will also be sufficient for concatenating answer but for sake of simplicity we taking last element which automatically will be single because after that we are terminating that block.
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 > 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 > 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 $$$< 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 $$$> 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
I wanna Duhhhhhh!!!!
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 me one as well dude, tickbird
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
C ka logic btao bkl iski
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
WA in test case 3566 in C,any?
consider the following test case:
1
3 3 13
aaabbbcccaabb
Your Output: YesBut clearly "bac" is not a subsequence of s12 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.
Thank you for the contest!
What is the expected rating of C?
so many Div2B solutions failed on system tests
fortunately, my solution did not
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 sThanks for pointing it out, I will try to solve it now.
can someone please tell about the rating system in contest?? why is it showing increasing alot then expected for ones who locked their problem how does this automatic lock hacks others problem and increase up thier ratings?? how?
someone please check my submissions for div2 C , it is showing wrong answer for testcase 1 , and showing accepted test case 1 in next submission even when the output is coming same . Plus the output which is coming on submitting is different from custom invocation .
what is this happening ?
ignore i have got the mistake
I feel soo good
for the first time i solved a question
and this is where my Journey started...
Lets goo :>
Finally became pupil
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?
My approach for problem C was initially this.
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 > \min(m,n)$$$.
243676528
Can C be done with DP?
yes :
https://www.geeksforgeeks.org/shortest-uncommon-subsequence/
Thanks
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 :(
Any hint or counter test for my div2C??
Here is the submission 243684563
The idea was to split the string in groups where each group has at least one of each first k letters. For example "aabbccbbaaaacb" will split into aabbc-cbba-aaacb. If there is more than or equal to n groups, then ans is yes. Otherwise, no. So in case there are less than n groups, the string could be formed using the last char of each group, and complete the string with the first char wich is not present in the last group. Example: abc-cba-ab => would be c,a,[c]. the last one is c because it is not present in the last group.
Just because a stupid error like:
I needed to use a constant var for ans.size() :'/
Can you look into this submission? 244387004.
I too had the same exact logic. In the above submission I used a set to keep track of found alphabets.
Later, I did it with a bool array and a variable for size. 244388047
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
PROBLEM B-> DIV 2 void solve() { int a, b; cin >> a >> b; int temp = a / b; int num1 = temp — 1; int num2 = temp + 1; if (a % temp == 0) { cout << temp << endl; } else if (a % num1 == 0) { cout << num1 << endl; } else if (a % num2 == 0) { cout << num2 << endl; } else { cout << 1 << endl; } } why this sol is getting WA on testcase 2 on 94th
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
Good contest!
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
c was very enjoyable
The Contest was really enjoyable
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.
Will 1 1 1 b be a valid testcase for Div.2 C?
Disclaimer
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!
For div2C/div1A, Can anyone please tell why am I getting memory limit exceeded on this submission https://mirror.codeforces.com/contest/1924/submission/244323304