Hello! I have a question. Can somebody give me some "difficults" test cases for problem E? I have Wrong Answear on test 11 and I have no ideea why. Thank you very much
I don't know how you solved the problem, but in my solution there was no need for 64-bit integers(because i didn't keep the numbers in any variables). Anyway, i'm not very sure if my solution is right, this is why i am asking for some tests:) Thx
I cant figure what is wrong with my D :/, tried a lot of tests here and all of them are ok, does anyone knows the test number 4? (its giving me PE, but I guess its WA)
"It is guaranteed that the set of breaks is correct, i.e. there is some order of the given breaks that each next break divides exactly one part of the bar into two non-empty parts.
Output
Output n + 1 numbers — areas of the resulting parts in the increasing order."
N is at least 1, and you cant break it on empty parts!
Can anybody explain how problem E is solved please?
I'm using DP. The parameters are (index, player1 result, player2 result, nTurns for player1, nTurns for player2)
but I'm memorizing only on index and player1 result, as the rest can be calculated through those two. Player1 result is too large so i'm memorizing in map. Sure that gives me TLE on test case 14.
Try DP: d[nTurns1][nTurns2] = maximum_possible_sum. Note that we can rid of the other parameters: at current step d[nTurns1][nTurns2] we select whom to give (nTurns1+nTurns2)-th digit of the number. It's easy to understand that following strategy doesn't depend on current digits, so we can add 10^{n-nTurns1} * s[nTurns1+nTurns2] to the value d[nTurns1+1][nTurns2] to best answer if we give current digit to Homer. Similar formula is in the case of Marge. Select maximum of these two values to obtain value for current d[nTurns1][nTurns2].
~
The text say, Breaks are given in arbitrary order.
will some test case like this?
2 2 2
0 1 1 1
1 0 1 2
I make one more for loop to calculate by force, then i got an Accept.
3
000999
?
The input example:
1234
The total is: 12 + 34?
Thx:)
"It is guaranteed that the set of breaks is correct, i.e. there is some order of the given breaks that each next break divides exactly one part of the bar into two non-empty parts.
Output n + 1 numbers — areas of the resulting parts in the increasing order."
N is at least 1, and you cant break it on empty parts!
I'm using DP. The parameters are (index, player1 result, player2 result, nTurns for player1, nTurns for player2)
but I'm memorizing only on index and player1 result, as the rest can be calculated through those two. Player1 result is too large so i'm memorizing in map. Sure that gives me TLE on test case 14.
What can I do? Thanks very much.