AksLolCoding's blog

By AksLolCoding, 6 days ago, In English

Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the strict time limit on E; it was very hard to balance allowing slow intended solutions but not fast cheese ones.

Rate the contest!
Rate the difficulty!

2285A - Composite Permutation

Rate the problem!
Hint 1
Hint 2
Tutorial
Code (C++)
Bonus

2285B - Diverse String

Rate the problem!
Hint
Tutorial
Code (C++)

2285C - Max Substitution

Rate the problem!
Hint 1
Hint 2
Hint 3
Tutorial
Code (C++)

2285D - Reverse Partition

Rate the problem!
Hint 1
Hint 2
Hint 3
Tutorial
Code (C++)
Bonus

2285E - Arithmetic Subarray

Rate the problem!
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code (C++)

2285F - Mooclear Reactor 3

Rate the problem!
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Code (C++)
  • Vote: I like it
  • +88
  • Vote: I do not like it

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Wow, record editorial release! Thanks for the contest!

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

peak contest

»
5 days ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

The 2nd one was too hard for me lol Now it's time to understand how to solve

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

wow so fast editorial. thanks

I didn't perform well in this round though

»
5 days ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

I was still able to cheese $$$O(nklog(nk))$$$ on E. Might be hackable.

398698053

»
5 days ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Yeah, my bad. I forgot to use long long on problem B, thought my solution was wrong, and ended up submitting 4 times.

Next time I’ll always use #define int long long :)

»
5 days ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

No contest can be better than goodbye 2026. But, I will accept it being equal.

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

awesome contest thx.

»
5 days ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Hi Administrators,

I am writing this comment on behalf of Chirag352 whose account was disabled during the contest. He started the contest by trying to solve question D but was using wrong value of MOD, so he got 3 wrong submissions, after 1:09 hrs, he started from question A, but while solving C, which also used MOD as 1e9+7, he realized his mistake in D's code and after submitting C, he corrected the value and also submitted D within 1-2 minutes and after this his submissions were skipped and the account was disabled. To justify his accountability, he has solved around 1000 questions on this platform and around 700+ on others and also he is my teammate in icpc this time and we are selected for 2 regionals. Please look on this matter as quickly as possible. Thanks

AksLolCoding MikeMirzayanov

»
5 days ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I feel like the amount of math problems in this contest is not normal.

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Isn't problem C $$$O(n \log V)$$$?

»
5 days ago, hide # |
 
Vote: I like it +5 Vote: I do not like it
A Rather simpler approach for E
»
5 days ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

bruh

Didn't realize updates were independent lol

»
5 days ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Solved D using Mo's Algorithm to sort the range count queries, thankfully the time limit was lenient

»
5 days ago, hide # |
← Rev. 3  
Vote: I like it +5 Vote: I do not like it

For problem $$$A$$$ we can simply use random shuffle. The only invalid cases are when $$$a_1 = 1$$$, $$$a_1 = 2$$$, or $$$a_i = 1$$$ for some prime index $$$i$$$. Since there are only $$$25$$$ primes up to $$$100$$$, the probability of getting an invalid permutation in one shuffle is at most $$$\frac{27}{100} = 0.27$$$. If we shuffle $$$60$$$ times independently, the probability that all attempts are invalid is at most $$$0.27^{60} \approx 1.4 \times 10^{-34}$$$, which is practically zero.

look at my submission.

  • »
    »
    5 days ago, hide # ^ |
     
    Vote: I like it +4 Vote: I do not like it

    Thanks for the interesting solution.

    To be more accurate, the only invalid cases are $$$a_1=1$$$, $$$a_1=p$$$ or $$$a_p=1$$$ ($$$p$$$ is prime). So the invalid probability of each random shuffle is $$$\frac{26}{100}+(1-\frac{26}{100})\times\frac{25}{99}\approx 0.45$$$.

  • »
    »
    5 days ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    If there was a testcase with t = 100 and all n = 5, your solution would have failed with high probability. If n = 5, only possible answers are when a1 = 4 and a4 = 1, so 6 correct answers. Overall 120 permutations => probability of failing all would be (114/120)^number of tries. You used 60 in your code => (114/120)^60 ≈ 0.046. Given t = 100, your solution would have failed with high probability.

»
5 days ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Liked (not loved) C. Max Substitution but I believe B. Diverse String was unnecessarily overcomplicated as a statement; it could have been simpler.

»
5 days ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

another solution for problem E. https://codeforces.me/contest/2285/submission/398683302

Real Code

In this code, we use the structure like LCA with binary-lifting, and the time Complexity is $$$ O(NK\log K) $$$. This is first coded by sadmecurial, but this user is unfortunately disabled.

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Post contest discussion stream with ABCDE here

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Editorial?????? Incredibly fast!!!!

»
5 days ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Problem E has questionable constraints.

$$$O(nk \log k)$$$ for $$$nk \le 10^7$$$ should not pass.

»
5 days ago, hide # |
 
Vote: I like it +34 Vote: I do not like it

»
5 days ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Quick editorial release, nice! Will try to upsolve D.

Slightly unrelated, but does anyone have any idea when the ratings for problems will be updated? It's been a while... the last time ratings were updated, it had been a while too (and I think they were updated shortly after someone posted a blog about it, although I don't know whether it was just a coincidence)

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I drew 4 pages of trees to up solve problem C after the contest, but after reading the editorial, I realized that I was too focused on the trees and missed the forest. No wonder why some people were able to solve C very quickly. RIP pupil :(, back to grey again...

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

the statement for b sucked ass.

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good for number theory lovers. Became expert btw...

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For E, I upsolved by maintaining linked lists of maximal size over (delta, position) elements, adding $$$(\frac{a_j-a_i}{j-i}, j)$$$ in front of $$$(\frac{a_j-a_i}{j-i}, i)$$$ when $$$i$$$ is at the head. This approach would allow one to do aggregations over all possible subarrays with at least 2 elements unchanged, not just find the maximal size.

»
5 days ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

literal slopfest

»
5 days ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

author forgot it is NNN and put a lot of number-theory

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In Problem B how can we say that the diversity is independent of on the positions of 0's and 1's in the explanation "_Consider the subsequence of 0s in s. Any operation with x=1 must affect a contiguous segment of these 0s. In fact, we can change any segment of these 0s to 1s by using the operation._ _ There are T(z)=z+(z−1)+⋯+1=z(z+1)/2 segments of 0s_"

here we assume contiguous segment of 0's and 1's and later says only depends on count of 1s and 0s.

Can anyone please explain it.

  • »
    »
    4 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    if we have 0100101 and let's say we want to look for the new distinct arrays that can be formed by the operation of changing a range [l,r] to 0, then choosing a subarray that only has 0's won't create any alternations, so 1 must be included choosing the ranges [2,2] = {1}, [1,2] = {0,1}, [2,3] = {1,0}, [2,4] = {1,0,0} all leads to same new array cause they only cause the 1 on position 2 to change, all other elements are the same so we should choose the ranges that are different based on the 1's they enclose the ranges that we can choose here are: [2,2], [5,5], [7,7] for one 1's [2,5], [5,7] for two 1's [2,7] for three 1's here we can already see the pattern of number of subarrays decreasing by one, everytime number of 1's enclosed in increased by one so its 3,2,1 here

    moreover, it's like we can choose any 1 as starting point and any 1 after it or itself as the ending point of the range for three 1's if we choose first 1 as the start then for the end, we have three options: itself, the second one, or the last if we choose 2nd 1 then we have 2 options and for the 3rd one as start we only have 1 option so we get 3+2+1 for three ones so it doesn't matter where the ones are, the number of ranges that can be formed with a given count of 1 is always the same and by ranges we mean those ranges that leads to a distinct new array that no other chosen ranges produce

    we can also say say if we have n number of 1's then the number of (start, end) pairs of that can be formed is C(n,2) but it doesn't include the unit length ranges so we got to add n to it C(n,2) + n = n(n-1)/2 + n = n(n+1)/2

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For Problem E

Index $$$i$$$ must be paired with a value at least a distance of $$$k+1$$$ from it if it will remain unchanged in any maximal subarray. You can then check each pair $$$j$$$ and hash the pair $$$(\frac{a_i-a_j}{i-j}, a_i-i\frac{a_i-a_j}{i-j})$$$ and maintain the maximum cnt for a window.

Even though the solution is $$$O(nk)$$$ with hashing it's literally impossible to pass. I've tried some small worst case improvements by making the hash table at most size $$$k^2$$$ and upgrading my pair hash but it doesn't seem to work. [submission:https://codeforces.me/contest/2285/submission/398740269]. I know technically this code is nklogk but it seems sorting vectors with unique is faster than using sets and maintaining the values of the hash is faster than calculating on the fly.

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem A, Bonus: (n-1)! * (n-P) (where P is number of prime indices from 1 to n).

  • »
    »
    3 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    $$$ (n-2)! * (n-P-1) + (n-3)! * (n-P-1) * (n-P-2) $$$ (P is number of prime indices from $$$ 1 $$$ to $$$ n $$$.

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C seems too hard !

Is it just me ?

»
4 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why was C way easier than A + B combined

»
3 days ago, hide # |
← Rev. 6  
Vote: I like it +8 Vote: I do not like it

My upsolve for F is based on a different sqrt decomposition that (if one could ignore the memory constraint) improves very slightly over the given complexity. Define the top C nodes (by degree) as heavy and the rest as light. For two light nodes in a pair, say one is the light partner of the other. $$$y$$$ is a heavy partner of $$$x$$$ when $$$(x,y)$$$ is a reactive pair and $$$y$$$ is heavy. Our DSU struct tracks all its nodes and all their light partners in hash tables, and bitsets of its heavy nodes and heavy partners. The number of light partners of a node is bounded by $$$\frac{m}{C}$$$. Then merging can be done in amortized $$$\log(n)\frac{m}{C} + \frac{C}{V}$$$ where $$$V$$$ is the size of a vector in bits (256 for avx2). The optimal $$$C$$$ then gives overall complexity $$$O\left(n+m+q \sqrt{\frac{m \log(n)}{V}}\right)$$$. However, the memory complexity is $$$O(nC)$$$ bits so I had to limit $$$C$$$ to make it work.

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In my opinion, the timelimits for problem E and F are extremely bad. If you have the intended complexity, you should get AC. This is not the case here, you have to constant-optimize a bunch. For E, what complexity should have been killed? $$$O(nklog(nk))$$$? Because guess what, $$$log(nk) = O(log(k))$$$, so the entire problem comes down to constant optimization. Moreover, you can easily get TLE with a $$$O(nk)$$$ solution using hashmaps, while optimized $$$O(nklog(nk))$$$ passes in a quarter of the timelimit. For F I have not gotten AC, despite having tried both $$$O(n\sqrt{n})$$$ and $$$O(n\sqrt{n\log(n)})$$$ solutions, and at this point I don't want to try any further.

I have not seen the scoreboard (likely the top is mostly AI cheaters, anyways), but in my opinion, if suffiently many contestants had TLE with intended complexity, the round should be unrated.

  • »
    »
    3 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    while I wasn't a fan of the constant optimization, since when has a strict time limit been grounds for unrating a round? the model solution is correct, and if your solution is too slow, that's your problem.

    also, the tight timelimit on E was to kill optimized $$$O(nk^2)$$$ solutions, obviously the author was not trying to kill $$$O(nklog(nk))$$$ solutions...

  • »
    »
    2 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    For E, please read the second line of the editorial: Apologies for the strict time limit on E; it was very hard to balance allowing slow intended solutions but not fast cheese ones.

    For F, the intended solutions passed without trouble during testing. Unfortunately, there are a few hacks after contest since tests are quite hard to generate. Now it is possible the time limit was too strict. Apologies about that.