Page 1 of 2
11224 - Let's swim!
Posted: Sun Jun 10, 2007 3:12 pm
by little joey
What is wrong with the following reasoning:
<DELETED>
I can't understand why this doesn't work...
Or do I have a misconception of the problem statement.
Posted: Sun Jun 10, 2007 4:10 pm
by Adrian Kuegel
In your second case, it may not be possible to place p3-th.
Note the tie breakers used for same times, and that if time differs, it has to differ by at least 1 hundredth of a second.
Posted: Sun Jun 10, 2007 4:20 pm
by little joey
Oops. Completely missed that. Thanks Adrian.
I've deleted my previous text cause it's too close to a solution.
Lane numbers
Posted: Sun Jun 10, 2007 7:30 pm
by jah
Hi do you use the lane numbers at all? This problem is kind of confusing.
Posted: Sun Jun 10, 2007 7:39 pm
by Adrian Kuegel
No, lane numbers (and how they are assigned) are not important, only thing that is important is your place in the qualification. I guess the problem contains this information just to make the solution less obvious.
Input
Posted: Sun Jun 10, 2007 8:54 pm
by jah
Hi,
Some tricky input cases would be greatly appreciated.
Thanks Adrian.
Posted: Sun Jun 10, 2007 9:40 pm
by txandi
Hi! Some critical I/O:
Input:
Code: Select all
5
9
3
2 00:10:99
1 00:11:00
4 00:10:99
5 00:10:99
6 00:10:99
7 00:10:99
8 00:10:99
9 00:10:99
10
3
2 00:10:00
1 00:10:00
4 00:10:00
5 00:10:00
6 00:10:00
7 00:10:00
8 00:10:00
9 00:11:00
10 00:11:00
10
1
2 00:10:00
3 00:10:00
4 00:10:00
5 00:10:00
6 00:10:00
7 00:10:00
8 00:10:00
9 00:10:00
10 00:10:00
10
1
2 00:10:00
3 00:10:00
4 00:10:00
5 00:10:00
6 00:10:00
7 00:10:00
8 00:11:00
9 00:11:00
10 00:11:00
10
3
2 00:10:00
1 00:10:00
4 00:10:00
5 00:10:00
6 00:10:00
7 00:10:00
8 00:10:00
9 00:10:00
10 00:10:00
Output from my AC code:
Code: Select all
Case #1:
Gustavo should be #2 during the qualification to achieve position #2 in the final.
Case #2:
Gustavo should be #8 during the qualification to achieve position #3 in the final.
Case #3:
Gustavo should be #1 during the qualification to achieve position #1 in the final.
Case #4:
Gustavo should be #7 during the qualification to achieve position #1 in the final.
Case #5:
Gustavo should be #3 during the qualification to achieve position #3 in the final.
Posted: Sun Jun 10, 2007 10:08 pm
by jah
Thanks txandi, that helped. (Silly mistake).
still WA
Posted: Wed Jul 11, 2007 7:42 am
by TimeString
Hi, I get wrong answer, but I don't know why. Can someone help me??
Here is my solution:
- Scan all possible times, i.e., from 00:01:00 to 09:59:99.
- Exam in this time, how many competitors will defeat Gustavo in the qualification phase and how many competitors will defeat Gustavo in the final phase.
- To decide how many competitors defeat Gustavo in the first phase, I count how many people swim faster than Gustavo, plus I also count in who swims as fast as Gustavo but his rank is better than Gustavo.
- Then accroding to who beat Gustavo in the first phase, if one's rank is better than Gustavo, he can still beat Gustavo in the second phase.
- Now in a critical time, I know X people defeat Gustavo in the qualification and Y people defeat him in the second phase. If X<=7 and Y<=2, it is a possible answer that Gustavo should be #(X+1) in the first phase and #(Y+1) in the second phase. Choose the best answer which contains biggest X.
Is there anything wrong?? In fact, I don't totally understand the description of the problem.
Posted: Wed Jul 11, 2007 4:52 pm
by Darko
When you say "scan all possible times", do you mean "all times that Gustavo can have"? If "yes", then you are not scanning all of them, he can swim faster. What if all of the others swim 01:00 and have better rank than Gustavo?
I get Wa.
Posted: Wed Jul 18, 2007 4:41 am
by mario
My code gives me WA. It works perfectly with the already posted tricky inputs. I don't know why I keep getting WA. Is there anything with the input output style that could give problem? Or can anyone give me other special inputs that I should try? I am out of ideas. Thanks.
Posted: Wed Jul 18, 2007 7:27 am
by Darko
I couldn't get it during the contest and I never figured out why. So, after the contest, I convinced myself my solution should work (like you probably did) and - recoded it. And got AC. I still have no idea what was wrong the first time around.
Posted: Thu Jul 19, 2007 2:29 am
by mario
Recode? You probably fixed something different by accident when you recoded and that's probably why you got AC. But if I write the same code again, I might not run lucky enough to fix any detail by accident. I did recode some stuff, but I can only think there is something wrong with my logic. Some critical inputs could really be helpful. Thanks for the help.
Posted: Thu Jul 19, 2007 7:08 am
by Darko
That was exactly my point, let me restate it - if you are certain your approach should work, and you can't find the mistake, recode it. If you are not that sure about the logic, think about the reason that makes you think it should not work.
We really can't tell if your approach is right or wrong if we don't know what it actually is.
trick input
Posted: Thu Jul 19, 2007 2:59 pm
by TimeString
Hey, i got AC now ^^
My previous program gives wrong output for this case:
Code: Select all
1
8
1
8 0:01:01
7 0:01:02
6 0:01:03
5 0:01:04
4 0:01:05
3 0:01:06
2 0:01:07
The correct output is:
Code: Select all
Case #1:
Gustavo should be #8 during the qualification to achieve position #1 in the final.
Hope it helps.
P.S. What Darko said is helpful!! Thanks!!