463A - Caisa и сахар. This is a simple implementation problem.
463B - Caisa и колонны. We have to use greedy method. Start from the first element and pass all the elements in order(also update by the energy).When energy < 0, add abs(energy) to solution and energy becomes 0 or we can find the answer by binary search.
463C - Gargari и слоны. We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays(so that for every element i,j we can find sum of elements which are attacked in O(1) time).Also for avoiding the intersection,we need to find two cells so that for one the sum of row and column is even and for the other one the sum of row and column is odd.Finally,we analyze every cell ,we see if the sum of row and column is even or odd,and update that two positions(solutions).
463D - Gargari и перестановки.We can build a directed acyclic graph with n nodes.If j is after i in all vectors then we add in graph edge (i,j).Now we have to find the longest path in this graph. Another way is using dp.
463E - Caisa и дерево. We use an array of dynamic stacks for every prime factor.We start a DFS from node 1.For node 1 we decompose its value in prime factors and push it to every prime factor's stack.To answer the question for x,we need to see the y (y belongs to the chain from 1 to x) that has a common prime factor with x,so the stacks will help us to see the earliest update(so the nearest y). For every x ,we decompose x to prime factors,look in the array and see the earliest update of the prime factors' stacks(if exists,of course). Also when we get back to fathers recursively,we need to pop from the prime factors' stacks. For every update we have to start dfs again.
Can someone explain the another way "Dp" of problem D ??
dp[i] = longest common subsequence which is finished at position i (i is position in first vector) dp[i] = max(dp[j])+1 with j < i and position of a[j] < position of a[i] in all vectors. The answer is maximum value of dp.
is a[i] and a[j] are the element from first vector ???
yes
if you explain it with more detail then it is more understandable and may be then i can get it clearly
i get it "get AC" AFTER 3WA :)
Problem D: it can be solved by DP...
Well... Do you mind explaining?
People who read the editorial are the people who didnt solve the problem, saying that it can be solved in a certain way is not helpful
Firstly lets create a position array for each sequence and call it pos[k][n]. In this array we store the positions of each of the n numbers (from 1 to n) to know where they occur in each of the sub sequences.
Now the dp solutions starts. dp[i] marks the maximum length common sequence we can generate by using the first i elements of the first sequence. For this we iterate over all possible previous numbers (j) and see if we can extend dp[j] to dp[i]. This can be done only when positions of number a[j] is less than positions of a[i] for each of the sequence. Then we can extend j to i. Finally we take the maximum of values in dp array. Refer to my solution in the contest. Link
Nice explation. Thanks a ton!
thanks for this :)
B question can be done by just taking the maximum of all the heights :D
Can anyone explain why this solution works?
the law of conservation of energy(http://en.wikipedia.org/wiki/Conservation_of_energy).You need to have max(h) energy at the beginning to make sure that you can pass through the highest point.
Just to be good guy. In order to climb to the a[i], you need to have starting energy more or equal to a[i]-a[i-1]+a[i-1]-a[i-2]+.... which equals to a[i], and you need to be able to climb to a[i] for 0<=i<n, thus you need amount of energy equal to maximum of an array.
You can consider it in my way below: 1. you must confirm that height sequence 1 2 2 3 3 4 4 4 is same with 1 2 3 4 right? if you think it's good, then you can prepare the input sequence as totally distinct element in it:) 2. troughs undo peaks right? 3. so finally the max height left:) hope my explanation helps u:)
yep, you said what I want to say:)
E's test is too weak.
Many brute force can pass.
And can you share the standard solution of E?
Maybe they pass because TL is 10 sec and
Isn't it?
Yes. It means that the queries of type 2 are not more than 50.
But if there are many queries of type 1, then it will TLE.
The case is: the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time.
Look at this data maker:(use python to make it)
463A — Caisa and Sugar. This is a simple implementation problem.
This is a simple way to offend people. I'm sure that there are some coders who couldn't get AC on this problem and they will probably feel like sh*t if they come here and read "this is easy". If you don't want to write editorial for this problem don't even mention it.
This is CODEFORCES!!!1111oneoneone
I would never thought that brute force can pass problem E.
Me, too... The test must be too weak.
Is there anyway to solve problem D if the k arrays aren't permutations of 1, 2, .. n ?
I believe complexity would become an issue — see here. (If I'm reading that correctly, it looks like it's O(kn + 1)).
I doubt, except exponential, you can find longest common subsequence in O(len1*len2) and keep searching for same one in other arrays, that would be O(d*n^2) best case, but if you have more longest common subsequences it could lead to exponential time complexity.
Nice(!!!) Tutorial !!!
I don't think the explanation of A is helpful. If people didn't get it, it should be explained, and I saw people who got problem D that didn't get AC on problem A.
The solution is to check each type of sugar and determine if you can buy it. If you can, the number of sweets you will receive is 100 - yi for that type of sugar, except for the case where yi = 0, in which case you will receive 0 (thank you to yash.15296 for catching that this was missing). The goal is to maximize that value on a type of sugar you can buy.
Pseudocode:
The first condition (
s > x[i]
) is the case in which you have more money than the sugar costs, and the second condition (s == x[i] and y[i] == 0
) is the case in which you have exactly enough to buy the sugar.Note that initializing
ans = -1
will also handle the case where you can't buy any of the types of sugar, since neither condition will ever be met and therefore the value ofans
will never change.One thing that I feel could've been stated better in the problem was that you are only buying one unit of sugar, regardless of how much money you have, so in the case
The answer is 40 (buying one unit will leave you with 3 dollars and 40 sweets) and not 80 (if you could buy two units, you would receive 0 dollars and 80 sweets), even though you can logically afford two units of that type of sugar.
Hack : 1 9 8 0
Thanks, good catch. I knew I was missing something.
Thanks! It seems like almost everyone who submitted and didn't pass pretests got it wrong because of
, myself included.
Not quite correct; as stated, the hack
1 9 8 0
works (expected0
, output100
). You need to modify the cases:This handles the case where if the cents is 0: you should enter the first case, where you receive 0 sweets, instead of the second case where you (wrongly) receive 100 sweets.
EDIT: I should refresh the page before posting a comment.
Please answer to this questions, NelsonMondialu!
Problem C:
We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays(so that for every element i,j we can find sum of elements which are attacked in O(1) time)
How? For what time complexity do you do the preprocessing?
...we analyze every cell... What particularly do you analyze? The PH of the sell?
Give some examples please!
P.S. One of the worst editorials I've ever seen.
Couldn't agree more. A real explanation or pseudo-code of problem C would be highly appreciated. I actually thought pretty much the same solution but I couldn't implement it.
Read a[i][j] Lets call the \ diagonals as 0 and / diagonals as 1. Make some way of hashing the diagonals, and then just do dia[0/1][numOfDiagonal]+=a[i][j], where numOfDiagonal is some number that depends on i and j, and could be achieved only by i and j in that diagonal. That would be the preprocess.
Can you provide link to your solutions!!!
Am sorry but these are really poor Editorials :(
Can anyone explain, How to solve the problem D with graph, I am not getting the editorial??
Another way to think about problem D is like this : Consider two sequences, how to find out the lcs in an optimal way. Because all the numbers are distinct in the first sequence, one of the way is to re-number the second sequence according as the order in which the numbers appear in the first sequence. Then an lcs of both is just a longest increasing sub-sequence of the second(because after re-numbering the first sequence becomes 1,2,3...,n). For multiple sequences we have to just find lis in one of them according to re-numbering in all the other sequences. Or re-numbering implies for the standard lis update equation dp[i] = dp[j]+1 if i>j & a[i]>a[j], we have also to make sure that a[i] and a[j] appear in the same order in all other sequences. That's why we have to make such graph. Or just check these conditions in all other sequences. Time = O(n*n*k). For a simple implementation see : http://codeforces.me/contest/463/submission/7631750
Someone explain me Problem C please..
A clear tutorial for problem A,B and C(D is the same as official tutorial,and I have no idea for problem E)
Problem A:
for the starter,we need to make a question clear:Can Caisa buy a type of sugar more than once?
for example ,there is a suger
2 60
and he has 6 dollars
can he buy the sugar twice for 5 dollars and 20 cents and get 80 sweets?
And the answer here is :NO
So the way to solve this problem is quite clear:
Try to buy every kind of sugar once,if we can afford it and the sweet we can get is more than previous choice,update the answer we save.
A lot of people make mistakes when dealing with some boundry situation like the following two hack data I used during the contest:
1 10
10 30
(Answer:-1,Wrong output:70)
1 10
10 0
(Answer:0,Wrong output:-1)
So,thinking carefully during coding and check your code before submit it to avoid this kind of unnecessary mistake.
My solution:7646837
Problem B:
the solution in the official editor is quite weird as far as I'm concerned.
You can write some number on paper randomly on paper and simulate the process, you'll find an interesting conclution:
if you have energy which is >0(let's say,E=a),you'll find yourself standing at somewhere lower than the h[Pylon 0] by a
if you have energy which is <0(let's say,E=-b),you'll find yourself standing at somewhere higher than the h[Pylon 0] by b
Example:
Pylon 0 1 2 3 4
Height 5 1 6 2 5
Energy 0 4 -1 3 0
it just works like Potential energy — process doesn't matter.Energy is just determined by your start to an end position.
Now we want Energy at evrywhere be non-negative,and we have only one start position to consider.So, we should make the start position as high as the highest Pylon.
So the answer is the biggest number in the given n numbers
(P.S. I think it should be the Problem A since the code is too short,which surprised me)
My solution:7646841
Problem C:
Facing with this kind of problem,why don't we draw a chessboard (with black and white ceils) on our paper?
It's obvious that if two bishops are in two ceils with same color, they'll attack at least one same ceil.So one should in a black ceil,and another should be in a white ceil.
n<=2000,there are at most 4000000 ceils to consider,and with a time limit of 3 seconds, so we can try some O(n^2) algorithm.
Enumerate every ceil on the board,and calculate how many points will the bishop get.And the expected answer should be the best point getter on the white ceils and black ceils.
It would be too slow if you calculate points will the bishop get on each ceil with an O(n) way
(that would be O(n^3)),so some preprocess may help.
We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays
so point we can get at ceil(x,y) can be described as:
point[x,y]=principal[principal_id(x,y)]+secondary[secondary_id(x,y)]-chessboard[x,y];
and we can calculate it with O(1)
so the total time complexity is O(n^2(reading and preprocessing)+n^2*1(calculating the answer))=O(n^2)
And be careful with some tricky situation like the following one:
2
0 0
0 0
(Acceptable Answer:
0
1 1 1 2
)
some great players make mistake on the one above.
Also, the answer may bigger than the range of 32-bit integers,so use 64-bit integers during calculation.(in C/C++,long long ; in Pascal ,int64 ; in Java ,long)
My solution:7641967
Well that's how an editorial should look like. +1 from me
Well , maybe only freshmen knows what other freshmen needs.A professional may think it weird to make any mistake on div 2 problem A and B ,so they think explanations are unnecessary and skip those.
I'm just a Newbie in China ,which is not joking.
Thanks a lot for this comment... :)
C is much easier to me now... :D
Very friendly for understanding, thx a lot!
can any explain problem E in detail :) ???
I'll post my solution for E and try to do a "mini-editorial" for it. You can easily notice that the value for any node is maximum 2*10^6. We can keep a binary search tree (Set in c++) for every number from 1 to 2*10^6. In each set we will keep a pair (depth[node], node) in order to find in O(1) the deepest node which has the divisor according to the set.
Example: node = 1; value[node] = 6; ( 6 = 2*3 ) depth[node] = 2;
We modify these sets in the DFS as follows:
!!!Node: these sets are gives the nodes sorted by their depth
When we find an update query we just run DFS(1) and done! If something is not clear just ask!
Code: http://codeforces.me/contest/463/submission/7647093
The DFS may be 'segmentation fault' if the tree is a long link. If the length is 80000, and it break.
what is the work of this line ans[node] = max( ans[node], last_element_in_set ); ?
ans[node] is a pair (depth, node number).
The bigger pair means that's a node with greater depth.
thanx AlexandruValeanu
Can someone explain in detail how to built the graph in problem D?
Acc to what I hav understood take every pair of i and j and see if i comes after j in all the given permutations.If yes,add edge i-j in the new graph.This makes the graph to find the longest path.Pl tell if I am wrong somewhere.
EDIT:Sorry didn't read Alexandru's reply which is the same as what I said.
Some idea of understanding Problem D(graph theory solution):
If i is in front of j in all k sequences then we add in graph a directed edge (i,j).
--what does the edge mean?what happends if we go through the edges?
Well ,think carefully:
If i is in front of j in all k sequences,then subsequence [i,j] is a common subsequence of those k sequences.
and if we walk through the edges, and line up nodes on the path we walk through, it would be a common subsequence of those k senquence.
=====================================================
and obviously,the graph is a DAG(directed acyclic graph),
to make it simple,I'll use in_front_of(x,y) to replace the statement x is in front of y in all k sequences
if in_front_of(i,j) is true ,it's obvious that in_front_of(j,i) is false.
Also if in_front_of(i,j) is T,in_front_of(j,k) is T,it's obvious that in_front_of(k,i) is false
=====================================================
with those in mind ,the longest path on this DAG will be the solution we need in this problem.
There are several ways to find a longest path on DAG, I'd like to use Topological sorting.
My solution:7647678
OMG,it's intresting to find that tutorial of every problem in this round is rewritten by other users, seems everyone's unsatisfied with this brief official tutorial.
I think it's just so so,
all right,I don't like it,
well , I hate it!
My solution for E always get TLE on test 7. The approach is the same as the tutorial, so I think there must be something wrong with my code, but I couldn't find it out. Does anyone know why? Here is my solution: 7650731
Find my mistake after lunch... Line 43: if (prime[i] > val) break; should be: if (prime[i] * prime[i] > val) break; And in fact, the prime factors of a node can be saved, we just need to change one node after each update.
Weak test cases in Problem E , Even brute force is passing all TCs
Is this going to be the 1st editorial with contribution <=0?
you bet Good editorials need to have clear in-depth explanations guided with proofs and well explained methods. fchirica has these kind of editorials and he is rewarded with +200. I personally like these editorials the best
In statement of problem E the sentence "there are no more than 50 queries that changes the value of a vertex" is ambiguous. It can be understood as "there are no more than 50 queries that changes the value of --each-- vertex", that is equivalent to say "for each vertex, there are no more than 50 queries that change the value of such vertex". With this interpretation, this condition is useless. In fact, I understood the statement in such a way, and have spend one day to solve the problem without taking advantage of the restriction.
AFAIK "value of a vertex" should mean that we don't care which vertex it is; the word "each" is used precisely to differentiate your understanding from what was meant here.
Well, it is ambiguous. The normal way to say that would be "there are no more than 50 queries of type 2". Anyway, now I am happy to have such a missunderstanding, since I have been able to solve the problem even without such a restriction.
Yeah, it does sound strange — just pointing out that it is a gramatically correct wording (unlike other cases where the statement is unclear because nobody can make sense of it).
Ok, since my english is very far from perfect, I believe you, and will try to improve my understanding.
In problem D, lets consider if k is 5, then can we find LCS of of first two sequences, store and and then find LCS of this result and the next sequence. Are there any issues with such an approach?
correct answer: 7 8 9
your answer: 1
Oh okay thanks
sry, didn't look at dates...
Solution to C:
First let me put the question in this way...
Consider a chessboard with back and white checks alternatively.You have a white and a black bishop(by this we assure both of them will never attack the same position). So now you have to put them in such a way that they both can earn maximum points together.
Solution:
It is pretty simple to see that the sum can be maximum only when the individual bishops fetch maximum money(as they both do not intersect each others path). So first precalculate the diagonal sum for all individual cells(which is equal to the money the bishop would have fetched if put at that location). Then you just find the maximum for white bishop and that for black bishop separately and add them up to get the answer.
Solution
why this code is wrong ? http://codeforces.me/contest/463/submission/41503320
Print the length of the longest ""common"" subsequence.
i do that ! did you see my code ?
Of course I read your code. What you are calculating is the longest "Longest Increasing Subsequnce", not the length of the Longest "" Common "" Subsequence.
I can hack your solution even k=1.
hack : 3 1 3 2 1
thank you for that and i hope to be like you in the future
In Problem C there is a problem with the testcases. for the case: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The answer 1 1 1 2 is not accepted.
B can be solved by just finding the maximum height.