This post is written to help my friend , Iman , complete this one.
Problem A: Triangle (code)
For each of the possible combinations of three sticks , we can make a triangle if sum of the lengths of the smaller two is greater than the length of the third and we can make a segment in case of equality.
Problem B: President's office (code)
For each cell of president's desk , we check all its neighbors and add their colors to a set. easy as pie!
Problem C: Alice,Bob and chocolate (code)
This one can be solved easily by simulation. see the code.
Problem E: Exposition
I solved this one in O(nlgn) time using a segment-tree and keeping track of minimum and maximum element in each segment. Adding a number is O(lgn) because we need to update minimum and maximum for the log2n segments containing that number. For each start point we query the tree to find the maximal endpoint. This is again O(lgn) and is done O(n) times so we have a total complexity of O(nlgn) fitting perfectly in the time limit.
The solution to Problem E should have a complexity of O(n*lgn*lgn), since an query (O(lgn) time) is made for each loop within the binary search (O(lgn) time).
It can be solve in O(NlogN) if you use two pointers and query in the segment tree each step, The two pointers is O(N) and in each operation we query on the segment tree giving an O(NlogN) solution better than the O(N(logN)^2) of the binary search. However both solutions work good and one more thing the solution with binary search can be done in O(NlogN) if you do the search with the query and no the query for every step of the search. Think about that last solution.
UPDATE: I get an O(n) solution no segment tree
Intuitive solution for Problem D
Can someone please explain any approach for problem D???
Here's the detailed logic I used for solving D:
Let's assume that the archers are numbered starting from 0. I will use the words archer and soldier interchangeably.
Let me first introduce a simplification. The problem says to make the health of the soldier < 0. Let us assume that we have to make the health of the soldier <= 0. To achieve this transition and obtain the same no. of min. moves as the case with < 0, we increment each h[i] by 1.
The only way to kill the 0th and the (n-1)th soldier is to shoot directly at the 1st and the (n-2)th soldiers respectively. Note that 1st and the (n-2)th soldier may be the same. So, at first we kill the 0th and the (n-1)th soldier via this process.
Now, we are left with soldiers from 1 .. (n-2). We'll use DP to solve the problem. Let's process the soldiers in sequence. When we are at the 1st soldier, we may either kill it directly by shooting appropriate no. of balls/bullets on it, or we may leave some of its health which will ultimately be made 0 by the direct shots that we make at the soldier 2.
When we are at the 2nd soldier, the above said things for the 1st soldier hold true for it as well. However, note here that the health of the 2nd soldier must have been reduced indirectly already due to the direct attacks that we made to the 1st soldier, and again we may or may not completely kill it and the remaining damage will be incurred to it by the next soldier (3rd soldier).
These observations tell us while we are at a particular soldier, our state is dependent on:
The index of the soldier that we are at.
The health of the previous soldier remaining. (This will ensure that we shoot atleast as many bullets on the current soldier so that the previous soldier gets killed / his health becomes <= 0).
The no. of direct attacks made on the previous soldier. (this can reduce the health of the current soldier).
Another observation: Since we only have to make the health <= 0, we can take any health < 0 to be 0. This will help us in avoiding negative indexing for the 2nd state variable mentioned above.
So, that's it. We can use a 3 state DP: dp[i][j][k]: where dp[i][j][k]= Min. no. of shots to kill the archers starting from the ith archer when the previous archer still has j health points left and the no. of direct shots at the arches soldiers were k.
Here is my code: 45348194. I have commented it to make it readable. Hope this helps. :)
Thanks a lot man! Your explanation is very clear and code is also very readable.
Can you explain why do we require 3 states here? I have tried this question using 2 states: index and the health of soldier at the current index. I don't know why my approach is wrong. Please explain. My code which fails at test 21- code
UPD: got the problem with my logic. Ignore.
solution to E problem can be done simply with using two sets and one frequency array and two pointer approach checkout solution below for this easy approach https://codeforces.net/blog/entry/59551
Hellooo. I wonder if anyone still visits this blog. I'm a noob trying to solve all the oldest problems on Codeforces, one by one. I think problem 6D is a fairly interesting one. I've solved its simplified version, with n <= 10 and h[i] <= 15, (which is presented on Codeforces now), using backtrack (265517328). But I really want to know how to solve the original problem. Unfortunately, I don't really get the DP solution mentioned in a comment posted above.
D is a good DP problem, but it doesn't deserve 2600 rate nowdays maybe 1900-200