1119A - Ilya and a Colorful Walk
Author, preparation: 300iq.
Editorial
1119B - Alyona and a Narrow Fridge
Author, preparation: KAN.
Editorial with bonuses
Aleks5d invites you to compete in the shortest solution challenge for this problem. His code (155 bytes):
Code
Authors during the contest
1119C - Ramesses and Corner Inversion
Author, preparation: 300iq.
Editorial
Author, preparation: cyand1317.
Editorial
Code
Author: gen, preparation: 300iq.
Editorial
1119F - Niyaz and Small Degrees
Author, preparation: 300iq.
Editorial
1119G - Get Ready for the Battle
Authors: Aleks5d, KAN; preparation: Aleks5d.
Editorial
Author, preparation: RDDCCD.
Editorial
Problem F: AC 4
Problem G: AC 7
Problem H: AC 5
...
Thanks for the fast editorial!
Passed G with the following solution.
Increase $$$hp_1$$$ such that $$$n$$$ is divisor of $$$\sum hp_i$$$. $$$m$$$ times choose greedily maximum group size such that it's possible to attack with this group without affecting the answer and then simulate this attacks randomly.
Any idea why this solution works?
It doesn't: https://codeforces.me/blog/entry/66411?#comment-504310
It seems that someone is curious about what I've done on problem A. Let me describe what has happened.
Contest starts ---> Open problem A ---> A little difficult? ---> I can solve it by binary search in O(nlogn) !
===== One hour later =====
Oh my god!!!
This look like funny What is your rank?I want to see your submission history
You can get into his homepage and click the points on the rating graph. One point stands for one contest. Clicking one will lead you to his rank in that contest.
Finally i find it ,thank you
How to solve B in O(nlogn) or O(nlog^2 n)?
For $$$O(n\log^2 n)$$$, we can binary search the answer. For $$$O(n\log n)$$$...maybe some interesing sortings? (Radix sort?)
I think, binary search gives $$$O(n \log n)$$$. Because $$$\sum^n i 2^i = O(n 2^n)$$$.
You only need to sort the array once if you also keep the original indices of each bottle. Then binary search the answer.
binary search + sort -> solved in O(n log^2 n)
sort in decreasing order and record the position of each value , then do binary search -> solved in O(n log n)
Can you please explain I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct? Similarly in example 1 — suppose there are 2 shelves one shelf has a bottle of size 5 and 4-second shelf has a bottle of size 1 and 2 therefore answer would be 4?
You cannot pick arbitrary bottles from the input. You need to pick k bottles from the beginning of the line. Therefore in example 1: "2 3 5" is ok, but "2 3 5 4" is too much, so the answer is 3. In example 2: "9 1 1 1" is ok, but "9 1 1 1 1" is too much, so the answer is 4.
Then why we are sorting in decreasing order...as written in editorial... sorting leads to derrangement of elements..from it's initial position..... please answer because i have literally spend 1 hour on thinking this only..
The problem statement says at the end that you need to look for the largest k: "Alyona is interested in the largest integer k".
The editorial says "just try all possible k".
Therefore you need to consider the following cases separately (independent of each other):
k=1 — you need to check if the first bottle fits
k=2 — you need to check if the first 2 bottles fit
k=3 — you need to check if the first 3 bottles fit
etc.
When you are checking for example k=3, take the first 3 bottles (from the input array that was not sorted yet), sort them, check if they fit in the fridge.
When you are checking k=7 forget that you have sorted the 3 bottles for k=3 — start again from scratch: take the first 7 bottles (from the input array that was not sorted yet), sort them and check if they fit in the fridge.
Does it make sense now?
would anyone post O(nlogn) solution for me please?
we can use set instead of vector(or array) to solve in O(nlogn) as when we are inserting the elements they are inserted in a sorted manner and we continuosly subtract the height of the bottles ....when the result becomes negative we can just print the answer
I did problem B in 125 bytes (including an LF) in Ruby. I tried to squeeze author's Python solution and it became 125 bytes as well. So to me seems like a notorious coincidence.
I can do like this. It's 109 bytes
Ok. Now it's 102 bytes.
By my count your solution is 99 bytes. Do you count 2 characters for newlines?
Also, you can remove 3 additional bytes, giving 96 bytes:
Submission: 52431059
Oh nice! Guess I was too obsessed with functional programming when doing code golf.
By using exec, we can achieve a significant 3 bytes improvement!
make it only 93 bytes :)
52473099
Why this is correct for C — If number of cells where A and B doesn't match in every row and column is even then answer is 'Yes' else it's 'No'?
The tutorial says that if the parity in each row and column remains the same, then the answer is yes. We can see that for every position where A and B doesn't match, we try to change it. If we change an even amount of positions in each row and column, then the parity in each row and column remains the same.
Can someone explain the proof of problem C?
tutorial means we always choose to operate (1,1,x,y) , every two element in one column can be change in one turn, because one column has (0 or 2 or 4 or 6 or num in odd),one column can be obviously set to the goal via some operations.imagine we have done every column except the first column,because for the sake of setting other column to the goal, and each row also has(0 or 2 or 4...) difference,the element in the first column also must be changed (0 or 2 or 4...)times, whether there exist difference in the first column doesn't change the result , if there exist difference in the first column, it just changed(2-1,4-1,6-1..)times.
Thanks for the effort!
Simple DP solution for E: 52420096
lol that is not dp
why?
he is just running the greedy algo, right?
Yes. But why greedy algo != dp? Task tags contains dp and greedy algo.
Can you explain solution? please
dp[i] means what is the answer for a[0],a[1]...,a[i] sticks.
using this dp we can calculate remaining sticks that we didn't use them
in any triangle before. for update dp[i] we have dp[i-1] triangle before
plus with any 2 sticks of a[i] and any stick of j (j < i) that we didn't use
that in any triangle before we can make a new triangle. after it if remaining sticks
from a[0] to a[i — 1] over, we can use 3 remaining sticks of a[i] and make a new triangle.
sorry for bad English .
Это нормально, я тоже не очень хорошо знаю англ. Спасибо за обьяснение.
Пожалуйста :)
I have slightly different approach on problem E. Don't know why it is true but it passed the systests. If the number of ones in the initial array is 0 then the answer is $$$sum of all elements / 3$$$(somehow we can take almost everything). If there are ones then we should compute the minimum possible amount of unused ones. Go from the end to the begginng of the array storing current amount of tiles we can use with the ones. If current $$$a_i$$$ is even the we increase this amount by $$$a_i / 2$$$, otherwise, we take one triangle from three tiles of this type and take the rest increasing amount by $$$(a_i - 3)/2$$$. Then the answer if $$$((sum of all elements) - (minimum number of unused ones)) / 3$$$.
Here's my code : 52409622
Here's a 112 byte solution to B: 52424010
The editorial for problem H is little unclear.
I try to explain from another aspect. Take the polynomial ring $$$Z[a, b, c, d]$$$. For the individual $$$i$$$, let $$$F_i$$$ be the vector of length $$$2^k$$$ where $$$F_i[0] = a$$$, $$$F_i[b_i] = b$$$, $$$F_i[c_i] = c$$$, $$$F_i[b_i \oplus c_i] = d$$$. We can verify $$$\mathrm{FWT}(F_i)$$$ contains only $$$4$$$ elements $$$(a+b+c+d)$$$, $$$(a+b-c-d)$$$, $$$(a-b+c-d)$$$, $$$(a-b-c+d)$$$ in the specified ring. Suppose that we have $$$x$$$, $$$y$$$, $$$z$$$, $$$w$$$ copies of each elements for $$$\mathrm{FWT}(F_i)[k]$$$. Since FWT is a linear transformation, $$$\mathrm{FWT}(\sum_{i} F_i)[k] = (x+y+z+w) a + (x+y-z-w) b + (x-y+z-w) c + (x-y-z+w) d$$$. Thus, we can obtain the value of $$$x$$$, $$$y$$$, $$$z$$$ and $$$w$$$ from $$$\mathrm{FWT}(\sum_{i} F_i)$$$ directly.
I think editorial proof for problem G is wrong. It states "This way the first $$$i$$$ groups will have size $$$k_i$$$", but that would require the first group to atack every enemy in different steps, which is impossible if the final answer is less than $$$m$$$.
I submitted a solution (52431440) that greedily chooses the biggest possible size for a group that doesn't waste soldiers in any atack (after incrementing the first enemy group health so that total enemy health is a multiple of $$$n$$$). It passes system tests, but I couldn't come up with a proof of its correctness yet.
Well, I think editorial proof can be fixed this way:
Instead of considering $$$k_1, k_2, ..., k_{m-1}$$$, we should split them in $$$k_{1,1}, k_{1,2}, ..., k_{1, r_1}$$$ and $$$k_{2,1}, k_{2,2}, ..., k_{2, r_2}$$$ and so on $$$k_{z,1}, k_{z,2}, ..., k_{z, r_z}$$$, where for each $$$i$$$, numbers $$$k_{i,1}, ..., k_{i, r_i}$$$ are remaining health points in consecutive enemy groups that are attacked without using all $$$n$$$ soldiers in between. So, we have $$$k_{i,1} + ... + k_{i, j} < n$$$ for every $$$j <= r_i$$$ and now we can proceed with the same idea of the editorial taking numbers:
And here is a counterexample for my solution:
It seems tests weren't strong enough as one of the 7 AC solutions for G fails this test.
So I think G is not a good problem.Lots of wrong lemmas of this problem are 'seems corrected and hard to hack'.We need a convincing lemma and natural proof.
Of course we meant $$$k_i$$$ after sorting, this will be clarified soon.
Maybe I wasn't clear. It has nothing to do with sorting, but with the restrictions imposed in the construction of the solution.
As stated in the editorial, these ' $$$m-1$$$ assumptions of type "some of our groups have total size $$$k_i$$$" ' should instead be $$$z$$$ assumptions (for each $$$i$$$ between $$$1$$$ and $$$z$$$, considering the same notation of my previous comment) of type:
"Some of our groups have total size $$$k_{i,1}$$$, some of our groups have total size $$$k_{i,2}$$$, ... , some of our groups have total size $$$k_{i,r_i}$$$, and all these $$$r_i$$$ sets of groups should be pairwise disjoint."
Then we can take the partial sums of the $$$k_{i,j}$$$ 's as in my previous comment, sort everything and get the distribution like in the editorial.
Anyway, nice problem, I really enjoyed it! :-)
Ok, you're right that there are cases when more than one group of enemy soldiers are destroyed on the same step; then we should modify the assumptions to yours or just directly replace the subsets of groups with prefixes.
I intentionally didn't dive into these details in the editorial because they can hide the main idea on one hand and because these cases are easy to cover once you get the main idea on the other hand. Probably I should mention them after the solution, though.
Why when i choose Solution(Rus) it shows Solution(Eng)
Still can't understand the C solution/proof !
and what's the meaning of the "parity of the matrix" ?
it means no. of 1's in matrix is even or odd like in this 01110 it is odd parity because number of 1's are 3.
Why can't the editorial be made easier to understand? Look at the number of people solving problems F,G and H, its hardly 20 people.
I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct?
You have to install the first k bottles, so you have to install the first bottle (the one with height 9) and, if you install it, you cannot install more than 4 bottles.
From problem D code, I am unable to understand the purpose of "t" array and how is it helping in calculate the result. Can anyone please help me in understanding the code or suggest a simpler solution?
If you understand everything upto the use of the array t in the tutorial's code, then this submission may help you.
What I did is that I kept the highest possible unique contribution of the rows (except the last row, it can contribute upto the entire length), sorted them (same as the tutorial). Then, for a specific query of length = r-l+1 (say), all I needed was the total contribution. And that is
(the summation of all the contributions that were $$$\leq$$$ length) + (rest of the elements in the "contributions" array and the last additional row will only contribute length amount).
Binary search on the contributions array (basically std::upper) and cumulative sum upto that position will give you the first term. I hope this helps. And I am also trying to figure out what the array t does in the tutorial. :(
Your solution was much easier to understand and was very helpful. Thanks.
I'm glad I could help.
i am unable to understand how did u found out the contribution of each elelment in range . Please help me understand. cout << summ[ind]+(sz-1-ind)*cov+cov summ[ind]= (max diffrence of s[ind]-s[0] among all rows) +(sz-1-ind)*cov . WHY?? +cov. WHY add cov at last??
By finding the differences of the elements (you need to sort them first) given in the problem.
i edited please look
for the last element which can contribute the entire length no matter what. ( cov means length in my code, just saying in case it confused you.)
quick question about C i just wrote a python code for make A to B but it doesn't work like i thought.
Here's a simple (?) general approach of solving H for $$$m$$$-tuples (instead of triples) in $$$O(n2^m + (m + k)2^{m + k})$$$. As explained above it suffices to solve the following problem: consider a set $$$t_1, \ldots, t_n$$$ of $$$m$$$-tuples of $$$k$$$-bit numbers. For a $$$k$$$-bit number $$$x$$$, say that the mask $$$y$$$ induced by $$$x$$$ for a tuple $$$t_i$$$ consists of all indices $$$j \in {0, \ldots, m - 1}$$$ such that $$$x$$$ and $$$t_{i, j}$$$ have an odd number of common bits. For each $$$k$$$-bit number $$$x$$$ and each mask $$$y$$$ of size $$$m$$$, we have to find how many tuples have mask $$$y$$$ induced by $$$x$$$.
Recall that multiplication of monomials in $$$\mathbb{Z}[x_0, \ldots, x_{k - 1}]$$$ with relations $$$x_i^2 = 1$$$ behaves the same way as xoring $$$k$$$-bit numbers. Further, WHT of an array $$$A = (a_0, \ldots, a_{2^k - 1})$$$ is the same as $$$k$$$-dimensional Fourier-transform of $$$P_A(x_0, \ldots, x_{k - 1}) = \sum_{i = 0}^{2^k - 1}a_i X(i)$$$, where $$$X(i)$$$ is the product of $$$x_j$$$ such that $$$j$$$-th bit is set in $$$i$$$. In simpler terms, we substitute all combinations $$$1$$$'s and $$$-1$$$'s into $$$P_A(\ldots)$$$ to obtain $$$2^k$$$ numbers; for the $$$j$$$-th number, the value of $$$x_i$$$ is $$$1$$$ if the $$$i$$$-th bit in $$$j$$$ is $$$0$$$, and $$$-1$$$ otherwise. Finally, recall that WHT is linear, and WHT of a product of two functions is the element-wise product of their WHT's (since WHT is basically FFT).
Consider a set of $$$k + m$$$ variables $$$x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}$$$. For a tuple $$$t_i = (t_{i, 0}, \ldots, t_{i, m - 1})$$$, consider a polynomial $$$Q_t(x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}) = \prod_{j = 0}^{m - 1}(1 + X(t_{i, j})y_j)$$$. What are the values of WHT of $$$Q_t$$$? Let's say that values of $$$x_i$$$ correspond to $$$k$$$ bits of a number $$$x$$$, and $$$y_j$$$ determine whether each index $$$j$$$ is included into the mask $$$y$$$. Then, one can observe that $$$1 + X(t_{i, j})y_j$$$ is equal to $$$2$$$ when $$$y_j$$$ matches the parity of the number of common bits of $$$x$$$ and $$$t_{i, j}$$$ (that is, $$$j$$$ is in the mask induced by $$$x$$$). Consequently, $$$Q(t)$$$ is equal to $$$2^m$$$ when $$$y$$$ is induced by $$$x$$$, and $$$0$$$ otherwise. By linearity, the WHT of
Unable to parse markup [type=CF_MATHJAX]
contains the exact values we wanted to obtain (after division by $$$2^m$$$).is this algorithmic round or International maths olympiad !
If there weren't problems as hard as these then people like Endagorion and tourist would finish all the problems in under 30 minutes, and where's the fun in that ?
would you translate following line into more easier english please? i trying to understand this line for like 30hours... but i cannot understand... 'the line starts from anoter perspective...'
Now come the queries. Given a fixed value of w, we need to quickly compute (∑n=1i=1min{di,w})+w. From another perspective, this equals the sum of value times the number of occurrences, namely (∑wk=0k⋅count(k))+(∑∞k=w+1w⋅count(k))+w, where count(k) denotes the number of times that integer k occurs in d1…n−1.
why did the contest problem's rating not show in the problemset
Problem H. How do I prove $$$x-y-z+w=p$$$?
I got it. Just needed to verify that every element after WHT looks like that. Basically, to prove that one needs to know that WHT is matrix-vector multiplication with matrix element $$$(i, j)$$$ being equal to $$$(-1)^{ij}$$$. After that, it is straightforward to show that $$$d$$$ is positive when $$$b, c$$$ have equal sign and negative otherwise ($$$(-1)^{ij}$$$ and $$$(-1)^{ik}$$$ have different signs if $$$j, k$$$ have different parity and then $$$(-1)^{i(j \oplus k)}$$$ is negative).
How to apply FFT in 1119E - Pavel and Triangles ? I saw FFT tag in this problem
Did you get the answer to this question? I also don't know how to do it :(
Another approach for C: Note that the problem can be restricted to only needing to perform the operation on a $$$2 \times 2$$$ submatrix, as any instance of the operation on bigger submatrices can be reduced to some number of the $$$2 \times 2$$$ operations. Proof: if we denote performing the operation on a $$$2 \times 2$$$ submatrix by the coordinates of its top left cell, performing all operations $$$(i, j)$$$ where $$$i \in [x, x+n-1)$$$ and $$$j \in [y, y+m-1)$$$ is equivalent to performing a single operation on submatrix of size $$$n \times m$$$ with top-left corner $$$(x, y)$$$.
With the problem thus reduced, an easy greedy solution emerges: Compare every position in the two grids in reading order. When encountering any position where $$$A$$$ and $$$B$$$ differ, perform the operation on $$$A$$$ with top-left corner at that position. If that's not possible because the position is on the last column or row, the answer is
No
.In problem E
Let's take 3 numbers i, j, k such that i < j < k.
Then why taking (i, k, k) and (j, j, j) is giving WA but taking (i, j, j) and (j, k, k) don't? 300iq
I came on a pilgrimage to the Holy Land. Please don't let IOI have problems with output only.
I came on a pilgrimage to the Holy Land. Please let me have a girlfriend who does problem solving.
Hmmm, problem F seems familiar ...
Is it just me, or the E problem is too easy to be E. I feel its more like Div2 B.