I was hoping to start practising on CF Div 1D and Div2F.

Finding all Div1D is easy as Division 1 rounds are specified, but it is impossble to know whether a Div2 only round has problem F based on just looking at it.

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 154 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | atcoder_official | 144 |

9 | pajenegod | 144 |

I was hoping to start practising on CF Div 1D and Div2F.

Finding all Div1D is easy as Division 1 rounds are specified, but it is impossble to know whether a Div2 only round has problem F based on just looking at it.

Could anyone suggest some problems which utilize Dilworth's theorem? Thanks in advance :)

In 173E, I've been getting denial of judgement several times. I tested with a previously accepted solution, and it resulted in the same denial of judgement verdict. On further investigation, I observed that test case no 64 is not being shown, like here-

Perhaps it's missing, due server-side data being corrupted?(if that makes any sense)

Here, it says- "First, place 0 as the first number. Next, for every following number ai + 1 we will select maximum possible number from numbers left, matching above constraints (in simple case it will be ai + 1, otherwise we will check if ai - 2 left, e.t.c)."

I can see that it works, ie it produces the correct answer. However, I can't quite understand why it works.

I'd be very glad if someone helped me out, explain why this greedy is correct-and what the thought process is for arriving at this particular solution.

Problem description starts here- /* King Motashota is in a war against the mighty Bachchaloks. He has formed a well trained army of snipers, and planning to use them as much as possible. In one of the missions, he has S snipers. They will be dispatched to get rid of the soldiers guarding the bank of the river Nodi.

From satellite images, Motashota has located positions of all enemy soldiers. Now, the plan is, snipers will take their positions. They are excellent swimmers, so, you can assume that they won't get caught, while taking position. Upon order from Motashota, they will start shooting enemy soldiers. A sniper can shoot a soldier, if Euclidean Distance between the soldier and sniper is no more than D. After the snipers get rid of all the soldiers, they can proceed with the operation. So, it is important for them to position the snipers in such a way that, all soldiers are within the range of at least one sniper.

In addition, when snipers start shooting, the guards will be alert, and thus, snipers can't change their position, they can only continue shooting from their position.

The river bank is defined by the horizontal line y = k. All points (x, y) where y > k is in the enemy territory, and if y < k, then it's on the water. You will be given location of N soldiers, strictly in the enemy territory; you have to place S soldiers in the water, so that they can kill all soldiers. For security reasons, the snipers should be as far from the bank as possible. For any sniper in position (xi, yi), the distance from the bank is |yi — k|. If, for all snipers, the minimum of them is M = min{|yi — k|}, you have to maximize M.

Both the soldiers and snipers are really superstitious. They will stay only in integer coordinates.

Input Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a black line. Next line contains four integers, k (-108 ≤ k ≤ 108), N (1 ≤ N ≤ 10000), S (1 ≤ S ≤ 10000) and D (1 ≤ D ≤ 109), the position of the bank, number of guards and number of snipers, and the range of the snipers.

This is followed by N lines, each containing a pair of integers (xi, yi) the position of ith guard (-108 ≤ xi ≤ 108, k < yi ≤ 108).

Output For each case, print the case number and M which is described in the statement. If the snipers cannot kill all the guards, print "impossible".

Sample Input Output for Sample Input 2

0 3 2 4 1 1 3 2 9 1

0 3 1 4 1 1 3 2 9 1 Case 1: 2 Case 2: impossible */

My code- Code

Idea-Sort the position of guards, then binary search the answer. Here, I checked if a particular distance was valid by greedy approach. Getting wrong answer, however; could some one tell me what's wrong with my code?

When I'm practising, I'm not sure how to choose the difficulty of the problem that I should attempt.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/23/2024 00:34:13 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|