Ropes solution codejam

Ropes codejam solution

For Solution

Click Here!

Two scout teams are taking part in a scouting competition. It is the finals and each team is well prepared. The game is played along a river that flows west to east. There are 4N4N trees planted along the river, with exactly 2N2N of them lined up along the north bank and 2N2N lined up along the south bank. Both teams alternate turns playing the game. Your team goes first.

On each turn, the playing team selects one tree on each bank that does not have any ropes tied to it and ties a rope between both trees, making it cross the river. Each rope that is added is placed higher than all previous ropes. The playing team scores 1 point per each previously used rope that passes below the newly added rope.

After 2N2N turns, all trees have exactly one rope tied to them, so there are no more possible plays and the game is over. The score of each team is the sum of the scores they got in all of their turns. If your team’s score is strictly greater than the opposing team’s score, your team wins. If your team’s score is less than or equal to the opposing team’s score, your team does not win.

The following animation shows a possible game with N=2N=2. Your team is represented by the color red and the other team by the color blue.

Animation of the first sample interaction

The opposing team felt confident that going second is a large advantage, so they revealed their strategy. On their turn, they choose the play that yields the maximum possible score for this turn. If multiple such plays exist, they choose one at random. This choice is generated uniformly at random, and independently for each play, for each test case and for each submission. Therefore, even if you submit exactly the same code twice, the opposing team can make different random choices.

You play TT games in total, and your team must win at least WW of them.

Input and output

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing three integers TTNN, and WW: the number of test cases, the number of turns of your team and the number of wins you need to get for your solution to be considered correct, respectively. Note that the opposing team also gets NN turns, for a total of 2N2N turns for each test case.

For each test case, your program must process NN exchanges. Each exchange represents two consecutive turns, one from your team and one from the opposing team.

For the ii⁠-⁠th exchange, you must first print a single line with two integers AiAi and BiBi and then read a single line with two integers CiCi and DiDi. This represents that in your ii⁠-⁠th turn you tied the rope between the AiAi⁠-⁠th tree from the west on the north bank and the BiBi⁠-⁠th tree from the west on the south bank. Similarly, in the opposing team’s ii⁠-⁠th turn they used the CiCi⁠-⁠th tree from the west on the north bank and the DiDi⁠-⁠th tree from the west on the south bank. Trees are indexed starting from 1.

After the NN exchanges, you must read one number that represents the result of this game. This number will be 1 if your team won, otherwise it will be 0.

The next test case starts immediately if there is one. If this was the last test case, the judge will expect no more output and will send no further input to your program. In addition, all TT test cases are always processed, regardless of whether it is already guaranteed that the threshold for correctness will or cannot be met. The threshold is only checked after correctly processing all test cases.

If the judge receives an invalidly formatted line or invalid move (like using a tree that has already been used) from your program at any moment, the judge will print a single number -1 and will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

Limits

Time limit: 90 seconds.
Memory limit: 1 GB.
T=2000T=2000.
N=50N=50.

Test Set 1 (Visible Verdict)

W=1200W=1200 (W=0.6TW=0.6⋅T).

Test Set 2 (Visible Verdict)

W=1560W=1560 (W=0.78TW=0.78⋅T).

Test Set 3 (Visible Verdict)

W=1720W=1720 (W=0.86TW=0.86⋅T).

Testing Tool

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.

Download testing tool

Sample Interaction
Judge
Solution
2 2 1
Judge provides TTNNWW. These are illustrative and do not abide by the limits of any test set.
3 2
Solution connects the 3rd tree from the west on the north bank with the 2nd tree from the west on the south bank, scoring 0.
4 1
Judge crosses the only rope, scoring 1.
1 3
Solution crosses both previous ropes, scoring 2.
2 4
Judge crosses the first two ropes and not the last one, scoring 2 more.
0
Your team lost with a score of 2-3, so judge indicates not a win.
1 1
Solution starts, scoring 0.
2 3
Judge has no way to score, so it plays something scoring 0.
3 2
Solution crosses the judge’s rope, scoring 1.
4 4
Judge plays its only option, scoring 0 again.
1
Your team won with a score of 1-0, so judge indicates a win.

Leave a Reply

Your email address will not be published. Required fields are marked *

*