2147A - Shortest Increasing Path
I dont know if it is a good idea to use binary search to find if a valid break point can be set on x axis. although it passed all tests very fast. ~~~~~ left = 1 right = xi find = False while left <= right: mid = (left + right) // 2 if mid < yi and yi < xi — mid: find = True break else: right = mid — 1 if find: print(3) else: print(-1) ~~~~~
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 132 |
| 9 | Dominater069 | 131 |
| 10 | Proof_by_QED | 130 |
Where did the binary search come from? There are only 3 possible answers: -1, 2 and 3. You can watch the editorial for detailed explanation, but binary search isn't used here
binary search is overkill. you can just compare x and y in a certain way and solve it in a few if statements:
$$$x \lt y\implies \text{ans}=2$$$
$$$x \gt y+1\implies \text{ans}=3$$$
$$$\text{else } \text{ans}=-1$$$
if y == 1 => ans = -1
else if x<y => ans = 2
else if x>y+1 => ans = 3
else => ans = -1
this solution passed all test cases for me
one of ur cases should be -1 no?
yeah typo