dp[i] - минимальное количество отрезков, если последний отрезок заканчивался в позиции i. ответ dp[m].

I've been struggling hard to overcome WA 8...
Then I've made these test cases and got AC in one go.
I hope these tests will be helpful to overcome WA... :)

Case 1:
4
3 0
4 0
1 0
2 0
Ans:
2
1 2

Case 2:
2
2 0
1 0
Ans:
1
1

Case 3:
3
2 3 0
1 3 0
1 2 0
Ans:
1
1

Case 4:
3
2 0
1 3 0
2 0
Ans:
2
1 3

Case 5:
4
2 4 0
1 0
4 0
1 3 0
Ans:
2
1 3

Case 6:
5
5 0
5 0
5 0
5 0
1 2 3 4 0
Ans:
4
1 2 3 4

Case 7:
5
2 0
1 0
5 0
5 0
3 4 0
Ans:
3
1 3 4

Let me know if any1 finds any error...
Thanks.

Edited by author 20.06.2016 22:19

If you get WA22, problem in saving minimal price of devices. If there are several popular devices, you need to display the one with the cheapest price
Try test:
a
htc
10000
b
nexus
10000
c
htc
99999
d
nexus
10000
e
htc
5000
f
nexus
10000

answer is htc (the most minimal price is 5000)

might it is very complicated but i use hash and dp to solve this problem

Segments can be with zero length

(p-1)(q-1) is euler function value of n.

See some test cases below. I hope some of them will help you.
2 5
2 3 9 2 100
1 2 5 4 100
2 1
1 5
ans:
0

5 1
100000
0
1
100000
1
4 1
5 1
ans:
0

5 1
100000
0
1
100000
1
3 1
5 1
ans:
0

5 1
100000
0
1
1
1
4 1
5 1
ans:
100000

5 1
100000
1
1
1
1
4 1
5 1
ans:
99999

3 4
1 2 2 1
1 2 2 1
1 2 2 1
2 1
3 4
ans:
0

5
1 2 1 3 2
ans: 1 2

It's strange that it has a tag "DP" as well.

You don't need to sum the branches, you need to do binary OR "|" on them.

On every step you move one level down. You have three choices to go down-left, down-right and just down (it's not always possible). So, you check which side m is on. If on the right, then we go down-right, otherwise - down-lef, if it's right below us, then we just go down

The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers.
Good luck, hope this will help!

Edited by author 13.11.2021 00:26

Edited by author 13.11.2021 00:26

I see many people solved this with graph algorithms, there is also greedy approach.

Let's build graph: u->v, if jedi u is winning v.
You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:36

there are 2 details which are not mentioned in the document.

1. number(0-9) is also the splitor of word, so word can only contained characters,a-z.
   such as A0B is 2 words.
2. Next line starts one new word, but not always starts one new sentence, such as
   this is one sentence, but
   is splited to 2 lines.

Help me!!!

WA#3:
   new word start after '\n';(e.g.  Abc'\n'new_word_here)

WA#10
   new word start after number; (e.g. 909090new_word_here)

5 rows of code to solve this

My issue was in EPS. When I changed it from 1e-5 to 1e-8 I got AC. Good luck!