Judge Code will be added after hacking phase.
Problem Credits: cry
Analysis: cry
If $$$n$$$ is a multiple of $$$4$$$, then you can have $$$\frac{n}{4}$$$ cows. Otherwise, you must have at least one chicken, so you can have $$$\frac{n-2}{4}$$$ cows and $$$1$$$ chicken.
Problem Credits: sum
Analysis: cry
Let's define every $$$k$$$ by $$$k$$$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $$$k$$$'th row and every $$$k$$$'th column.
Problem Credits: cry
Analysis: cry
For two strings to be the same after sorting, they must have the same occurrences of every possible lowercase letter. To answer the query for a range $$$[l, r]$$$, we must ensure that after the operations, $$$cnt_c = cnt2_c$$$ must where $$$cnt_c$$$ is the number of times character $$$c$$$ occurs in the range for $$$a$$$ and $$$cnt2_c$$$ is defined similarly for $$$b$$$. Both $$$cnt_c$$$ and $$$cnt2_c$$$ can be obtained by doing prefix sums for character $$$c$$$ specifically. Note that since there are only $$$26$$$ possible $$$c$$$, you can afford to create $$$26$$$ length $$$n$$$ prefix sum arrays.
In one operation, you can replace one occurrence of a character $$$c$$$ with another character $$$c2$$$. Essentially, you are subtracting one from $$$cnt_c$$$ and adding one to $$$cnt_{c2}$$$. Obviously, you must choose $$$c$$$ and $$$c2$$$ such that $$$cnt_c > cnt2_c$$$ and $$$cnt_{c2} < cnt2_{c2}$$$. So, we only have to focus on $$$c$$$ or $$$c2$$$ since one decreasing will automatically lead to the other increase. The answer is just the sum of $$$cnt_c - cnt2_c$$$ if $$$cnt_c > cnt2_c$$$ over all possible lowercase characters $$$c$$$.
Problem Credits: sum
Analysis: cry
There are several solutions to this problem, The easiest way is to just fix either $$$a$$$, $$$b$$$ or $$$c$$$. Let's fix $$$a$$$. Since $$$ab + ac + bc \leq n$$$, we know at the minimum, $$$ab \leq n$$$. Divide on both sides to get $$$b \leq \frac{n}{a}$$$. When $$$a = 1$$$, there are $$$n$$$ choices for $$$b$$$. When $$$a = 2$$$, there are $$$\frac{n}{2}$$$ choices for $$$b$$$. So in total, there are $$$n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$$$ total choices for $$$b$$$. This is just the harmonic series, so over all possible $$$a$$$, there are about $$$n \log n$$$ choices for $$$b$$$. Therefore, we can afford to loop through both $$$a$$$ and $$$b$$$.
Now that we have $$$a$$$ and $$$b$$$, all that's left is to solve for $$$c$$$. Let's solve for $$$c$$$ in both equations. In the first equation, we can factor $$$c$$$ out to obtain $$$ab + c(a+b) \leq n$$$. So, $$$c \leq \frac{n-ab}{a+b}$$$. In the second equation, $$$c \leq x - a - b$$$. Since we want the $$$c$$$ to satisfy both inequalities, we must choose the stricter one. So, the number of possible $$$c$$$ is $$$\min(\frac{n-ab}{a+b},x-a-b)$$$.
The answer is the sum of number of possible $$$c$$$ over all possible $$$a$$$ and $$$b$$$.
Problem Credits: cry
Analysis: cry
How can we efficiently check if a range contains the same amount of zeroes and ones? Let's create an array $$$a$$$ where $$$a_i = -1$$$ if $$$s_i = 0$$$ and $$$a_i = 1$$$ if $$$s_i = 1$$$. Let's denote $$$p$$$ as the prefix sum array of $$$a$$$. We want the contribution of $$$-1$$$ by the zeroes to cancel out with the ones, so if $$$p_r - p_{l-1} = 0$$$, then the range $$$[l, r]$$$ contain equal amounts of zeroes and ones. We can rephrase the problem as the following: for each subrange $$$[l, r]$$$, count the number of pairs $$$(x,y)$$$ such that $$$p_{x-1} = p_y$$$.
Let's fix $$$p_{x-1}$$$ and keep track of all potential $$$y$$$ such that $$$y > x$$$ and $$$p_{x-1} = p_{y}$$$. How many subarrays will cover $$$[x, y]$$$? Well, we have $$$x+1$$$ options as $$$l$$$ and $$$n-y+1$$$ options as $$$r$$$, so the range $$$[x,y]$$$ contributes to $$$(x+1) \cdot (n-y+1)$$$ subarrays. We just need to calculate this expression for all potential $$$y$$$ now. Let's denote the all possible $$$y$$$ as $$$y_1, y_2, ... y_k$$$. We are asked to find the sum of $$$(x+1) \cdot (n-y_1+1) + (x+1) \cdot (n-y_2+1) + \dots + (x+1) \cdot (n-y_k+1)$$$. Let's factor $$$(x+1)$$$ out, and we have $$$(x+1) \cdot ((n-y_1+1)+(n-y_2+1)+\dots+(n-y_k+1))$$$. Since, the second part of the expression is just the sum of all $$$(n-y_i+1)$$$, we can first precalculate that sum and since $$$y > x$$$, subtract as we sweep from left to right.
Problem Credits: sum
Analysis: cry
Let's first solve the problem in $$$\mathcal{O}(k)$$$. One possible solution is to loop through each operation and take the largest $$$a_i$$$ each time, and set $$$a_i = \max(0, a_i - b_i)$$$. This can be done with a set or a priority queue.
With that in mind, let's binary search for the largest $$$x$$$ such that every value we add to our score has been greater or equal to $$$x$$$ for all $$$k$$$ operations. Define $$$f(x)$$$ as the number of operations required for every $$$a_i$$$ to be less than $$$x$$$. Specifically, $$$f(x) = \sum_{i=1}^n \lceil \frac{a_i-x}{b_i} \rceil$$$. We are searching for the smallest $$$x$$$ such that $$$f(x) \leq k$$$. Once we've found $$$x$$$, we can subtract $$$f(x)$$$ from $$$k$$$. Note that now, $$$k$$$ must be less than to $$$n$$$ (otherwise we can another operation on all $$$a_i$$$). So, it suffices to run the slow solution for these remaining operations. Alternatively, we can notice that the remaining operations will all add $$$x-1$$$ to our answer (assuming $$$x > 0$$$).
To obtain the sum of all $$$a_i$$$ we collected when calculating $$$f(x)$$$, we can use the arithmetic sequence sum formula. For each $$$i$$$, the number of terms in the sequence is $$$t = \lceil \frac{a_i-x}{b_i} \rceil$$$. The first term of the sequence is $$$f = a_i - b_i \cdot (t-1)$$$. The last term is $$$a_i$$$. Using the formula, we can add $$$\frac{t}{2}(f+a_i)$$$ to the answer.
Problem Credits: cry
Analysis: cry, awesomeguy856
There are two configurations to satisfy every friendship $$$(a, b)$$$: activate all the roads from $$$a \rightarrow a+1 \rightarrow \dots \rightarrow b$$$ or $$$b \leftarrow \dots \leftarrow n \leftarrow 1 \leftarrow \dots \leftarrow a$$$. Let's fix a road we deactivate. Say it goes from $$$i \rightarrow i+1$$$. Observe that the configuration for all friendships is fixed to one of the two cases. For example, if $$$a \leq i < b$$$, then we must use the second configuration.
We can try fixing every road and taking the minimum of number of roads. This can be done with sweep line. Once we reach $$$i = a$$$ for any friendship, we toggle to the second configuration. Once we reach $$$b$$$, we toggle back to the first. We can track maintained roads by performing a range addition on a lazy propagated segment tree for each point covered by the current configuration. The number of roads required is $$$n$$$ minus the number of occurrences of zeroes in the segment tree, which can be tracked with Counting Minimums in a Segment Tree.
Consider the $$$n$$$-gon formed by the houses, with each road becoming an edge of the polygon. We draw diagonals between houses if they are friends. Let each diagonal arbitrarily "cover" one side of the polygon, where every road contained within one section split by the diagonal is covered by the diagonal.
We claim that two roads can both be deleted if and only if they are covered by the same set of diagonals. First, this is equivalent to saying that when we draw a line between these two roads, they do not intersect any of our drawn diagonals. (This is since if any diagonal covers one road and not another, then they must be on opposite sides of the diagonal, so drawing a line between the two roads must intersect that diagonal. The converse also holds.)
Now note that if two roads are on opposite sides of a diagonal, they cannot both be deleted, as then there is no path along maintained roads that connects the two endpoints of the diagonals, or the two houses that are friends.
So it suffices to count the most frequent set of covered diagonals over all roads.
We can represent a diagonal cover for some road using a xor hashing, where each diagonal is assigned a random number, and the roads that are covered by that diagonal are xor'd by this number.
By using $$$64$$$-bit integers, the probability of collision is negligible, as each 64-bit integer has equal probability of representing a unique set of diagonals, and we have at most $$$n$$$ represented sets.
For each pair of friends, we want to xor all values in a range by some random number. This can be done with a prefix xor array in $$$\mathcal{O}(1)$$$ per pair of friends. Counting the most frequent value at the end will take $$$\mathcal{O}(n \log n)$$$ time if a map is used or $$$\mathcal{O}(n)$$$ if an unordered map is used. In all, this solution runs in $$$\mathcal{O}(n \log n + m)$$$ or $$$\mathcal{O}(n + m)$$$ time.
cry orz
Couldn't solve D. RIP my brute force skill.
orz
orz
orz kill me i cant do F
orz I also.
i almost finished on it but then time was up, man what a mess ive done
also i was 30' late for the contest so screw me >:(((
Oh and I thought when I was seeing the standings As this was not rated for you. You found it too much of a hassle to code XD
awesomeguy856 orz
omeganot orz
what is 'orz'?
its a slang expression used to show admiration or respect for someone's skills, It originated from an emoticon representing a person bowing down in respect.
After reading problem F You realize that nuclear bombs take so much time to bomb!
sadly this is not the case in palestine!
G reminds me of this JOISC problem
In problem F: We are searching for the largest x such that f(x)≤k
Won't we reach infinity by doing that?
$$$x$$$ can't be larger then maximum element of array a.
fixed
My solution for problem F:
let's find the minimum number
X
, whereX
is the smallest number that all numbers in arraya
can be less or equal than using at mostk
operations.then, you calculate the answer for making all the numbers in
a
less thanX
, and maintain valuesk
anda[i]
for eachi
.After all you will be left with
k
operations, so you add to the answer :number_in_a_equal_X * k
link to my solution
isn't that the same solution as mentioned in the editorial?
oh, ohk i get it, you sped up the last part of solution by doing
number_in_a_equal_X * k
. That's good.Amazing xor-hashing solution for G, love it!
great contest, really fun problems. i wish i managed to solve E on time as well but oh well
Can anybody tell why this solution for C is getting MLE?
Submission
You use map. Try replacing it with arrays and you'll be fine.
please can anyone explain why my code works or if it can get hacked please hack it : ), i will be so happy (https://codeforces.com/contest/1996/submission/272827778)
I think it can't be hacked because worst case I found O(2 * 10^9) , and it's fast enough for your code to pass because the operations sums and multiply aren't that heavy.
Can anyone explain how this code works? I don't understand it. Also, can you provide some sources that explain how it works? Thanks! 272756177
brother can u explain my code please : )
cry sum Is there a penalty on unsuccessful hacking attempt?
no
Thank you for the editorial ! There is just a little typo in the explanation of problem E. You wrote in the line before the last one $$$(x+1) \cdot ((n-y_1+1) + (n-y_2+2) + ... + (n-y_k+1))$$$. It shouldn't be $$$n-y_2+2$$$ but $$$n-y_2+1$$$
thanks sir