Блог пользователя NelsonMondialu

Автор NelsonMondialu, 10 лет назад, По-английски

463A - Caisa и сахар. This is a simple implementation problem.

Sample solution.

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.

Sample solution.

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).

Sample solution.

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.

Sample solution with graph.

Sample solution with 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.

Sample solution.

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone explain the another way "Dp" of problem D ??

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

B question can be done by just taking the maximum of all the heights :D

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can anyone explain why this solution works?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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:)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yep, you said what I want to say:)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E's test is too weak.

Many brute force can pass.

And can you share the standard solution of E?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe they pass because TL is 10 sec and

    there are no more than 50 queries that changes the value of a vertex.

    Isn't it?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      n = 100000
      print n, n
      
      for i in range(n - 1):
          print 2,
      print 3
      
      for i in range(n - 1):
          print i + 1, i + 2
      
      for i in range(n):
          print 1, n
      
»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +32 Проголосовать: не нравится

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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

I would never thought that brute force can pass problem E.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyway to solve problem D if the k arrays aren't permutations of 1, 2, .. n ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I believe complexity would become an issue — see here. (If I'm reading that correctly, it looks like it's O(kn + 1)).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Nice(!!!) Tutorial !!!

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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:

ans = -1
for i = 0..n:
  if s > x[i]:
    if y[i] == 0:
      ans = max(ans, 0)
    else:
      ans = max(ans, 100 - y[i])
  if s == x[i] and y[i] == 0:
    ans = max(ans, 0)

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 of ans 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

1 6
2 60

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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Hack : 1 9 8 0

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Thanks! It seems like almost everyone who submitted and didn't pass pretests got it wrong because of

    You are only buying one unit of sugar, regardless of how much money you have.

    , myself included.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Not quite correct; as stated, the hack 1 9 8 0 works (expected 0, output 100). You need to modify the cases:

    for i from 0 to n-1
        if x[i] <= s and y[i] == 0
            answer = max(answer, 0)
        else, if x[i] < s
            answer = max(answer, 100 - y[i])
    

    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.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you provide link to your solutions!!!

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Am sorry but these are really poor Editorials :(

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain, How to solve the problem D with graph, I am not getting the editorial??

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone explain me Problem C please..

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well that's how an editorial should look like. +1 from me

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks a lot for this comment... :)
    C is much easier to me now... :D

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Very friendly for understanding, thx a lot!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can any explain problem E in detail :) ???

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

    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;

    At one point we will have: (2,1) in Set[2] and
                      (2,1) in Set[3]
    

    We modify these sets in the DFS as follows:

    void DFS (int node)
    {
    	ans[node] = pair(-1,-1) /// we might not have an answer for this node
    
    	for ( every prime divisor of value[node] )
    		if ( Set[ prime divisor] not empty ) /// we have found a node x that has the same divisor and our node
    		ans[node] = max( ans[node], last_element_in_set );
    
    	for ( every prime divisor of value[node] )
    		Set[ prime divisor ].insert( pair( depth[node], node ) );
    
    	for ( every every child of node )
    		DFS(child)
    
    	for ( every prime divisor of value[node] )
    		Set[ prime divisor ].erase( pair( depth[node], node ) );
    }
    

    !!!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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain in detail how to built the graph in problem D?

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
    for ( i = 1, N )
    	for ( j = 1, N )
    		if ( j is after i in all permutations )
    			addEdge( i, j ) /// i->j
    
  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Is this going to be the 1st editorial with contribution <=0?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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).

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ok, since my english is very far from perfect, I believe you, and will try to improve my understanding.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

sry, didn't look at dates...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Print the length of the longest ""common"" subsequence.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i do that ! did you see my code ?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          thank you for that and i hope to be like you in the future

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B can be solved by just finding the maximum height.