Codeforces Round 921 (Div. 1, Div. 2) (Partial) Editorial

I hope you enjoyed the round. Here is the editorial for some of the problems. The hints and tutorial for the rest of the problems will be added soon. Do provide your feedback on each problem so that we can improve upon them the next time.

2A. We Got Everything Covered!

Author: JaySharma1048576

2B. A Balanced Problemset?

Author: JaySharma1048576

2C/1A. Did We Get Everything Covered?

Author: JaySharma1048576

2D. Good Trip

Author: yash_daga

2E/1B. Space Harbour

Author: yash_daga

2F/1C. Fractal Origami

Author: mexomerf

1D. Balanced Subsequences

Author: yash_daga

1E. Paper Cutting Again

Author: yash_daga

1F. Anti-Proxy Attendance

Author: JaySharma1048576

• 41 hour(s) ago, # ^ | I don't really get why I was being downvoted initially (and even now) I am genuinely interested in knowing that, if someone can politely point out the reason. It will be much appreciated. (will take care about it next time I say something, feel free to see previous revisions).

  • 37 hours ago, # ^ | what was your comment?

    • 37 hours ago, # ^ | You can press the <-Rev. 6 button to see the previous revisions (i.e. what my comment was). Thank you for your time.

      • 36 hours ago, # ^ | now i wonder too what made you have so many downvotes

• 41 hour(s) ago, # ^ | It seems interesting, it's quite easy when find this greedy way in A but harder in C.

• 2 days ago, # ^ | The moment, when the greats despaired

• 36 hours ago, # ^ | I can only provide their codes here because I don't fully understand them (My rating doesn’t allow me to understand it). dario2994's solution (70 queries) kevinsogo's solution (55 queries)

  • 36 hours ago, # ^ | dario2994's solution is roughly what I expected (split into up to 8 equal segments, then reduce to two segments). Not sure what kevinsogo is doing for though — would appreciate a proof regarding the total number of queries if there is one. It's also not clear to me why the find function never asserts false.

    • 20 hours ago, # ^ | ← Rev. 4 →   +16 It seems you have pinpointed the most crucial part of my code :) When I derived this algorithm, I had no proof that find would work, just empirical evidence that I tried it for many random tests and couldn't find a breaking case. (And I guess I proved it for small just by checking.) But now after you asked, I spent some more effort proving it, and I think I have come up with something that might work. Roughly, it seems to me that we need to show some sort of variation of the Borsuk-Ulam theorem. Let's make the array circular, and consider its half-open subarrays , with appropriate wraparounds, i.e., is to be understood mod , and . Note that the complement of is . Then I defined a cost function from subarrays to 2D vectors satisfying the following: near-continuity property: whenever . (The in the former uses Manhattan distance.) antipodal property: . boundary condition: for all and . And the goal is to show that has a near-zero, i.e., some such that . (In my code, you can see the definition of in the comments: its two coordinates are scost and bcost.) We can think about a continuous version of this, where the indices and are now allowed to have fractional values, and extend into a continuous function in a somehow "tame" way. The claim is that this extended has a zero. If this is true, then I'd think that the original, discrete version of must also have a near-zero nearby (...maybe, haha; alternatively, maybe the proof of the continuous version can be adapted to the discrete one) which is what we want. Thus, we seem to need to know the topology of "subarrays of a circular array". Well, I think it's a sphere! Map the subarray to the point on the sphere with longitude and latitude . Then we can check that: This respects the fact that only makes sense mod (because replacing with doesn't change things); and map to antipodes; empty subarrays map to the north pole, so the boundary conditions are satisfied. (Their complements map to the south pole.) So Borsuk-Ulam applies, and (the extended) has a zero.

    • 20 hours ago, # ^ | ← Rev. 2 →   +16 Now, for a proof of the number of queries, we have two quantities at every step: The number of indices such that . Let's call this . The number of indices such that . Let's call this . Here, we only consider "alive" indices, i.e., those that may still contain the target value. Initially, and are . Then, assuming that we are always able to perform a query on a subarray such that: it kills roughly half the indices; it splits the indices roughly equally into the two kinds; then we have the recurrences and . (This is what the find function accomplishes; it looks for a subarray that will do this.) This then means that the sum decays with a factor of roughly at each step.

• 2 days ago, # ^ | Expectation is one of the core application of probability.

• 2 days ago, # ^ | You could sum up all the values time their probabilities respectively to get the expectation value.

• 42 hours ago, # ^ | ← Rev. 2 →   0 They asked us to sum up the pairs involved in the excursion. The question is so poorly worded that I had the same doubt during the contest.

• 38 hours ago, # ^ | I don't get it either. I get 7/9 but how does it relate to 777777784?

  • 38 hours ago, # ^ | They want you to kind of find exact values of p and q in p/q. There might be a possibility that you simulate the process and find average according to it or something (then you get the approximate answer by remaining well within the constraints or something). They don't want that, they want you to use math to find the expected value and not implement the selection process in it's entirety.

    • 38 hours ago, # ^ | Yeah, so what should I output? It says calculate p/q mod (1e9+7) but p/q is a fraction, and according to my knowledge the modulo operation is only valid between two integer operands. Btw based username :)

      • 37 hours ago, # ^ | You are to output modulo of times Modular inverse of .

        • 36 hours ago, # ^ | Thanks, I'm new here. I thought -1 was an exponent.

          • 20 hours ago, # ^ | It kind of is, if p/q were an integer less than 1e9+7, It will be equivalent to p/q.

• 47 hours ago, # ^ | Much concise and clearer than the tutorial, thank you for your explanation!

• 39 hours ago, # ^ | Concise and efficient!

• 2 days ago, # ^ | It took me a while to see it too. But I guess if you have a,a,a,a,a...a,(x-(num)*a), we want the last term to be a multiple of a. Then you can kind of see that a has to be a factor of k

• 46 hours ago, # ^ | ← Rev. 5 →   +5 You can think like this: You want to split into so as to maximise subject to the constraints that and . Let , then . Hence must divide . So, you can basically iterate over all factors of in time complexity, and take if , as each , so . Where, is just the residual when is divided by . Here's my submission for reference :)

  • 18 hours ago, # ^ | what is k in your solution , k1+k2...kn , i didn't understand that

    • 17 hours ago, # ^ | Oops, I missed it in my explanation: So, if is of , that means (definition of a divisor). Also, since , this gives us the condition . I hope, it is clear now :) You can ask if you have any other doubts.

• 2 days ago, # ^ | Very intuitive explanation. I saw the question and thought there must be a numberphile videos on this.

• 2 days ago, # ^ | Yeah I did the same. I also wrote a struct to store which was very convenient and easy to debug. struct node{ int x,y; node(){x=y=0;} node(int xx){x=xx;y=0;} node(int xx,int yy){x=xx;y=yy;} node inv(){ node z; z.x=x; z.y=(mod-y)%mod; int a=x*x-2ll*y*y%mod; a=(a%mod+mod)%mod; a=poW(a); z.x=z.x*a%mod; z.y=z.y*a%mod; return z; } friend node operator +(node x,node y){ node z; z.x=(x.x+y.x)%mod; z.y=(x.y+y.y)%mod; return z; } friend node operator *(node x,node y){ node z; z.x=(x.x*y.x%mod+x.y*y.y*2ll%mod)%mod; z.y=(x.x*y.y+x.y*y.x)%mod; return z; } friend node operator /(node x,node y){ y=y.inv(); return x*y; } };

• 2 days ago, # ^ | is the largest prime number under under which is a quadratic non-residue.

  • 45 hours ago, # ^ | I might be missing something very simple, but why do we want 2 to not be a quadratic residue? Why would the existance of "sqrt 2 under modulo" be a bad thing?

    • 44 hours ago, # ^ | Answer is not defined if sqrt 2 exists (a + b root 2 can be written with other values of b)

      • 44 hours ago, # ^ | But the statement doesn't say "find , for which ", it says "find , for which ". The fractional value of is well defined regardless of the modulus used since it is defined by equality, not congruence under modulo. This means that the value of under modulo is well defined unless , where , and . If instead, your argument is that "sqrt 2 doesn't exist under modulo it is harder to misunderstand the problem", then I think I can agree with that. But I still wouldn't change the modulus to something non-standard for this reason. Or am I wrong?

        • 41 hour(s) ago, # ^ | You are correct, idk the reason either now

          • 37 hours ago, # ^ | ← Rev. 2 →   +11 Maybe because (the denominator) can be ?

        • 36 hours ago, # ^ | This means that the value of under modulo is well defined unless , where , and . So let's test this theory. If you take the math to its natural end you will find out that the value of such that is exactly, with no modulo reductions: Where and . Since is always either or it's easy to check that no big prime can divide both and , and thus no big prime can divide both the numerator and the denominator either. So we require to never be divisible by for our modulo of choice . Assuming is nonzero modulo this gives So there you have it, as long as $2$ is a quadratic non-residue modulo we are guaranteed to be able to compute the answer. Since is a quadratic residue for both standard choices and , this seems to me like a good enough reason to change the modulo. However, you might argue that even if is a quadratic residue, that doesn't mean that the answer is impossible to compute. After all, and are something specific and not whatever you want them to be. So let's go a bit further. I'll focus on the case where is even and therefore . Then And so we want To never happen. We know $8$ is a quadratic residue for the usual primes since is, so choosing for either modular square root of fails. But wait! is not equal to just any number, it must be equal to for some . So in fact we need Clearly this is much better, there's nooooo way a power of $2$ just happens to give one of these two random values modulo for both of our standard primes. Unfortunately it just so happens that for both and the order of modulo is , and so passes through every single quadratic residue modulo . But there's still some hope! There's no reason both values of have to be quadratic residues... Aaaand it's dead, for and we have that is a quadratic residue. But wait! Both of the choices actually turn out to give quadratic non-residues modulo ! Surely these silly authors should have just gone with that instead of their weird modulo... Nope, recall that is only one of the possibilities, we also need to discard . Doing similar math we find that the bad case here is Significantly less clean than the previous case, but equally solvable. We now need to check the square roots of $2$ modulo and see if the resulting expression is a quadratic residue. For this turns out to be a non-QR, and for ... wow! also a non-QR! Very unexpected! So in summary, while is a no-go, it turns out that the authors could have safely chosen and kept the answer computable. My question for you now is, if you were the author, would you rather go with the non-standard modulo that clearly works, or the standard modulo that basically only works because we won four coin flips in a row and could have easily sent contestants with more number theory experience on a wild goose chase like the one I just sent you on?

          • 35 hours ago, # ^ | My question for you now is, if you were the author, would you rather go with the non-standard modulo that clearly works, or the standard modulo that basically only works because we won four coin flips in a row and could have easily sent contestants with more number theory experience on a wild goose chase like the one I just sent you on? Now that I understand the reasoning behind it, I would definitely choose the non-standard modulo. Your comment seems a little passive aggressive, possibly because of my comments about "this is not a good enough reason to change the modulo", and I don't really like that. I wasn't trying to critisize the problemsetters' choices of modulo; I was just looking for a good explanation for that, and your comment managed to do that. Before your explanation, I didn't know why having 2 be a quadratic non-residue was desirable — now I know. Anyway, thanks for the explanation!

            • 35 hours ago, # ^ | Sorry if it came off that way, it's definitely a good and valid question and I was mostly trying to emphasize that one of the standard modulos working seems very unlikely at a glance.

• 2 days ago, # ^ | If you are just checking for n-1 occurences of each character ahead it might fail for abcaaabbbccc , n=4 , k=3 a,b,c, all have n-1 occurences ahead of them, but the string can't make all subsequences. I have not checked your code, but this might be the problem in your approach

• 2 days ago, # ^ | ← Rev. 3 →   +1 oh,Your approach is the same as mine during the contest, both wanting to use this method to check if there are n abcs This kind of arrangement string. However, this idea is problematic For example, aaabbbcccaaabbb You will find that there is no substring like CBA, but the result obtained using the above approach will be YES. So the correct way should be to use greed to check.like this

• 2 days ago, # ^ | I think I might used a similar approach and just came to know what was the problem with this approach. if I understand correctly you are checking that if the freq of the character you have right now is let's say x then every character must be present n-x times in its suffix, but the problem is that we are not considering the order of the characters in this approach, that's why this will give the wrong answer.

• 2 days ago, # ^ | I was getting wrong answer for test case 6. I think the limits just go boom. Can someone check the code and point where is the thing going wrong?

  • 3 hours ago, # ^ | Do all the math in this problem with long long instead of int. Otherwise you WILL have overflow in the multiplications.

    • 3 hours ago, # ^ | Ah i defined int as long long. I didn't take mod for f sum so it overflowed

• 2 days ago, # ^ | I also came up with same idea but got stuck at printing the non occuring subsequence . But finally again tried an hour ago and solved it.

• 46 hours ago, # ^ | ← Rev. 2 →   +15 Expectations can be tough to think about. Here is a mathematical proof for Div2D [Note that it requires basic understanding of probabilities and expectations]: Let pair 1 occur times, pair 2 occur times pair occur times in the excursions. Let be the total contribution of pair to the total friendship. Hence, if total friendship is subject to . Here, each is a random variable which takes value in the range . Clearly, using linearity of expectation [even though 's are contrained]. This is the power of linearity of expectation. What is ? If pair occurs times in the excursion. So, the contribution is . Which can be simplified to . It is easy to find = . How to simplify this? For each the answer is just = Note that .Idea, is that there are places. You have to reserve places. In each of the places, where you place the pair the probability is and in the remaining places where you don't, the probability is . You can then multiply be . And, also is . So, for each the answer can be expressed as where and can be precalculated as they don't depend on . This gives the proof behind expression used in the editorial. Submission: here

• 2 days ago, # ^ | ain't that always how it is for same round but separate division?

  • 2 days ago, # ^ | Oh wait, I didn't realize this. Tks

• 2 days ago, # ^ | int pos = find(all(v),1)-v.begin(); ans += pos+'a'; bro this part is wrong you should add last character of the block but you adding the first character from block which has count 1,let for k=3 block is "abbc" you should add 'c' but you adding 'a'. replace above two lines with ans += s[i] ;

  • 47 hours ago, # ^ | Thank you, but adding s[i] means that this character will definitely have a frequency of 1, but I am adding the character that also have a frequency of one,so how does it affect the final answer.This part is not clear by me. Can you please explain this, or just give me counter test case it would be much helpful.

    • 47 hours ago, # ^ | Let n=2 , k=3 , s="abbcab" In this 1st block will be "abbc" and 2nd block which is incomplete will be "ab" In 1st block you adding 'a' instead of 'c' , because 'a' also have count 1 and find function returns iterator of first matched element. Your logic giving ans "ac" but it is present and ans should be "cc".

      • 47 hours ago, # ^ | Thank you so much!

• 2 days ago, # ^ | gcd(a1,a2,a3...an)=gcd(a1,a1+a2,a1+a2+a3,...,a1+a2+a3..+an) so at the end we get sums of all sub problems which is just x so answer is gcd(a1,a1+a2,....,x) so ans is always divisor of x .

• 2 days ago, # ^ | Consider an array of numbers . Let be the greatest common divisor (gcd) of all these numbers. Since every number is a multiple of , we can express each number as follows: where are positive integers. The sum of these numbers is: Therefore, should be a factor of . And here all 's are positive integers so hence we have to find smallest factor of that is greater that or equal to ,say Then is our required

• 39 hours ago, # ^ | It's a math website

• 2 days ago, # ^ | By the way; it is 2D. Can you please explain your solution?

  • 2 days ago, # ^ | We can treat each pair of friends separately. Regardless of the pair of friends, the probability of selecting them is . At the jth excursion, if the ith pair of friends is selected, then its contribution to the answer is , where is the expected value of having selected the ith pair of friends earlier, and we get . Then if we are not sure if the ith pair of friends was selected (the probability of selection is ), the contribution of the ith pair of friends to the answer in the jth tour is . Combining the contributions to the answer from the i-th pair of friends in the kth excursion, the After the contribution of the ith pair of friends to the answer has been counted, the answer is obtained by adding up the contributions of each pair of friends to the answer. This is the result.The time complexity is $O(t\log MOD + m)$. Look here.It's my new solution.243708880

• 2 days ago, # ^ | The sum of m over all test cases is mentioned to have an upper bound of 10^6 so it wont pass

• 2 days ago, # ^ | ← Rev. 3 →   0 we want to check divisors . for each divisor , we also check , because it will be another divisor of , and we don't need to check any divisor , all of them were already checked.

• 2 days ago, # ^ | To Reduce TC: if i is a factor then x/i is also a factor, similarly for sqrt(x).We need to loop till sqrt(x) because all factors after it had already been taken [ by (x/i)]

• 45 hours ago, # ^ | Output is NO cbba

• 45 hours ago, # ^ | Oh sorry didn't see your #define there

• 45 hours ago, # ^ | Iirc when you're doing many operations with 64-bit integers, 64-bit compilers are significantly faster. I believe 64-bit compilers are faster (or at least not slower) most of the time. Where did you get tle with 64-bits and ac with 32-bits? Also, this has happened to quite a few people before and I don't think anyone has gotten a rejudge, so you're probably out of luck.

  • 44 hours ago, # ^ | ← Rev. 3 →   0 Thanks for your answer, it sounds like a reasonable explanation. In this problem 1250B - The Feast and the Bus I got tle in C++ 64 (243748301) and ac in C++ 17 (243748727). I also have a friend who got tle for similar reasons on a shortest path problem I think ? I'll try to find it but it was a long time ago By the way, if the runtime can change that much, during the testing phase, can't they try to submit solutions in both C++ 64 bits and 32 bits to avoid such things happening ?

    • 44 hours ago, # ^ | Here is your code with removing #define int long long and chaning one int to ll https://codeforces.com/contest/1925/submission/243752795 Gets an AC with C++ 17, not very strong though (because there are still a lot of lls)

      • 43 hours ago, # ^ | Oh thanks ! I wouldn't have thought that changing only a few ints to long long would make such a difference as most of the operations are in the segtree

• 43 hours ago, # ^ | ← Rev. 2 →   0 You are looking for the probability of a pair being chosen a fixed number of times (probability that the pair gets selected i times). What you are doing is just like, wrong I would recommend you to learn a bit about expected value (definition, linearity) and to do things more formally. You want E(S) where S is the sum of friendship values of all k pairs chosen for the excursions. S = X1 + ... + Xm where Xm is the sum of friendship values of pair i (over all the excursions it was chosen for). By linearity: E(S) = E(X1) + ... + E(Xm) Now, to compute E(Xi) you can fix how many times the pair i has been chosen and you end up with a simple sum to compute (which is a bit similar to what you sent, except you need some binomial coefficients for the probabiltiy).

  • 42 hours ago, # ^ | First of all, thank you for the reply. Sorry, but I don't understand what you mean by "fix how many times the pair i has been chosen". Could you provide an example of calculating using "binomial coefficients for the probability"? Thank you very much.

    • 40 hours ago, # ^ | ← Rev. 7 →   0 So let's consider pair i. (I technically skipped a step here, but overall it's just partitioning the events depending on how many times the pair i was chosen). And (which has a closed form that you pointed out in your original comment) Now, you are looking for which actually follows a binomial law. If you don't know what that is, I'll just try to explain intuitively: - you have probability for the pair i to be chosen at a fixed excursion so if you fix the excursions at which the pair i is chosen, the probability to be chosen exactly at these excursions is you have ways to chose the excursions at which the pair will be chosen So overall,

      • 33 hours ago, # ^ | can u explain div1 B ?

• 42 hours ago, # ^ | Great solution. I didn't notice that sum of is bounded in the problem statement. So although I came up with an ( is the modulo) solution, I didn't think it could pass and did not submit. So I tried to transform my original formula (which is similar to the expectation of a binomial distribution) into a direct formula through an algebraic way during the whole contest. Of course I failed. Now I realize that I should use an alternative explanation to form another simpler formula instead of transforming the original formula directly.

• 23 hours ago, # ^ | is too large for this problem because and the constant is not small enough. It is much better to process a problem with interval assignments and interval queries using a segment tree which has time complexity than a block array which has time complexity .

  • 23 hours ago, # ^ | Thanks!

• 32 hours ago, # ^ | ← Rev. 3 →   0 Spoiler

  • 25 hours ago, # ^ | thanks bro

• 26 hours ago, # ^ | ← Rev. 3 →   0 Input 2 3 2 6 babbaa 2 1 3 aaa Expected NO aab YES Produced YES YES

• 26 hours ago, # ^ | Take a look at Ticket 17298 from CF Stress for a counter example.

  • 23 hours ago, # ^ | Thanks. Why is this one failing?

    • 20 hours ago, # ^ | Take a look at Ticket 17306 from CF Stress for a counter example.

• 20 hours ago, # ^ | how are differentiating whether addition was performed first or multiplication ? order matters here right?

  • 18 hours ago, # ^ | ← Rev. 2 →   0 I am storing the lazy values for each node of the segment tree, which means that we must multiply the value at that node with first and then add (r — l + 1 is the length of the segment covered by node) to it, i.e., . Now let's say we are pushing the lazy information of a node, say to its child with lazy information then we can observe that becomes . Hence, we can accordingly modify the lazy_multiply and the lazy_add values. ( NOTE: The identity for lazy_multiply and lazy_add are 1 and 0 respectively. Since we also need to do the division operation, there is also a lazy_div for each node in actual implementation. )

    • 13 hours ago, # ^ | t[l].lazy_add = (t[l].lazy_add / t[id].lazy_div) * t[id].lazy_mul + t[id].lazy_add You are rounding values here. t[l].lazy_add may not be divisible by t[id].lazy_div

      • 12 hours ago, # ^ | Observation: is always of the form and t[id].lazy_div is always a divisor of so there will be always an exact division.

• 12 hours ago, # ^ | it works i do it in same way. code

  • 12 hours ago, # ^ | Thank you for letting me know that it's correct. How did you handle division without a lazy value for division? And why did you take mod? The original problem wasn't asking us to print the answer modulo M.

    • 12 hours ago, # ^ | I guess the problem in your solution is that the lazy division values can overflow if multiple updates are stacked on top of each other without pushing further. tmpzlp's solution uses a big prime modulo larger than the largest possible answer, and this solves all of your problems: Since the modulo is larger than the largest possible answer, the value reduced modulo will be correct. Since the modulo is prime, we can perform division via multiplication by modular inverse. Now we don't need a separate lazy division variable (since division is now multiplication) and the values won't overflow since we reduce them in modulo, though __int128 needs to be used for multiplication.

      • 113 minutes ago, # ^ | Got it. Thank you, sir. Btw, such a cool usage of __int128 ^w^

• 32 hours ago, # ^ | ← Rev. 2 →   +5 We are just walking from 1 to sqrt(x) When x divides i, that means there are 2 divisors of x, not just one -> i , x / i The first condition handles the first divisor and the second handles the second

  • 13 hours ago, # ^ | so the factors of x that are greater than sqrt(x) are just the same product we have seen before sqrt(x) but written vice versa? like if we have seen (a*b) before square root it's the same numbers repeating again but in reverse like b*a?

    • 13 hours ago, # ^ | Exactly. If it's a new concept for you, you should study number theory.

      • 13 hours ago, # ^ | Sure, will do

• 26 hours ago, # ^ | ← Rev. 2 →   +6 My solution: For each harbor I keep the sum of distances of every ship between this harbor and the next harbor. I can do it using a std::set maintaining the positions of all available harbors. Now i put the mentioned value for a harbor at position x inside a Fenwick tree ( the xth number in the Fenwick tree, if there is a harbor at position x, contains the value of that harbor). Now let's talk about answering each query, in each query i First take the sum of all values of harbors inside that segment. It's really easy to see that there are some ships in the segment that I'm not counting their distance but I should, and there are some ships outside that I'm counting their distance but I shouldn't. I can calculate these missing/extra values using the std::set we maintained above. It is a bit mathy, so I recommend taking a look at my implementation to understand it better: 243623915

  • 23 hours ago, # ^ | Your method doesn't require lazy propagation. Great. Can you please tell me if this approach will work? (Although it is a bit messy to implement)

• 19 hours ago, # ^ | You have to consider the number of test cases also

  • 15 hours ago, # ^ | I haven't had any problems like this before and i have never considered the number of test cases before as well, is this because in most problem there is a statement like:- "It is guaranteed that the sum of n and sum m over all test cases does not exceed 1e5 and the sum of k over all test cases does not exceed 2⋅1e5." While this question didn't??

    • 14 hours ago, # ^ | Yep that's exactly the reason

• 8 hours ago, # ^ | The editorial for 1C has been added. Unfortunately, there was an Indian ICPC Regionals contest the very next day of this contest and all three of us were judges for that contest. We didn't get any time on Sunday to write the formal tutorials in the editorial and the author of 1B and 1E was busy today. Hence, the delay.

• 8 hours ago, # ^ | ← Rev. 2 →   +10 Yeah, you are right. I probably messed up something while writing the editorial. But it was an editorial-only bug. The constraints in the problem are correct and according to the better bounds found by you. You can check that which is according to the value of and not . And yeah, the solution works only after rounding. There is a buffer of just query between the constraints and the calculated bound so you have to be quite precise.

  • 8 hours ago, # ^ | Actually, surprisingly my solution with the incorrect constant passes the tests when always rounding down (243937391), even though theoretically it should fail. I guess it is hard to kill solutions with slightly suboptimal constants at high values of , as sometimes you'll get lucky and get 3 queries when the worst-case is 4.

• 13 hours ago, # ^ | ← Rev. 2 →   0 I was wondering if there have been cases where an author came up with a problem, which had an obvious greedy solution but later came out to be wrong because someone came up with a test-case where it didn't work. This probably happens every now and then during the problemsetting process — usually this would be noticed during stress testing. But sometimes shit happens and these mistakes aren't caught, even with stress testing. For example Codeforces Round 846 (Div. 2) had a problem C with an intended greedy solution, but it turned out to be incorrect. The round got unrated and the problem was deleted as it was unsolvable with the given constraints.

• 75 minutes ago, # ^ | Well, I do have a proof for 2C/1A. It is easy and intuitive so I felt it unnecessary to explain in the editorial. Let the counter-case we are building using the greedy until we reach the end of be and the final counter-case be . There are two things that must be proven: If , then is not a subsequence of . If , then all possible strings of length formed using the first English alphabets are a subsequence of . Firstly, notice that the greedy algorithm divides the string into some blocks with each block (except possibly the last one) containing all the first English alphabets and where the last character appears exactly once in the block in the end. So, if you are aware of the well-known greedy algorithm to check if a given string is a subsequence of another string or not, you can notice that the first character of must match to the last character of the first block of since there is no better choice for it, the second character of must match the last character of the second block of because there is no other choice between the first chosen character and the last character of the second block and so on. Now if , the first character that is in and not in is not present in the last remaining block (possibly empty) of . So, the string subsequence matching algorithm fails and is not a subsequence of . Now, if , we already know that is a subsequence of . Now, the character in is the last character of the block of , If you replace it with any other character, it will still be present in the block of since these blocks contain all the first English alphabets. So, no matter what changes you do to the string , it will still remain a subsequence of . This proves the second part.