NelsonMondialu's blog

Codeforces Round #264 Tutorial
By NelsonMondialu, 10 years ago, In English

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.

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (78)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can anyone explain why this solution works?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep, you said what I want to say:)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E's test is too weak.

Many brute force can pass.

And can you share the standard solution of E?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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)

      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
      → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +32 Vote: I do not like 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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Me, too... The test must be too weak.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Nice(!!!) Tutorial !!!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hack : 1 9 8 0

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, good catch. I knew I was missing something.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide link to your solutions!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Am sorry but these are really poor Editorials :(

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/463/submission/7631750

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone explain me Problem C please..

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very friendly for understanding, thx a lot!

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it

    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://mirror.codeforces.com/contest/463/submission/7647093

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The DFS may be 'segmentation fault' if the tree is a long link. If the length is 80000, and it break.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is the work of this line ans[node] = max( ans[node], last_element_in_set ); ?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ans[node] is a pair (depth, node number).

        The bigger pair means that's a node with greater depth.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanx AlexandruValeanu

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it 
    for ( i = 1, N )
	for ( j = 1, N )
		if ( j is after i in all permutations )
			addEdge( i, j ) /// i->j
    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like 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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Weak test cases in Problem E , Even brute force is passing all TCs

      → Reply
»
10 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

sry, didn't look at dates...

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this code is wrong ? http://mirror.codeforces.com/contest/463/submission/41503320

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i do that ! did you see my code ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

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

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B can be solved by just finding the maximum height.

→ Reply