11224 - Let's swim!

[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.

[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.

[little joey]

Oops. Completely missed that. Thanks Adrian.

I've deleted my previous text cause it's too close to a solution.

[jah]

Hi do you use the lane numbers at all? This problem is kind of confusing.

[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.

[jah]

Hi,

Some tricky input cases would be greatly appreciated.

Thanks Adrian.

[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.

[jah]

Thanks txandi, that helped. (Silly mistake).

[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.

[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?

[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.

[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.

[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.

[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.

[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!!