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.
solution to problem D still not clear, would appreciate if someone could provide a better explanation.
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
For any hare except the first and last there can be three cases :
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 )
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 :)
awesome explanation, thank you so much!!
Crystal clear explanation. Thank you. :)
great explanation.. thxs a lot!!
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 ^_^
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
Same O(n^2) complexity
Problem A condition 1 and 4 are same. condition 2 and 3 are also same.
Can we do problem D with recursion? If possible can anyone please explain the states and base case?
use recursion you will get TLE and has many repeated problem
I am talking about DP with recursion I have written this code but its not working,
http://codeforces.net/blog/entry/9334#comment-149501 this one is awesome!!
really awesome. thanks.
my recursive solution for D https://codeforces.net/contest/358/submission/91724299
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.
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.
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.
After the 0-command you should empty all the containers.
Guess I missed that...
actually, the second
8
will be stored in the deck(front), while the numbers6
,5
,7
,3
will all be stored in the deck(back). therefore optimal answer for first0
is8+9+8 = 25
(not24
)The first 8 is for the number of operations.
oops, sorry about that....then ur right, the answer should be
24
.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?
answer should be "divisor of maximal length sequence" minus 1; because if the answer is
2
, then there will be3
consecutive1
s (start square, end square, and square u have jumped over)more formally k should be divisor of all consecutive ones length,there is not Necessary maximum length.Am I right?
yes i think you are right.
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$$$ ].
This is super late but there is a simple $$$O(n)$$$ solution for 358A if anyone's interested: https://codeforces.net/blog/entry/66841
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
The idea is the following. We add the points incrementally and check and update our information about the state. If the closest neighbour to the newly added point from the left or from the right are closer to it than the previous added point, then there is an intersection. Of course there are some special cases when using std::set but nothing hard.
But how to get to O(n)?
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!