ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2071. Juice Cocktails

WA 23 any ideas?
Posted by Nodir NAZAROV [TUIT-Karshi] 8 Dec 2015 08:58
I didn't find any case that my algorithm fails.

Please give me test cases for test #23, I see there are a lot of WA#23.
Re: WA 23 any ideas?
Posted by Jane Soboleva (SumNU) 9 Dec 2015 12:48
I guess, it has to do with something when certain types of drinks are not present.

Initially, i only analyzed one possible permutation, and got WA15. Then, i added another one to check, and got WA31. I threw in 4 more to check before giving answer, and got WA95. I probably missed just a few more unique cases, though i never figured out what was the problem.

Well, in the end, i stopped bothering and just checked all 7! permutations. It's a lot more excessive than just checking a few selected, but will guarantee AC. You should do that too, probably.
Re: WA 23 any ideas?
Posted by Nodir NAZAROV [TUIT-Karshi] 9 Dec 2015 20:56
Thanks Jane for your advice!

It's obvious that possible number of pourings are 1 to 5. So I've put all the conditions that requires certain number of pourings. If these conditions are set well you don't have to check all the 7! permutations (I think that's quicker and easier solution, maybe I'm wrong).
Re: WA 23 any ideas?
Posted by Jane Soboleva (SumNU) 9 Dec 2015 23:57
No problem~
Also, the worst case is 4, see
A AB ABP AP P BP B
1 pouring for A, 1 pouring for P, 2 pourings for B, if all present.
That's the only one i checked when i got WA15.
I guess, at that point, my fault was something like... if AP and P aren't present, then we don't interrupt our pouring, and B is 1 pouring then.
Or maybe that wasn't the thing... anyway i fixed that in my final version.
Re: WA 23 any ideas?
Posted by Nodir NAZAROV [TUIT-Karshi] 11 Dec 2015 20:54
hey Jane,

How come the worst case is 4, not 5? If all types are present then it should be as following (You cannot pour P over B, hence 1 A, 2 B, and 2 P):

12345
A....
AB...
ABP..
A.P..
..P..
...BP
...B.

Please correct me if I'm wrong.
Re: WA 23 any ideas?
Posted by Jane Soboleva (SumNU) 11 Dec 2015 23:43
Um, i just listed pourings in an order of a growing number of them, a proper order is, of course, 1 for A, 2 for B and 1 for P. As for your table, i'm not sure why you put that P to the right.
A....
AB...
ABP..
A.P..
..P..
..PB.
...B.
I mean, PB doesn't mean we pour P first, but if we represent it _this_ way...

Add:
I'm not sure if above was proper explanation, maybe i'll explain it like this:
in A AB ABP AP P BP B, it goes
1. Pour A in 1-4.
2. Pour B in 2-3 and 6-7
3. Pour P in 3-6.

Oh, and you can email me if you want to...

Edited by author 12.12.2015 00:31
Re: WA 23 any ideas?
Posted by Nodir NAZAROV [TUIT-Karshi] 12 Dec 2015 10:09
Thanks a lot. That explains well. Actually I thought the order should be maintained, probably most of the WA#23 because of wrong understanding of the problem statement.
Re: WA 23 any ideas?
Posted by Jane Soboleva (SumNU) 12 Dec 2015 14:15
Good job on finally making it~

Edited by author 15.12.2015 01:37