Sereja's blog

By Sereja, 11 years ago, translation, In English

358A - Dima and Continuous Line

Author — Berezin

If our line has self-intersections, that some pair of semi-circles exists, which intersect each other.
Let points x1 < x2 are connected with a semi-circle and points x3 < x4 are connected with another semi-circle. Then this semis-circles intersect if one of the conditions is true:

1). x1 < x3 < x2 < x4
2). x3 < x1 < x4 < x2

Let’s iterate trough all pairs of semi-circles, and check if the semi-circles intersect each other. So, the solution will have complexity O(N2) what satisfied the constrains.

358B - Dima and Text Messages

Author — Berezin

It’s clear, that adding new random symbols means, that we can simply omit them, they don’t change the structure of the phrase:  < 3word1 < 3word2 < 3... wordN < 3. Let’s determine the phrase before inserting random elements: s = " < 3" + word1 + " < 3" + ... + " < 3" + wordN + " < 3". Lets i —is an index in s, we are waiting for. At the beginning i = 0; we will iterate though the sms and when we will meet the symbol which equals to si we will simply increment i.

if at some moment |s| ≤ I we found all needed symbols and answer is yes, otherwise – no.

358C - Dima and Containers

Author — Berezin

We know all the numbers at the beginning, so, it’s clear, that we want pop three maximums. We can “precalculate “ maximums with finding next zero and iterating through all numbers between two zeroes.
We should do pops from different containers, so let’s save maximums in the top of the stack, in the beginning of the queue and on the beginning of the dek. (you can do this in some other way) We should determine, where will be stored the 1st, 2nd and 3rd maximum. For example, the first(the biggest one) – in the stack, second – in queue, and the third – in dek. “trash” – other numbers we can save into the end of the dek.
Also you need to catch cases, when two or less numbers are between zeroes.

358D - Dima and Hares

Author — Sereja

Let’s look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn’t depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics:
1). d0i — answer for suffix as a separate task.
2). d1i — answer for suffix if the previous hair for this suffix is feed already.
Movements:
d0n  =  an
d1n  =  bn
d0i  =  max(ai  +  d1i  +  1,  bi  +  d0i  +  1)
d1i  =  max(bi  +  d1i  +  1,  ci  +  d0i  +  1)
answer is d01;

358E - Dima and Kicks

Author — Sereja

The first thing to understand is that the answer is the divisor of maximal-length sequence of standing one by one ones. (1111…11)
Let’s iterate trough this number. Now we should check the table knowing the value of K. Let’s find the most left of ones, and choose from them the most top. Let it be (X, Y). then after each step Dima can appear inly in cells which look like: (X + K * a, Y + K * b). Let such cells are the vertexes of the graph. And sequences of ones – the ribs. We will build the graph. We should check that there are no additional ones in table. We should also check if the graph is connected and has en Euler’s path. The value of K is the next answer under the all conditions. The correct implementation will have the complexity O(N * N * log(N)). In reality it will be never achieved.

  • Vote: I like it
  • +27
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

solution to problem D still not clear, would appreciate if someone could provide a better explanation.

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

    f[i][0]:set i before i-1 f[i][1]:set i-1 before i

    f[i][0]=a[i]+max{f[i-1][0]-a[i-1]+b[i-1],f[i-1][1]-b[i-1]+c[i-1]} f[i][1]=b[i]+max{f[i-1][0]-a[i-1]+a[i-1],f[i-1][1]-b[i-1]+b[i-1]} =b[i]+max{f[i-1][0],f[i-1][1]}

    i=1 is special since it doesn't have state f[i][1]

    look my code for detail:my code

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    For any hare except the first and last there can be three cases :

    1. Both the adjacent hares are hungry
    2. Both the adjacent hares are already fed
    3. Exactly one adjacent hare is fed

    So when I am at a particular hare I should know if I have fed the previous hare and I have to make a decision for the current one that whether it should be fed now or after the next hare

    So state would be like ( int position, bool previous )

    if previous is true (previous hare is already fed) :
    
     1. I can feed the current hare now so result1= solve( position+1, 1)+ b[position]
     2. I will feed after the next one so  result2 =  solve( position+1, 0)+ c[position]
     
    
    Else if previous is false (previous hare is not fed)
    
     1. I can feed the current hare now so result1= solve( position+1, 1)+ a[position]
     2. I will feed after the next one so  result2 =  solve( position+1, 0)+ b[position]
    
      return max(result1,result2)
    

    Boundary conditions :

    *Now I will call my solve function as solve(0,0) coz 1st hare has no left adjacent hare.so I assume it as hungry always

    *When I am at my last hare I will take care not to feed any right adjacent hare of it

    u can see the code here :)

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

      awesome explanation, thank you so much!!

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

      Crystal clear explanation. Thank you. :)

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

      great explanation.. thxs a lot!!

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem A have more simple solution

you pick two consecutive points and check them with all other consecutive points

let the points to be x1,x2 and x3,x4. you want to check if semi-circle between x1 and x2 intersects semi-circle between x3 and x4.

**all you have to do is swap x1 with x2 if x1 > x2 and swap x3 with x4 if x3 > x4

this will lead to one condition if ( x1 < x3 < x2 < x4 ) then intersected**

i know it's easy to some people but some guys got stuck with it ^_^

  • »
    »
    11 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Another possibilty though involving too much work is treat each semicircle as a circle and find centers and radius of each. Now two circle intersect iff

    • (r1-r2)^2 < (dist. b/w centers)^2 <(r1+r2)^2

    Same O(n^2) complexity

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem A condition 1 and 4 are same. condition 2 and 3 are also same.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do problem D with recursion? If possible can anyone please explain the states and base case?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote the code for Dima and the Text Messages in CodeForces Round 208 division-2 in Java. Every time I submit the code it says TLE. But don't know why it says so even if I am using BufferedReader and PrintWriter for reading and printing the values. My solution code in 4901148.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    s = s + str + "<3";
    

    String concatenation is not efficient in Java. It create a new String and copies the old value because in this language, Strings are an immutable type. You can use .concat or StringBuilder instead or rethink the algorithm.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the 3rd problem 'Dima and containers', what if after the end of all operations there are some numbers left in the containers? If this is a possible case then the approach given in the editorial would not work and if it this is an invalid case, shouldn't this be specified in the problem statement. I did not code the solution to this problem because of the following test case:

8 9 6 5 8 7 3 0 0

According to the editorial 9 would be stored in stack, 8 in the queue and 7 in the deck(front). all other numbers will be stored in the end of deck. For the first 0 operation all three containers will be popped giving 24 (9+8+7). But for the second zero only one container can be popped giving 6. so total answer is 30 while the optimal answer will be 38.

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

    After the 0-command you should empty all the containers.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    actually, the second 8 will be stored in the deck(front), while the numbers 6,5,7,3 will all be stored in the deck(back). therefore optimal answer for first 0 is 8+9+8 = 25 (not 24)

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem E,ans is not "divisor of maximal-length sequence of standing one by one ones",for example testcase 3 maxlength=4 and ans=3,maybe i didn't understand idea and can someone explain me the main idea in detail?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    answer should be "divisor of maximal length sequence" minus 1; because if the answer is 2, then there will be 3 consecutive 1s (start square, end square, and square u have jumped over)

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

      more formally k should be divisor of all consecutive ones length,there is not Necessary maximum length.Am I right?

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The editorial for problem E reads: "The first thing to understand is that the answer is the divisor of maximal-length sequence of standing one by one ones".

Note that the answer will also be the divisor of ( minimum length consecutive segment of $$$1s$$$ of length $$$> 1$$$ that cannot be extended further $$$-$$$ 1) [with the exception of a grid containing all isolated $$$1s$$$, in which case, $$$0$$$ is the only possible solution and the output has to be $$$-1$$$ ].

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

This is super late but there is a simple $$$O(n)$$$ solution for 358A if anyone's interested: https://codeforces.net/blog/entry/66841

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

    Could you link your submission for your O(n) solution? I found the O(n log n) for the A problem. Here it is 109041885

    Spoiler

    But how to get to O(n)?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I find the method of dynamic programming for problem D is interesting and quite new to me so are there any problems that are similar to that one? If yes, please give me some, I would appreciate it very much. Thank you!