A.K.Goharshady's blog

By A.K.Goharshady, 13 years ago, In English
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. 
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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

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

Intuitive solution for Problem D

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

Can someone please explain any approach for problem D???

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

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:

  1. The index of the soldier that we are at.

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

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

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

    Thanks a lot man! Your explanation is very clear and code is also very readable.

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

    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

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

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.com/blog/entry/59551