472A - Уроки дизайна задач: учимся у математики
One way to solve this is by bruteforce: there are O(n) different ways to decomose n as sum of two number. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation.
And another way is try to prove this theorem. The prove is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number).
472B - Уроки дизайна задач: учимся у жизни
This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k]-1) + ...) .
It is a bit tricky to prove the correctness of greedy, since people can get off the elevator and take it again. We can give a lower bound of the answer by flow analysis: between floor i and floor i+1, there must be no more than (# of f[i] >= i+1) / k times the elevator goes up between these 2 floors, and then there be same number of times goes down. We can find this lower bound matches the answer by above greedy algorithm, so it means the greedy algorithm gives an optimal answer.
472C - Уроки дизайна задач: недетеминированность
This one laso can be solved by greedy, let's think in this way: let pick one with smallest handle, then we let him/her use min(firstName, secondName) as handle. And go for the next one (2nd mallest handle), now he/she must choose a handle greater than handle of previous person, and if both meet this requirement, he/she can pick a small one.
This time the correctness of this greedy solution can be proved by exchange argument.
Note that if we change the goal of this problem: ask number of different permutations they can get, then it will be very hard. (I tried it for hours but can't solve.)
472D - Уроки дизайна задач: обратные задачи
Let's think it in the following way: for the minimal length edge, it must belong the the tree, ..., for the k-th minimal length edge(a, b), if there is already an path between a-b, then it can not be an edge of tree anymore, otherwise it must be edge of tree, why? Because otherwise there must be a path from a to b in the tree, that means a and b can be connected by edges with less length, but a and b is not connected.
So this Kruskal style analysis gives us this theorem: if there is an answer, then the answer must be the MST of that graph. (You can also guess this theorem and try to prove it.)
You can solve MST in O(n^2 log n), and then there are many way to check distance between notes on tree: you can just simply do dfs or bfs from each node, it can run in O(n^2). Or if you have pre-coded LCA algorithm, it can run in O(n^2 log n).
472E - Уроки дизайна задач: учимся у игр
First let's solve some special cases:
If the initial board and the target board contains different orbs, then there can't be a solution.
If n = 1 (or m = 1), then we can try all O(m^2) (or O(n^2)) possible moves.
And for the other cases, there always have solution. We first hold the orb with number target[1][1] in initial board. Then we want to move other orbs to their position.
So let's come up with a process to move orb from (a, b) to (c, d): it must be some continue path from (a, b) to (c, d), so we want to build a single move: it will move an orb from (a, b) to an adjacent cell (c, d). How to do that? We can move our touching orb to (c, d) first, and then move to (a, b). But there are some concerns: in this move, the touching orb shouldn't pass any already-done cells, and it shouldn't pass (a, b) when we get to (c, d).
That means we need a good order to move orbs. We can do it in this way: first, as long as there are more than 2 rows, we move the orbs to last row (from left to right or right to left). And then it must be 2xm boards: we do it column by column from right to left. We can find that in this order, there always exist paths for our touching orb to get (c, d).
472F - Уроки дизайна задач: меняем цель задачи
You need to know some knowledge about linear algebra and notice the operation of xor on 32 bit integers equals to + operation in a 32 dimension linear space. If you don't know, you should learn it from the editorial of similar tasks, for example, Topcoder SRM 557 Div1-Hard.
We need to know some basic properties of our operation:
we can swap two number a and b by: a^=b, b^=a, a^=b.
This operation is inversible, the inverse is itself.
By property 1 we can do the Gaussian elimination of each set of vectors.
By property 2 we can use this way to build an answer: use some operation to make A[] into a base (linear independent vectors that the span will be A[]), then transfer it into a base of B[], then use the inverse of Gaussian elimination to recover B[].
So now we have two bases: {a1, a2, ..., ax} and {b1, b2, ..., by}. If there exists some bi such that it can't be expressed as a linear combination of {a1, a2, ..., ax}, the solution can't exists.
Otherwise there always exists a solution: first we build b1 and put it in the first position. Suppose b1 = a2 ^ a3 ^ a8, then we swap any of them, say, a2 into position one, and then xor it with a3 and a8, then we get b1. Note that after this operation {a1, a2, ..., ax} will remain a base. And we need to ensure we don't erase already-done numbers in a.
472G - Уроки дизайна задач: увеличиваем ограничения
Let's start with a simpler task: we have string A and B (|A|, |B| <= n), we have q queries and each query we ask the Hamming distance between A and a substring of B with length equals to |A|.
How to solve this? We need to notice compute A with different offset of B is similar to the computation of convolution, so it can be done by FFT.
We use +1 to replace '1' and we use -1 to replace '0', and then we do the convolution of A and reverse B. We can extract the answer of all possible query of "the Hamming distance between A and a substring of B with length equals to |A|."!
Then let's come back to our problem, how to use this way to make a faster solution? We can use a way like sqrt decompose: we divide A into L blocks, for each block, we compute the convolution of this part with B, it will takes O(n*L*logn). And for each query, we can use the pre-calculated results to speedup (if a whole block contains in the query, we can compute it in O(1)). So each query needs no more than O(L) operation.
If n = q then this solution can run in O((n*logn) ^ 1.5). But in practice it has some issues: for example, we can use bit operation to speedup like __builtin_popcount(). I tried to set constraints to fail solution with only bit optimization, but seems I failed: I apologies to allow this kind of solutions passed. (I used __builtin_popcount() to test such solution, but in fact cnt[x<<16] + cnt[x>>16] is much faster than the builtin fucnion)
(Also, you can use your knowledge about real world computers to solve this task: http://codeforces.me/contest/472/submission/8014415)
Thanks for fast editorial!
D can be solved in O(N^2). Prim can solve MST in O(N^2) if we don't use priority queue:)
Oh, yes, Gerald told me that some days before. :)
Thank you for the interesting problems! I like D problem the best. (I solved it by a different way from editorial.) I have created Puzzle and Dragon solver few years ago but I took so many time to solve E problem.=( I like your problems, so I'm looking forward to a new problem!:D
I'm glad to hear you love my tasks!
What is the algorithm of your Puzzle and Dragon solver? Can it solves task E or it only works for the 5x6 grids?
It may be able to solve task E by some modification (I write a solution for E problem from empty source code).
Because there is time limit in the game, I tried to minimize the number of swaps. (I just write a trivial search.) I uploaded a movie of the solver.
Oh, that video looks so crazy! :)
I used to want to write it but it seems not that easy.
How did you get the pattern on your phone? (use Computer Vision or you can access the game data from memory?) And how do you do the clicks on your phone?
I got the pattern from a screenshot and I operated by using ADB (Android Debug Bridge).
In which way you can use Prim's algorithm without priority queue?
find minimal element each time in O(n)
Priority queue is used to find the next vertex in Prim. But you can find the next vertex in O(N) straightforwardly. (Note that you'll find "the next vertex" N times.)
It can be solved in O(n^2) even without using Prim.
Firstly, lets make the 0 vertex as a root and add it to the tree. After that, sort the first row of input (weights of edges connected with the 0 vertex) and lets add vertices to our tree in this order. For each vertex we will save a vector of it's children. Suppose we are trying now to add vertex "v_to_add". We will have a function
add_to_tree(root, v_to_add)(root is an initial state). When we trying to add new vertex we need to check for all our chlidren ifw[cur_v][v_to_add] = w[cur_v][its_child] - w[cur_v][its_child]. If it happens to any child of current vertex, then we need toadd_to_tree(its_child, v_to_add). (Of coursev_to_addmust be a descendant ofits_childbecause of its distance tocur_vis a distance toits_child+ edge fromits_childtocur_v). If no suchits_childfound we have to connectcur_vandv_to_add(sov_to_addbecomes a child ofcur_v).After that we are checking distances between all vertices. If they are same as given, then "YES". Otherwise "NO".
Prob A, you say that:
n is 25
ans = 8 17
isn't 17 prime number?
But 25 is not an even number. You should output 9, n-9 which is 9, 16.
got it. I confused sorry..
Why we used sqrt decomposition in G? Isn't it possible to decompose out interval on base intervals, like it is done in every segment tree? UPD: That thing here proved to be wrong.
If you want to build a segment tree it will have O(n) nodes, and that means O(n) times FFT, that will be slow.
But I will have n nodes where I want to do 1x1 multiplication, n/2 nodes where I want to do 2x2 multiplication etc. which will result in O(nlog2n)
Can you describe your algorithm in detail? :)
Why you can do 2x2 multiplication instead of 2xn?
Umm... Sorry, I was obviosuly wrong and you were right ; p.
Problems were very interesting.Thank you!![user:cgy4ever] .
Can anybody explain the solution for problem D? I am unable to understand the editorial.
Another one solution for problem D. One can make vertex №0 root of the tree. Then you can restore for each vertex path to the root (u is ancestor of v if dist[v][0] = dist[u][v] + dist[u][0]) and restore the tree from this information. Then one should use n dfs to check if the matrix is correct.
Solution: 8007468
I will be thank full to you if could help me understand why one needs to do n DFS to check if the matrix is correct? or
Why is 1 DFS not enough for checking the correctness of the matrix??
Well, one DFS is actually enough if you will check all distances between vertices using LCA or something like that. But I think, it is harder than make n DFS.
Can you please provide solution for D implemented in java? -_-
Your mistake is probably implementing Prim's algorithm in O(N^2 * log(N)) or using Kruskal's algorithm, they might be too hard for Java.
P.S. https://sites.google.com/site/indy256/algo/mst_prim_simple
no, my mistake was in choosing java 7. Resent with java 8 and received AC. Just shocked.
Here on Codeforces different Java versions are faster in different problems
You may use filter by language here
Actually it's not necessary to use assembly hacks to solve G.. bit hacks are enough.. Brute force bit hack is nm/32, which is not enough.. But in fact we can use offline algorithm to optimize it to n^2/32.. which is enough to pass with O2...
Well, online
works too
Well, it's a pity that there's such solution for a cool problem, but anyway I'm glad to have personal record:)
D:<
Problems were very interesting.Thank you!!!!!!!!!!!!!!!!
Just changed cin/cout to scanf/printf: AC (after contest) 8015832 and TLE 8010736 (during contest). cgy4ever why you didn't warn about large input? T_T why?
read this and you don't need scanf on CF
I have that
ios_base::sync_with_stdio(false);in my template, but it is commented and at the bottom. Actually whenever I see N < 106 I use scanf/printf. But this time I didn't notice it T_TAnyway thank you.
I think that scanfs and printf are a bit faster than cins and couts even with iosync thing. Isn't that right? (Am I not starting a flame war?)
In C++11 it isn't right, especially if one use
sync_with_stdio(0).well, I don't see reason why c++11 would change anything
Just an observation. Maybe it is compiler-depend. But at least on acm.timus.ru it was almost always faster.
Also one can look at this benchmarks, but they don't really have a lot of common with C++11.
If we don't consider doubles (reading them is very slow using con on CF) they may be different, but not really significantly. I believe today I saw a comment where one said that after changing scanf->cin he got TL->AC (but that was really near TL)
Two years ago I measured that iostreams (with
sync_with_stdio(false)) was faster on reading/writingints thanscanf/printfon MinGW.I spend the same :'-( , my solution of problem D obtained TLE without "ios_base::sync_with_stdio(false);" cgy4ever why? TT_TT
Anyway cgy4ever thanks for the problems, they were very interesting.
I also did the same mistake. I know its my fault. But the thing i love about codeforces is that its not as I/O extensive like other online judges. I hate this kind of i/o extensive problem. And I think it should be advised in the problem to use faster i/o in this kind of problems so that nobody gets it unsolved for only I/O latency.
Excuse me, but where the heck are floors indexed from 1 :P? I definitely prefer indexing from 1 in general, but floors are always indexed from 0! That made me solving B 2 times longer than it should :P.
Probably it depends on country/culture. They are numbered from 1 everywhere I know in Russia
They are numbered from 1 in China. In US (at least here in Los Angeles) they are showed as G (for ground floor), but it equals to 1 (because the next floor will be 2).
For prob D, I just rearranged the matrix, and rebuild the tree in O(N^2) without using MST or any other algorithm. Here is my solution http://codeforces.me/contest/472/submission/8013128
Sad story with problem D: These 2 solutions are equal except the array w[][]. Having an int array gives AC, but long gives TLE.
But anyway, thank you for the contest so much! I really enjoyed solving the problems! :)
My solution for D problem:
This algorithm may be O(N^2). source code
in problem D tutorial, in the last line you said: ** if you have pre-coded LCA algorithm, it can run in O(n^2 log n).**
shouldn't that be O(n*log n) when using LCA ??
It depends on the way one codes LCA. If you are using the Euler Tour + RMQ method then it's O(n^2) (because RMQ is O(nlogn) and each query is O(1)). On the other hand if you prefer any other O(logn) per query method, then it will be O(n^2logn)
Can anyone help me get the idea of LCA in problem D ?
Another one for D:
Let's pick some vertex V. Then let's find such vertex U, that dist(V, U) is max for all U. Found U is the leaf of the tree. Now let's find suck vertex T, that dist(U, T) is min for all T <> U. It means that in our tree there is an edge TU. Now let's delete U from the tree and continue algorithm from vertex T. We need O(n2) time to do such manipulations. And now in the same O(n2) time we're checking if given distances equals to distances in built tree.
This approach is more intuitive and easier to implement.
Time limit is too tight for N^2logN solution of problem D . My TLE code in the contest got accepted just after changing long long int to int. I think the time limit should have been increased to 3 or 4 seconds. I don't think there is a fear of getting a N^3 solution accepted at that time limit as N=2000.
In fact Gerald has a N^3 solution that can pass most cases even if N=2000, so I'm afraid reduce N into 1000 may not be a good decision.
Thanks a lot for this round. Nice problems and a lot of fun :)
Problem D .. Why am I getting a WA on test 9 . Also how do I see the full testcase ?
You cannot see the full test case as far as i know
Same here... I wonder what it is.
I am not able to understand F. What does it mean "the operation of xor on 32 bit integers equals to + operation in a 32 dimension linear space"? And what is FFT? Great competition, the first four tasks were pretty nice, the last two tasks seems impossible for me ):
Here's another idea for Problem C.
We can make name-"person id" pairs,and sort those pairs regarding the name as keyword.
Now the "peoson id" form a number sequence,all we need to do next is check whether the given n-length number sequence is a subsequence which we made or not.
Take the sample 1 as example:
After sorting,we can get a sequence:
3 3 1 1 2 2
so ,we can't find a subsequence 1 2 3 in it(answer is NO),but we can find a subsequence 3 1 2 in it(answer is YES).
Here's my solution:8001545
Good problems, enjoy the problem F and G. It seems that you like the problem of linear space and make some problems of it. I think I can solve it next time you make such problem. By the way, my solution about D is O(n^2logn) but got tle, feel a little sad..
"By property 2 we can use this way to build an answer: use some operation to make A[] into a base (linear independent vectors that the span will be A[]), then transfer it into a base of B[], then use the inverse of Gaussian elimination to recover B[]."
I did not get two parts here. How to go from one base to another (i.e. from A to B) and how to do inverse of Gaussian Elimination ? Please help !!
To go from one base to another : Note that one can always form a base vector such that MSB of each element of base vector is 1 only in that element. Now suppose you want to go to b_i in basis(y), then it can be reached iff xor of all elements e in basis(x) is equal to b_i, where e is such that MSB of e is 1 in b_i.
Inverse gaussian elimination : If a sequence of xor operations is performed on array x to reach basis(x), then performing these operations in reverse order on basis(x) will give back array x. So, in the original problem, once we reach basis(y) from array x, we could perform in reverse order, the operations done on y to reach basis(y).Hence, giving array y from array x.
Nice implementation by GateOne http://codeforces.me/contest/472/submission/8020297
@cgy4ever: "(I used __builtin_popcount() to test such solution, but in fact cnt[x<<16] + cnt[x>>16] is much faster than the builtin fucnion)" what is cnt here?
cnt[x] = number of '1's in binary representation of x. So cnt[x<<16] + cnt[x>>16] is the number of '1's in x if x is an int.
“So the answer is 2 * (f[n] + f[n-k] + f[n-2k] + ...) — n.” It seems that the last "n" means
n%k? 2*(n/k+1): 2*(n/k);? cgy4everOh, you are right! Thanks for finding that. Fixed.
cgy4ever Could you give a more detailed explanation of Problem E? I don't quite get your point in the tutorial.
Which part you can't understand? The part of FFT or the part of sqrt decomposition?
darrensun talked about problem E, not G :P
Sadness of long long int in Problem D :(
Loved the round, contrary to many people saying D had a bad time limit I think it was fine. My solution passed with O(N^2 log N) in 1500ms in final tests and it passed pretests with 1200ms. So I see there were some large testcases in the pretests which is good enough in my opinion (if you pass pretests in like 1800ms-1900ms, obviously you should worry).
D was given in a Bulgarian competition a few years ago so I quickly coded the solution, really loved E though, took me about 2 hours to get it working and I was 5-10 minutes late to submit it.
One of the best competitions I've participated in :)
"This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * (f[n] + f[n-k] + f[n-2k] + ...) — n." if n = 3 , k = 2 and f[3] = 4 , f[2] = 3 , f[1] = 2 , the answer will be 2 * (4 + 2) — 3 = 9 , is not 2 * (4 — 1 + 2 — 1) = 8.
Problem G was used for online contest just 2 weeks ago: Hamming Distance from Hackerrank, it contains problem G as a subtask (H-type queries).
True, but the intended solution in Hackerrank was indeed bit tricks optimizing the naive solution, while in this problem the author had a much cooler one and expected bit tricks to fail.
can anybody please help me understand the B part solution more clearly. More specifically, what is f[i] here? Is it number of people "i", who are destined for f[i]? or something else?. And please can anyone elaborate more on proof of correctness of algo? Thanks
F[i] is simply the floor of the i-th person assuming you've sorted them, so F[n] is floor of the person that wants to get to the highest floor and F[1] the floor of the person that wants to get to the lowest floor. So F is simply the inital array but sorted.
Now what is the solution? Well you know that at some point the elevator will go to F[n], soon or later he has to deliver that person to the F[n]-th floor. Well, while doing that the best thing he can do is fill the rest of the elevator with the other people that go as high as possible. The intuitive proof is that you are going to the F[n]-th floor and it is sensible to get rid of passengers that want to get to high floors as you are anyway going there, and in this way later you might not need to get that high up.
So well, while delivering passenger to F[n]-th floor it is optimal to take F[n-1],F[n-2]...F[n-k+1] with him. Obviously since we sorted the array that's the people wanting to go as high as possible. Well repeating that kind of thinking over and over again it is easy to see that you actually go to floor F[n] and back, then to floor F[n-k] and back, then F[n-2*k], F[n-3*k] and so on. And since climbing up and down again to floor F[i] takes 2*(F[i]-1) time, the total time is simply 2*( (F[n]-1) + (F[n-k]-1) + ... )
Sorry if you don't understand my explanation, I tried my best. You can always try to prove it strictly mathematically yourself but in my opinion it is intuitively obvious that it's the correct way to go :)
Thanks @Enchom, you explained perfectly. I get it now.
I can't understand the last 2 column by column part of E, like that,
suppose We have a target of filling the cell (2,n) and the cell (1,n) is already in position. Now how can we move the cell to (2,n) . If the desired cell is at (1,n-1) or (2,n-1) , then how , can someone explain please?
upd-> sorry , I forgot the part we can move cells diagonally too.
Why problem D is giving TLE, if I am using sets?
Solution using sets 8041413
Solution using vectors 8041479
cgy4ever, can you please show your sample solution for G? I managed to get it accepted with runtime under 5 seconds using FFT + decomposition of input vectors, but it required a highly optimized FFT implementation, fine-tuning of the L parameter and non-trivial implementation of the partial block case. There's no chance I could have gotten it accepted if I followed this approach during the contest, so I'm curious if I'm missing some implementation trick.
I used the size of blocks = 15000 instead of sqrt(n).I got AC without any other optimizations. Try to use L = 15000.
вопрос по D. Я из входной матрицы строю граф(полный), ищу в нем минимальный остов и dfs'ом из каждой вершины нахожу расстояния от неё до остальных и сравниваю с записанными в исходной матрице. итоговая асимптотика получается n^2 * log(n*n) — сортировки. но из-за всяких проверок, построения остова и т.д. у меня TL на 11 тесте(10 еле-еле влазит). скажите, такое решение не предусматривается или нужно оптимизировать? 8063019
Получает AC (8063333) после замены
на
Связано это с тем, что перегруженный оператор "меньше" оптимизируется лучше. А также (самое главное) происходит передача аргументов по ссылке вместо копирования.
Огромное человеческое спасибо)
Can anyone please help me out with this? For Problem A, I found composite numbers using sieve and solved the problem by checking every possible composite number. Submission id is 8060116 I am getting run time error on test case 14, but on my local machine it is giving the answer as 4 4860 when Input is 4864
Thanks.
As you are using
while(curr<=n)you might access p[n]. So the array size should be n+1 instead of n.Could someone explain problem B proof in different words ? Didn't get correctness of it..
Problem D: My Submission
I used the same approach as mentioned in the editorial, but I have a problem of verifying the distances between all pairs of nodes, and that results in TLE.
Is there a faster way to find the distances between all pairs of nodes? Any help?
cgy4ever, can you help me with a sample solution or something, please?
Dfs / bfs from some vertex will find shortest distances to all other vertices.
Run it n times.
Actually after I posted this comment I came up with an idea using Dijkstra n — 1 times to find the shortest paths to all other vertices, because this is a weighted graph. After that I got an AC.
But I don't understand how can I use DFS/BFS to find shortest path on weighted graph.
Oh, I forgot it's weighted. Anyway it's tree and doesn't contain cycles, that's why dfs and bfs work
I tried to find a tree in problem D using Dijkstra from vertex 0, but that solution failed.
When I changed it to Prim, the solution passed.
Can you tell me why using Dijkstra's algorithm to find the tree didn't work in this case?
Can the problem D be solved in the following way?
This approach give WA#9. The test is huge so I can't tell whats wrong. Any help? Code
This approach fails if the two nodes have a LCA other than the root or either of them. See this bad diagram:
However, this very similar idea passes: 8011400. I'm still trying to figure out why. If anyone can explain it (or give a test case where it fails) I would be very grateful :)
Thanks man, dunno how I missed such a big flaw :P
8011400 tries to see whether the dist[x][0] + dist[y][0] — dist[x][y] is twice of any of dist[i][0].
http://codeforces.me/contest/472/submission/20199101
Dunno why did this failed, I tried to consider to distance between two nodes and check them with the sum of the distance two the LCA yet it still failed.
472D — Design Tutorial: Inverse the Problem == http://www.e-olymp.com/en/problems/7413