ico-arrow-big-left

TCO19 Marathon Round 2

Key Information

Register
Submit
The challenge is finished.
Show Deadlines

Challenge Overview

Important Links

  • Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores. 
  • Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution etc.  

Problem statement

You are part of a group that is running a programming competition. As participants are expected to be of varied ability levels, it is run as a team event, with the teams determined by the event organizers. You have been put in charge of dividing the individuals into teams.

Each participant has a certain, theoretical, skill level. Unfortunately, you have no way of directly knowing what is the skill level of each person. What you do know, however, is some information about the results of several previous contests. In all previous contests, those that participated were each ranked from first to last. Each competitor carefully kept track of how many times they finished ahead of any other competitor, and you have been furnished with that informaion.

Your job is to arrange the N competitors into M teams, not necessarily of equal size. (But each team must have at least one member.)

Test Case Generation

  • N is selected between 50 and 200, inclusive.
  • M is selected between 5 and 20, inclusive.
  • The skill level of each participant is chosen between 100 and 1000, inclusive.
  • A number of contests are determined, between 3 and 50, inclusive.
  • For each contest, the performance of each contestant is chosen, uniformly at random, in the range [0, skill).
  • The number of times each competitor outperformed each other competitor is tabulated to form the problem input.
    • Note that ties, while rare, are possible. In such a case, neither competitor will be recorded as having outperformed the other.

Input / Output

Your code will receive as input the following values:

  • M, the number of teams that should be created.
  • N, the total number of competitors
  • N lines indicating how many times each competitor has finished ahead of each other competitor.
    • Each line is a space-separated list of non-negative integers.
    • The k-th number on line i is the number of times that the i-th competitor placed ahead of the k-th competitor (0-based)

Your code should write to output the following:

  • On the first line, the number of lines that will follow (which should be the same as M given as input)
  • Each line will represent the competitors to be placed on a team.
  • Each of the subsequent lines should be a space-separated list of the indices of which competitors will be on that team.

The number of teams should be M. Each team must have at least one member. Each competitor should be part of exactly one team. Any output that does not meet these requirements will receive a score of -1.0. Illegal output or values or invalid competitor indices will likewise result in scoring -1.0.

Scoring

The overall strength of each team is calculated by the following:
  • The skill levels of all team members are sorted in ascending order.
  • The sorted skill levels are weighted by their 1-based ordinal position. (That is, the weakest team member is weighted by 1, next weakest is weighted by 2, etc.)
  • The weighted skill levels are summed and divided by the sum of (1...teamSize), thus computing the weighted average skill level of the team. This is the team skill level.

We find the difference in skill level between the strongest team and the weakest team. Your raw score for each test case will be calculated as 1000 / (1 + difference).

The relative score for each test case is calculated as YOURS / BEST where BEST is the best score (highest) anyone got for that case, and YOURS is your score on that case. On any test case where your raw score was -1.0, your relative score will be 0.0.

Overall score for submission is the sum of relative scores across all test cases, scaled to 100.0.

Notes

  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
  • There are 10 example test cases and 100 full submissions (provisional) test cases. There will be 2000 test cases in the final testing.
  • The match is rated.

Languages Supported

C#, Java, C++ and Python

Submission Format 

Your submission must be a single ZIP file not larger than 500 MB, with your Source Code only:
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as ContestOrganizer. <appropriate extension> 

- Java Source Code - ContestOrganizer.java
- C++ Source Code - ContestOrganizer.cpp
- Python3.6 Source Code - ContestOrganizer.py
- C# Source Code - ContestOrganizer.cs

Sample Submissions

Tools

Submission format and an offline tester are available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

Downloads

Helpful information

Offline Tester / Visualizer

In order to use the offline tester / visualizer tool for testing your solution locally, you'll have to modify your solution by adding the main method that interacts with the tester / visualizer via reading data from standard input and writing data to standard output. As long as you do not change the implementation of method findSolution, this doesn't affect the way your solution works when submitted to our server.

Here are example solutions for different languages, modified to be executed with visualizer. They all implement the same approach: divide the competitors, in order, into teams.
To run the tester with your solution, you should run:
java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\solution.exe" or "~/topcoder/solution". In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder Solution".

Additionally, you can use the following options:
  • -novis : Turn off visualization.
Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.

Payments

Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.