How did you write in white font?

I guess you can become pupil in today's round if you solve A and B fast. Good luck!!

omg no green round

OMG no green round

omg orange round

omg no green round

We have same rating, stranger!

No one wanted you to join the contest

unacceptable contest! why can humans make contests now on codeforces? does no one know how things run among humans when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it

I can see that you have been consistent for the past few days. Hope you reach green, good luck bro!!

they literally have a 12 hr gap in their start time...

Skill Issue Tbh

tourist in parallel universe

how it's unbalanced?

no we are just retarded

or maybe we need to improve ( i mean look at the standing alot of peoples solved it)

Here you go. https://codeforces.com/blog/entry/62393

Same got TLE, in python...

Tried collections.Counter, defaultdict and all such, but nothing worked...

It seems that O(n) solutions won't be accepted. Maybe I just need to work out an O(log(n)) solution next time...

Viewing the acceptance rate, it seemed that many people had similar issues.

Anti-hashing testcases. I was aware of that...

Basically there are some testcases that purposefully break solutions that use hashing.

More details

in the worst case, the time complexity for all the operations in an unordered_map is O(n)

Construct a prefix array $$$p$$$. Then you can break the original array into segments based on the positions of $$$0$$$s in it. Each segment starts at a $$$0$$$ and ends at the index before the next $$$0$$$. Suppose the positions of $$$0$$$s in $$$a$$$ are $$$z_i$$$, then the maximum score you could get from subarray $$$[z_i, z_{i+1}-1]$$$ is the maximum frequency of any element in the subarray of $$$p$$$ from $$$[z_i,z_{i+1}-1]$$$. I implemented this by using a resetting the frequency count every time I hit a zero, and then finding the maximum among the frequencies when I reached the next zero. Also, any $$$0$$$s in $$$p$$$ that occur before the first $$$0$$$ in $$$a$$$ have to be counted as well. Hope this helps!

My Solution for D:

Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.

Otherwise,Let's construct the solution.

First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.

How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).

This is actually a problem of solving congruence equations:$$$(2^{key}-1)+2^{key}X=0(mod d)$$$,use ecgcd to get such $$$X$$$.

Lol, I rewrote my solution to c++ to pass 8
Didn't even think we could have hash-hack pretests

You're right

Well, It is nice that they included it in pretests I guess.

I suspect it was, I only passed pretest 8 after adding code specifically to stop hash hacks (mainly xoring each value in the dictionary by a predetermined random value)

1. You consider base 2 factors independently — if 2^x divides d, then both a and b must have x clear least significant bits
2. Now let d be not divisible by 2. We want to use 30 most significant bits, because they are enough. Let's say that a | b has remainder y over d. then we are looking for number x, such that x * 2^30 = d — y mod d. So x = (d — y) * (2^30)^(-1). Then we return x * 2^30 + (a|b)

The main idea is to split the original array into segments based on the positions of $$$0$$$s. Each segment starts at a $$$0$$$ and ends at the index before the next $$$0$$$. Then I can perform the operations in such a way that each $$$0$$$ only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count all $$$0$$$s in $$$p$$$ that occur before the first $$$0$$$ in $$$a$$$. Hope this helps!

And here I was thinking that it had to be done using 2 pointer+ sliding window

Then I realized it could be done with brute but was unable to find the maximum times inner loop should work :(

$$$O(100n)$$$

It seems the intended solution is to bruteforce with one simple observation: By the pigeonhole principle, a substring of length $$$101$$$ would have at least one character with at least $$$11$$$ occurrences. So we only have to check for substrings of length upto $$$100$$$, because lengths above that are guaranteed to be non-diverse.

The main idea is to split the original array into segments based on the positions of 0s. Each segment starts at a 0 and ends at the index before the next 0. Then you can perform the operations in such a way that each 0 only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count all 0s in $$$p$$$ that occur before the first 0 in $$$a$$$. That will give you the answer.

even better: 100 is only 10^2, not 10^3

It will update soon :)

This should have been included in the official editorial. I think most of the solutions came from this intuition. Hats off man!

Can i ask why in your solution you have used i+228 if 100 is the maximum length of valid substring?

I learned main idea when study IOI 2002 Batch Scheduling. This problem's main topic is CHT but provides one observation related to the prefix sum. Other implementations were learned while upsolving code forces.

It was quite simple to come up with by looking at the prefix sum array and the zeros ;-)

bro maybe u were just overcomplicating it. C is quite simple as you can probably tell from the editorial (i havent read it yet tho)

and when i look at the solutions many people are suspiciously using that i+228 logic, is there actually any reason for it to be i+228 or is everyone just copying this video?

You can use https://cfviz.netlify.app/virtual-rating-change.html and look what rating change you may have had.

thanks

If there are more than 10 * 10 + 1, we can realise that there is at least one digit that appears more than 10 times. It is because there are at most 10 digits, and if those digits doesn't appear more than 10 times, it means that there are at most 10 * 10 numbers, which contradicts what we are saying. (I think the rest is the most delicious part of the problem, so i won't say it...)

Start with the simplest case:

$$$a[x]=0,a[1],a[2],...,a[x-1]≠0,a[x+1],a[x+2],...,a[n]≠0$$$.

How to determine the value of $$$a[x]$$$?

Case1:make $$$a[1]+a[2]+...+a[i]=0$$$,the contribution is $$$1+cnt$$$,$$$cnt$$$ is the number of $$$y>x$$$,which make $$$a[y]+...+a[n]=0$$$.

Case2:make $$$a[1]+a[2]+...+a[i]=k$$$,the contribution is $$$cnt$$$,$$$cnt$$$ is the max number of $$$y>x$$$,which make $$$a[y]+...+a[n]=k$$$.