As a non-tester, I'm still waiting for invite

ScreenCast

Same here :)

Congratulations bro

agree

Exactly!!

All is good don't limit yourself

What I think of when I see Chinese spam

Chinese, please calm down!!!!

Changing Chinese to Japanese makes no sense.

why so downvotes "."?

disadvantages of being expert.That's the reason i am still specialist.

Obviously to make an unbalanced round :D (no offence)

Try to think about case : how does answer change if we pick such $$$(i,j)$$$ that $$$(A_i$$$ $$$mod$$$ $$$k)$$$ $$$+$$$ $$$(A_j$$$ $$$mod$$$ $$$k)$$$ $$$>=k$$$ .

For example : $$$k=3$$$

$$$A:{1,2,4,5}$$$

matching $$$(1,5),(2,4)$$$ gives answer $$$4$$$ and matching $$$(1,4),(2,5)$$$ gives $$$3$$$

for each value a[i], a[i]/k will always be there in the total answer. So, we can add a[i]/k for all i. Then, in another array we store a[i]%k. Now, the maximum sum of two of the remainders of a[i] and k is 2k-2. And (2k-2)/k is 1. So we have to find the number of pairs that we can form (from the remainders) such that their sum is greater than or equal to k. We can do this using greedy + two pointers. My solution — https://mirror.codeforces.com/contest/1690/submission/159852372

If you have some more basic questions of this concept please do share. I didn't knew about this earlier, that such a topic exists. Thanks.

What edge case?

Yeah, I got all the cycles and tried to get all the number of moves for each cycle such that all the letters get matched to the correct locations. But I had no idea how to go on from there without brute force.

For individual cycle you need to find number of operations after which string will repeat with brute force and then take LCM.

try to check for pattern, like if cycle string is abab you take the lcm of answer with 2(not 4)

Until the last 2 problems lol

I took more time in A , than (B+C+D) combined xD

Yes! Sometimes $$$B$$$ is more indirect and confusing than $$$C$$$. I too spent slightly more time on problem B than C:

Because that's traditionally how podiums work.

Because

Ya, That's true );

Instead of maximizing values, we want to "minimize" loss. Notice that if we group 2 items into the same package, their sum might not be divisible by $$$k$$$. So we can see here some "profit" are lost (which is the remainder of $$$(a_i + a_j)$$$ $$$\text{mod}$$$ $$$k$$$. Therefore we want to pair items in such a way so our profit loss are minimized.

For each good it is sure that u can get a[i]/k.Then you still have to deal with n a[i]%k. Use f[j] to record the number of a[i]%k that == j. If u can find two things that add up over k，ans++. Even the biggest two goods，still 2k-2，and after /k，it is 1. 159835536

Int overflow. Use ll ans = 0; instead of int ans = 0;.

My solution is firstly for each $$$i$$$, add $$$a[i]/k$$$ to the answer, then reduce $$$a[i]$$$ to its remainder divided by $$$k$$$.

Then for example with $$$k = 6$$$ : we want to pair an $$$a[i] = 4$$$ with something $$$\geq 2$$$ (so not $$$1$$$) to get more cost, this can be done with 2 pointers

Edit : nevermind, got hacked :d

Update: Take a look at Ticket 11121 from CF Stress for a counter example.

we need to maximize floor((a[i] + a[j]) / k)

floor((a[i] + a[j]) / k) = a[i] / k + a[j] / k + (a[i] % k + a[j] % k) / k -> (1)

=> we need to maximize (1)

a[i] / k and a[j] / k are constants, so we cannot maximize them. Therefore, they directly contribute to the answer.

=> we only need to maximize (a[i] % k + a[j] % k) / k

The above expression can be maximized when the numerator is maximum since the denominator is constant.

=> now we need to maximize (a[i] % k + a[j] % k). This can be done by an approach similar to two-sum where we try to pair the smallest remaining element with the largest remaining element such that their sum is >= k (because only then the sum can contribute towards the answer)

"baba" will become equal to orginal string after 2 rotations and not 4

Yes. The periodic can be something like abcabc for this case, you need to take the length 3 instead of 6 into account

Ye that's about it. If you have a -> b -> a -> b cycle then it's rotational value is 2 not 4.

The one who spent less time gets a higher rank.

You don't need KMP for this. I think normal brute force would work to check all periods. I used divisors which need modular arithmetic to prove correctness

In submission, it is written " 'out of bounds' on the line 128". Probably when rem[k-i] is empty

Assuming that i == k-i then, you might reach a case where the size of the vector only consists of 1 element and you're popping back it twice (for example where $$$i$$$ and $$$k-i$$$ is equal to 0)

You have directly assumed that the number of members in the cycle is the number of iterations it will take to loop back to initial value or 1 in the case of similar characters in the loop. But suppose take the case abab in this it will take 2 iterations only. abab --> baba --> abab.

What you actually needed to do here was find if the string has a repeating pattern which you can do in two ways as pointed by many people — 1. Using Longest Prefix Suffix — O(n) time complexity 2. Or rotating the array till it is equal to its initial value — O(n^2)

You haven't considered if a cycle has string like abcabc, when this is the case, the length of the cycle is not 6 but 3

xd

probably you registered the contest before you reached expert ,that happened to me before.

Take a look at Ticket 11101 from CF Stress for a counter example.

This kind of bugs is one of nightmares in java. Remember that ArrayList returns Integer, not int. You should use equals instead of ==, when you are comparing Integer with Integer. In your AC code, you compared Integer with int, so it was fine.

It can be solved using prefix sum. You basically count up to each index how many 'B' are there and store them in an array, the loop through this prefix array and check in a subarray of length k how many 'B' are there. I'm not really good at explaining so you can check my code and ask any questions if you want

If you want to find cycles in permutation then you can use DSU.

dsu works but is kind of an overkill. I usually go for a dfs-like iteration and keep visiting the next element until I reach the beginning from where my iteration started. I also keep a bool array to not run a specific cycle twice

Take a look at Ticket 11322 from CF Stress for a counter example.

No

1 6 cabcba 6 1 5 2 3 4

correct output — 2 your output — 4

The results aren't out yet

that test is 9 cbbbcbccb 9 5 6 8 4 3 1 2 7 which contains a cycle of index 5-2-8-4 cbcb ,it justs need 2 steps instead of 4 so the answer is 6 not 12

What about G?