Thanks all participants. I hope, you liked problems.
A — Brain's photos
We need to do exactly what is written in the task: to consider all of the characters, and, if there is at least one of the set {C, M, Y} print "#Color" else — "#Black&White"
B — Bakery
Note that it makes no sense to choose the city for bakeries and the city with the warehouse so that had more than one way between them, as every road increases the distance over which you have to pay.
So, the problem reduces to the following: select two neighboring cities so that one is a warehouse, and in the other & mdash; no. For doing this, simply iterate through all the city with the warehouse, among the neighbors of each town without looking for a warehouse and update the answer. If there is such a pair of cities, print -1.
C — Pythagorean triples
D — Persistence bookcase
Solution №1:
Note that the data is delivered all at once (offline). Then we can build a tree of versions, then run out of the DFS root and honestly handle each request in the transition from the top to the top.
Solution №2:
Note that Alina uses operations that relate to the columns. We can make an array of versions of the shelves, and each version of the cabinet to provide an array of indices and the corresponding shelves to store it explicitly. Then, for the operation, such as changing wardrobe, shelves, a new version which has been changed, this version of the index is recorded on the same shelf position. This approach eliminates the decision on the use of extra memory for storing unnecessary information.
E — Garlands
Let us handle each request as follows:
Let's go for a "frame" request and remember lamp garlands, which lies on the boundary. Then, in order to find concrete garland, what part of it lies within the query, sum all of its segments, the ends of it are lamps that lie on the "frame".
Also, do not forget the garland wich lies entirely within the request. Each garland at the beginning we find the extreme points, and to check whether it lies entirely within the query, check whether the lie inside its extreme points.
Can you please give the tutorial for Problem C — Pythagorean Triples?
n = 1, 2: There are no solutions (easy to prove)
n is even:
n is odd:
Do you have a proof for the formula ?
You can prove it by induction.. Check the base case by considering the case that sum of two sides of triangle is greater than the third side. This will give you n>1 for odd 'n' and n>2 for even 'n'.
You can directly substitute and check using (a + b)2 = a2 + b2 + 2ab formula.
No need of induction.
For instance
how can i come with such a formula if i didn't know it before ?
Actually you can figure it out easily. You see that n²=m²-k²=(m-k)×(m+k), so you need to find a way to present n² as a×b with (a-b) is even. You will always find a and b if n is odd and larger than 1, which is 1 and n². If n is even and n is larger than 2 then how about 2 and n²/2. Easy as that, huh?
http://mirror.codeforces.com/blog/entry/46681 explains it.
The second formula for odd numbers is easier to see in the following form —
(k)^2 + (2k + 1) = (k + 1)^2
If n is odd, it's square is also odd ... so** n^2 = 2k + 1**, and the equation is re-written in terms of n.
If n is even ... i.e.** n = 2m**, then** n^2** is also even ... so n^2 = 4k .. a multiple of 4. Using that observation,
then
(k — 1)^2 + (4k) = (k + 1)^2
Again the equation is re-written in terms of** n**.
consider a^2 = b^2 + c^2 (PT)
now we are given the cathetus (any of the two sides other than hypotenuse) let c = n then -> n^2 = (a-b)*(a*b) [a^2 — b^2]
check yourself that either (a-b) and (a+b) both are even else both are odd
from the above eqn (a-b) and (a+b) are factors of n^2
simplest -> if n is odd let (a-b)=1 and (a+b)=n^2
if n is even let (a-b)=2 and (a+b)=n^2/2
solve these and u will get values for a and b :) but for n<=2 no ans exists so print -1 :)
Brilliant explanation .
why did you assume that if n is odd you put a-b =1 why 1 not any odd number .and the same if n is even ?
I said that's the simplest.... Plus u need a-b to be a factor of n^2 and 1 is a factor of every number that's why a-b=1 same goes if n^2 is even
Your_dad, actually we are given either cathetus or hypotenuse. Is there always exist a Pythagorean triple in which given n represent cathetus? How can we prove that?
Let n = 2k where k > 1. Consider the Pythagorean triple obtained by scaling (3, 4, 5) by .
Now suppose n has some odd prime factor. Every odd prime p is the difference of two consecutive squares. Let x be such that (x + 1)2 - x2 = 2x + 1 = p. Thus, (p, 2x(x + 1), x2 + (x + 1)2) is a Pythagorean triple. Scale it by and you obtain a triple that has n as a cathetus.
Thus, every integer n > 2 is a cathetus of at least one right triangle.
How to prove that for n <= 10^9 and n is a cathetus, there exists c <= 10^18 where n^2 + x^2 = c^2?
For the case of 2k, it's trivial, so suppose n has an odd prime factor p = 2x + 1 as in my previous comment. We can show that my scaled right triangle will be small enough for the problem:
As for the hypotenuse:
Note that in the last step, the reason $x+2 \leq p$ is because x ≥ 1 since p is at least 3.
[http://www.codeforces.com/blog/entry/46681] try this:P
Hi
You could refer this explanation. :D
Problem D solution no.1
Does that mean if there's op is '4', then the tree contains a cycle?
No. in the case of 4 x , you don't attach the node i-1 to the node x , you attach the node i to x.( i will be the another children for x )
That's awesome
Nice contest. Can you elaborate more the second solution of D ?
Note that for operation 1~3 we will only change one line at a time. So there are at most 10^5 different lines. We can use array/bitset to maintain these lines. Lets call this array/bitset
lines[]
. We also need to know after each operation, where these lines are stored. So we need a new arrayposition[][]
.position[op][i]
means after the op-th operation, the status of the i-th line is stored inlines[position[op][i]]
.When we use operation 1~3, we just add a new line to
lines[]
. And after each operation, we will need to updateposition[][]
. If we use operation 1~3, onlyposition[op][i]
will change to the newest added line. If we use operation 4, we just need to iterate through all lines, and letposition[op][i] = position[x][i]
.You can also see my submission for details (I use a bitset to maintain
lines[]
) 20015649goto is not good,you can use continue instead
I guess we can just use string here instead of bitset. Bitset has a little more overhead.
When using string, we could add another field inverted that basically keep track of # times operation 3 applied % 2. inverted == 1 means every bits in the string are inverted, otherwise not.
Your complexity is O(n*q). This means O(10^8) worst case. How can this fit in 2 seconds?
I'm not quite sure about the speed of the judge server, but the following code can be executed within 1 second on my laptop (just a normal laptop, not a very good one).
So I think O(10^8) can be executed within 2 seconds.
I guess if he use
memcpy
instead of coping by loop it would be faster. Despite the fact that memcpy also loops it's so much faster.I did as you told, but I've got TL — 20157774
Problem D. also has an online persistant segment tree solution. 19996544
why do you do this lz = lz^lazy; in update1 . ?
Another solution to problem E.
Note that the data is delivered all at once (offline). We can precalculate the sum of the happiness value of each garland in each rectangle given in the "ASK" operation (using two-dimentional Binary Indexed Tree/Fenwick Tree). Then for every "ASK" operation we just need to enumerate all the garland and see if it is on. If the garland is on we can add the precalculated value to the answer.
The time complexity is O(nm(log(2000))^2). You can see my submission for detail 20021444
I know this is your first editorial but I think editorials should be more detailed, editorials should be 'editorials' if that makes any sense. Thanks for the round.
Can anyone add the solution to the second problem? My code is http://ideone.com/fOzg7O. Please tell me where I am wrong.
Your solution gives WA, because you create arrays
u1[m], v1[m], l1[m]
of sizem
. But following cycle can add2m
edges. So this solution works correctly.Now we have TLE. That is because your solution works at least in O(m*k). You can see 19989181 — my contest submission, which works in O(m + k).
How can there be 2m edges?
In cycles for an edge
(u[i], v[i])
if both citiesu[i]
andv[i]
have flour storage, then the edge appended twice.There is another solution to C , which gives you all pythagorean triplets in O( 500* sqrt(side ) ) . 20008793
Would you please explain a little ...
I think order of your solution should be more because there is another loop inside a sqrt(side) loop ... isn't it ?!
Well , you are quite correct , I tried to approximate the number of factors of a 9 digit number and https://en.wikipedia.org/wiki/Highly_composite_number and in rare cases number of factors go beyond 500 but since it was sqrt( 10^9 ) * 500 so it worked.
In O() we don't use a number... it should be a variable or something ... for example max_factors or something. ....
I know that buddy , its done to make life simpler :)
Can someone please explain the editorial solution of E? I could not understand it properly. What is 'concrete garland' and 'extreme point'? How are we handling 'garland which lies entirely within the request'?
There are only 2000 ASK queries. For each ask query let us precompute for each garland the sum it will contribute if this garland was on. This can be done by a 2-D BIT. This will take time equal to O(ASKQ * K * logN * logM).
Then for each switch query just keep an array which will denote whether each garland is currently on or off. For each ask query, iterate over all garlands, if it is on, add to the answer the previously computed sum.
I understood this one. But is this the one explained in the editorial? I don't think so. Please correct me if I'm wrong. :)
Its almost like he doesn't want us to understand what he wrote facepalm
The solution in editorial uses prefix sums of values in garland to find answer to a query. Whenever a garland enters the frame, subtract prefix sum from answer, and whenever a garland leaves the frame, add prefix sum to answer. Also, for a garland ending inside the frame, add the prefix sum of its end to the answer. Do all these operations only for "on" garlands.
There will be O(n+m) such entries and exits, hence time complexity: O(2000 * (n + m))
In solution for B I believe that this
If there is such a pair of cities, print -1.
should be rewritten to..if there is NO such pair..
Someone please explain the editorial of E
In problem E. there are at max 2000 ASK queries. And k<=2000. So for each ASK query basically we are calculating our answer separately for each garland. Now we arrive at two cases :
When the entire garland is in our rectangle (the one in query) This can be checked in O(1) for all the garlands by storing the extreme points . That is storing the topmost, leftmost,rightmost, bottommost. If all these points are inside the boundary, then we simply add the sum of all the values in garland to our answer.
If some part of the garland is inside and rest is out, then at least one of its lighthouse must be present on the boundary. While taking the input, for each garland we can number all the lightbulbs in the order of input (Consecutive in the grid), and we can make an array of pair of integers where for each cell we store the garland number and the index of the lighthouse. Now we need to iterate through the four boundaries and we need to store the indeces where some garland exits or enters the rectangle. This can be easily done. Refer to my implementation. Now with this information we need to calculate the sum of lightbulbs in the rectangle, which can be done by storing the prefix sums for each garland.
Time Complexity : O (q* (n+m+klogk)) where q<=2000 Here is my implementation : 20021555
Got it!
You are also sorting the positions for each garland.That would bring another logn.
Yes it will. Totally forgot about it.Thanks
Since the maximum length of a garland is $$$2000$$$, we can use counting sort instead of ordinary sort and bring the complexity to $$$O(ASK * (n + m + k))$$$.
Also, when checking for garlands that lie completely inside, we don't need to check extreme points (minX, maxX, ...) as the editorial said. Instead, we can take any point of the garland and check if it lies inside the rectangle. Since we have checked all border cells, if any point of the garland lies inside the rectangle, then it has to lie totally inside. We can conveniently check the last point, since we need to check it anyways.
This is my implementation 126593034. Sadly, in this problem, solutions with $$$log$$$ are indistinguishable from linear ones, and even $$$log^2$$$ ones can pass.
What's the time complexity of problem E.
Can you explain about problem D using dfs
Let's construct graph, where every vertex is state of our bookcase. Initialy we have one vertex corresponding to the initial state of bookcase. Let's process all queries. We will create new vertex every time we find queries of type 1, 2, 3. Also we make new edge from current vertex to the new one. On queries of type 4 we just change our current state(without changing the graph). Then we travel across graph with dfs and apply every change of bookcase written on the edge.
Sorry for my english. Here is the code. I hope it will help.
Worst editorial ever !!
Why there isn't any editorial for C ?!
There is a nice page explaining it, see here.
Thanks for the great round.
Would like to know if anyone could do O(q) or anything better than O(qm) online solution of problem D?
Yes there is an online O(qlogn) solution using persistant segment tree. 19996544
Thanks for the tips!
I found a pretty good explanation of persistent segment tree here for anyone might be interested. If you know this the solution could be super straightforward.
Note that it's actually a simplified persistency, compare to real persistency like partial persistency and full persistency. There is a pretty good youtube video course that would walk you guys through those ideas if you are interested, see here.
how did you handle range updates?
Lazy propogation.
yeah i tried lazy propagation but i am stuck in a point.Point updates are clear like
Point updates for a particular query means that we have to change only log(n) nodes in path from root to leaf so for q queries space complexity would be n+qlog(n) but for the case of range updates i would keep a lazy value at each node but the problem i am facing is that the node to be updated would be representing some range so to change it would mean recreating the whole structure beneath it which be be too much costly considering the fact that there might be more range updates in the queries.Can someone suggest how to implement this?
I implement lazy propagation like this in normal segment tree first when i need to update a range i update the node representing the node and if it is not a leaf node i pass the lazy update to its two children but here if i just create a new node and pass the lazy value down this will contradict with some other k used before.
In Problem E, there is another offline solution which uses persistent segment tree. Note that 2d range query can be done in O(log n) with a persistent segment tree. So for each garlands, add its lightbulbs' weights to their coordinates to the persistent segment tree. Now for each ASK queries, we can determine how much the garland will affect to the answer by summing the rectangle area. After calculating them, we follow the queries again, turn on/off garlands, and calculate the answer. Time complexity is O(q+k(len log len + len log 2000 + s log 2000)+ks). (s is the number of ASK queries)
http://mirror.codeforces.com/contest/707/submission/20108841
Can you help me regarding range updates in persistent segment tree referring to my above comment?
I'm having difficulties with question B — Bakery. Can someone help me with what i'm doing wrong
https://mirror.codeforces.com/contest/707/submission/78816637
-->u did'nt took the visited array to mark the storage locations coz they woud'nt be the part of your ans ! u can refer this (https://mirror.codeforces.com/contest/707/submission/79922973)