AksLolCoding's blog

By AksLolCoding, 36 hours 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
  • +63
  • Vote: I do not like it

»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Wow, record editorial release! Thanks for the contest!

»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

peak contest

»
18 hours 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

»
18 hours 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

»
18 hours 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

»
18 hours 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 :)

»
18 hours ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

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

»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

awesome contest thx.

»
18 hours ago, hide # |
 
Vote: I like it +22 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

»
18 hours 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.

»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

bruh

Didn't realize updates were independent lol

»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
17 hours 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.

  • »
    »
    17 hours ago, hide # ^ |
     
    Vote: I like it +1 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$$$.

  • »
    »
    17 hours ago, hide # ^ |
     
    Vote: I like it 0 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.

»
17 hours 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.

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

    i thought b statement was basically as simple as the problem would allow.

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

    B's statement is really short, no clue what you're talking about

    If they just said "the diversity is $$$T(\text{ones}) + T(\text{zeros}) + 1$$$ then the problem would be a slop div2a instead of a good div2b

»
17 hours ago, hide # |
← Rev. 2  
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.

»
17 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Post contest discussion stream with ABCDE here

»
17 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
16 hours 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.

»
16 hours ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

»
16 hours 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)

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

    sometimes they will get updated, you can check clist.by for approximate ratings

»
14 hours 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...

»
14 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

the statement for b sucked ass.

»
14 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
13 hours 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.

»
11 hours ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

literal slopfest

»
8 hours 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

»
7 hours 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 hours 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

»
5 hours 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 hours 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).

»
60 minutes ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

C seems too hard !

Is it just me ?