### Question:
There is a grid with a balloon at some cells. Players can shoot arrows from outside the grid horizontally and vertically. Every arrow shot will burst all balloons in that row if fired horizontally and in that column if fired vertically.
Given the positions of the balloons in the grid find the minimum no of arrows required to burst all the balloons.
### Constraints:
1 <= N(No of ballons) <= 50
0 <= x, y -> Positions of the balloons < 10^9-1
### Input Format:
Line1: Integer denoting N.
Next N lines, where each of the ith lines contains two integers representing (row, col) of ith balloon.
### Sample Input :
6
15 21
33 8
17 21
17 8
28 11
28 19
### Sample Output:
3
### Sample Input :
6
15 1
15 2
15 3
15 4
18 1
20 1
### Sample Output:
2
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 14:43:10 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Where did this assessment held?
hackerrank
Is the assessment going on right now, if so then pls remove the question.
No is was a past question.
Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).
Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).
EDIT-Seems like I have the wrong approach
Future can affect the past here :)
Wait, no, I can't see how it fails
Let say for some balloon at (x, y) you shoot an arrow in vertical direction, then it affect the already calculated value for (x, y-1), (x, y-2).... (x, -INF);
Please never change the original comment, now all replies make no sense to upcomming readers.
Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).
Think in terms of graph, assume line to point graph, it will be bipartite, then the question is minimum vertex cover on bipartite graph, or MBM using konig theorem.
could you kindly elaborate ?
Can yoou share the link of the problem?
This is such a bad problem for online assessment for job interviews.
I guess recruiters just select some problems from Hackerrank library for job interviews without even checking what the solution requires :P
IMO final objective of companies to take online assessment is to just reduce the number of candidates, so if they are achieving their objective goal why would they even care.
I think we can solve it the following way in order, although i am not sure.
If there are no balloon in that row and column, then remove that and increment the answer by one.
Then If there are no balloon in this column, (it is profitable to hit by row). Hence remove all the balloons in this row. Similarly do for columns.
Now if there is a balloon in a cell, then we have at least one balloon in that row and in that column. Hence there can be no more than 25 distinct rows or columns. We will do brute force(i.e. check all subset of rows / columns and then if we do row/column shot on that subset, then how many column/row shots I need for the remaining) and then get the minimum.
The complexity should be no more than O(N * 2^(N/2))
Nice!!, but it will be hard to prevent TLE by this approach.
yeah. It comes to around 2*10^9 operations. I cant think of any other way.
This is min vertex cover of a bipartite graph. Construct a graph where the left nodes are the rows and right nodes are the columns with an edge between a row and a col iff that position in the grid contains a balloon. The min cut of this graph is the minimum number of arrows required to pop all balloons.
Since the max flow across a graph is equal to the min cut, we can solve this in V*sqrt(E) time after coordinate compressing to only count rows or columns with at least one balloon, or in other words 102*sqrt(50) runtime, which should be plenty fast enough if we use Dinic's algorithm to calculate the max flow.
smh people hiring software engineers based on this. Yeah, in the 2AM server crash, someone who knows vertex cover, and Dinic's algorithm will fix it in mere minutes.
You dont have any idea how difficult it is to manage google's servers!
Any company can face such issues, and it happens once in a blue moon. The fact that that google has been able to manage everything smoothly so far suggests that the people they hired are not bad.
Of course one cannot be a master of everything. Once you enter an organization you have to learn stuff.
So people who can think smart and learn fast do great in this IT field.
https://tryalgo.org/en/matching/2016/08/05/konig/
This is a good article to understand the minimum vertex cover for a bipartite graph.