In this problem you should guess that exists only three valid groups of three
1) 1, 2, 4
2) 1, 2, 6
3) 1, 3, 6
(You can see that integers 5 and 7 are bad).
So, we will greedy take these groups of three. If some integers will be not used, the answer is -1. In other case, print found answer.
The problem is solved by greedy algorithm. We will pass the note only in correct direction. Also, if we can pass the note at the current moment of time, we do it. In other case, we will hold it and don't give it to neighbors (we can make this action at any moment of time). Obviously this algorithm is correct. You should only implement it carefully.
In the problem you should carefully get formula. The optimal solution put marbles by two in a row. And then put one marble upon others if it possible. The most difficulties were to deal with this last phase.
In comments to the post were given formulas how to put the last marble (exactly in the middle). And there was a good beautiful illustration, which describes the situation.
In the problem you can count number of correct puzzles or substract number of incorrect puzzles from number of all puzzles. In any case you should count DP, where the state is (j, mask) — j — number of the last full column, mask — mask of the last column. This problem is equivalent to the well known problem about domino tiling or the problem about parquet.
To get the solution of the whole problem I did the following. I try to attach one domino to each of 4 directions, then paint all three cells in black and count the number of correct puzzles. But in this case you will count some solutions several number of times. So you need to use inclusion exclusion formula for these 4 directions.
The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into sqrt(m) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest red node using bfs. To answer the query we should update this value by shortest distances to red nodes in current block.
The solution becomes simple. Every sqrt(m) queries we make simple bfs and for every node v WE calculate value d[v] — the shortest distance to some red node from node v. Then to answer the query of type 2 you should calculate min(d[v], dist(v, u)), where u — every red node, which becomes red in current block of length sqrt(m).
Distance between two nodes dist(u, v) can be got using preprocessing for lca.
Can someone please explain problem D in more detail, I am not able to understand anything from what is posted.
Thanks
Solution is simple. let me explain it with a examples:
suppose we have filled all the empty blocks from column 0....i-1 and on ith column we have filled some of the empty blocks which is stored using mask 0,1,...,7
suppose if mask is currently 0 and i=2, so configuration could be something like this.
blocks with A are already filled.
now we have two options, we might use some vertical block or not:
now we are almost ready with solution and need to check while putting block if that box was empty earlier and which we put block near 0, we need to note this also.
I think, you should be able to understand my code now.
Could you please post the link to your solution.
I got the algorithm but I am lacking clarity over some points like considering the state (i,3), How does one keep track of whether a single vertical block was placed or 2 horizontal blocks covering the squares were placed.
Anyways, thanks for your explanation.
solution: http://codeforces.net/contest/342/submission/4424666
it does not matter whether it was vertical block or 2 horizontal block. (i,3) tells that all the blocks in first i-1 columns are filled and in this column there is only last row left to be filled.
.d.
Assume that you have the distances from vertex with index 1 to every vertex u in a vector d[].
Define lca(x, y) the lowest common ancestor for vertex x and y. You must find out the distance from v to u.
The result is d[u] + d[v] — 2 * lca(u, v) because you add twice the distance from vertex 1 to lca(u, v) (that's where the 2 roads intersects). You can draw a tree on a paper and and work with some examples, it will be clearer.
Could you please tell me the complexity of the Problem E?
Here is my solution: http://codeforces.net/contest/342/submission/4509629 The complexity seems to be O((n+m)*sqrt(m)). But it still gets TLE.
O(n*sqrt(m)*log(n))
\begin{equation}m \cdot\sqrt{m}\cdot\log_2{(n)}\end{equation}
You can precalculate the lca of nodes in Mlogn
In E problem , there isn't any boundary case like chain. Then O(N*N) solution can get AC.
did u code in cpp?
I don’t even remember what I had for dinner last night and you’re here asking me about a code I wrote 6 years ago. That’s like a lot of months :)
That can be answered with what language u used to code with... But anyway you have a point... and I got the ans after stalking your profile... Thanks
Any online solutions for problem E ? Or different solutions to E?
My solution uses Heavy-light decomposition and segment trees. Complexity is O(N log^2 N). http://codeforces.net/contest/342/submission/6999318
Could you explain your idea ?
very good. It was really helpful.
We can achieve O(NlogN) if we store each "heavy chains" in separate segment trees. For each operation, all queries and updates, except the beginning one, are on the whole chain, and only takes O(1). Therefore, each operation takes O(logN)*O(1)+O(1)*O(logN)=O(logN)
My solution (it doesn't run faster in practice though)
in problem E, the complexity is O(N * sqrtN * logN).... logN because of the LCA part it doesn't pass the time
how did you handle this !!?
You can precalculate the lca of nodes in Mlogn
oh 7 years to get an answer...that was really too fast! :D
Deleted
For problem 342E - Xenia and Tree, I came across a centroid decomposition solution 23224047. I have gone through the solution, but I am not able to convince myself about the correctness of the algorithm and the reason as to why query method is correct(or works). Please help!
PS: HolkinPV, can you please help?
I'm a bit late but the solution is explained here.
How to solve Div1,C if we have to return the maximum distance to any red node instead of min distance...?
"Distance between two nodes dist(u, v) can be got using preprocessing for lca." - Xenia and Tree
Can anyone explain me how to do it?
Notice that
dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, l)
, where l is the LCA of u and v1) Use a DFS to find the distance from node 1 (the root) to every other node. Let
rootDist[n]
by the distance from node 1 to node n. The DFS should also find the parent of each node, and the depth of each node from the root. Letparent[n]
be the parent of node n anddepth[n]
be the depth of node n.Example DFS code:
2) Build a sparse table.
sparse[u][i]
stores the 2**i-th parent of u, or-1
if that parent doesn't exist. Note thatsparse[u][0] = parent[n]
. The sparse table can be built by:3) To query the lca of u and v, we do the following steps:
Here is the code for the query:
And finally, to put it all together, to query distance
Building the LCA sparse table takes
O(n log n)
time while querying takesO(log n)
time(I wrote this from memory; please tell me if there are any mistakes or if any part is confusing)
Source/Additional reading
Thanks for your help. You explained very well.
How to do this - Calculate minimum distances from every node to the closest red node using bfs.
Store all nodes which are currently red in a vector redlist. Create an queue bfslist for bfs, and create a array
dist[v] = Distance from v to the nearest red node, 0 if v is itself red
and initialize an empty queue. Now for all red vertices v, letdist[v] = 0
and push all the neighbours u of the red vertices which are not red into this queue, and for all such u, letdist[u] = 1, isdiscovered[u] = 1
. Now it's just regular bfs: while the queue is nonempty, pop the first elementw
from the queue, and add all the neighboursy
ofw
not already discovered to the queue, and letdist[y] = dist[w] +1, isdiscovered[y] = 1
. Here's a code implementing it:Hi, can anyone please help me debug this code for Problem E.
https://codeforces.net/contest/342/submission/39819558
It has been days and I've not been able to find the error.
I used 'Centroid Decomposition'.
Thanks in Advance!
In problem Div2 E, can someone share the code implementing the sqrt optimization trick. Are there any resources for this technique ? In what all cases can this technique be applied ?
https://pastebin.com/cCYBLvjs
https://codeforces.net/contest/342/submission/75643716
For Div2 C, what comments?
Can somebody help me with problems 342E. Here's my source code: https://codeforces.net/problemset/submission/342/157723527
I still don't know why I got TLE. Thanks so much!!
...