Register
Submit a solution
The challenge is finished.

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

Your task is to construct a large number T using the least number of steps. You begin with two distinct numbers Num0 and Num1. At each step of the process you can create a new number by applying an operation on two existing numbers (can be the same). The operations are addition (+), subtraction (-), multiplication (*) and integer division (/).

 

Here is an example solution for seed=1, Num0=19, Num1=25 and T=1048575. This solution uses 7 steps:
  • Num 0: 19
  • Num 1: 25
  • Num 2: 6 = 25 - 19 (1 - 0)
  • Num 3: 1 = 25 / 19 (1 / 0)
  • Num 4: 31 = 25 + 6 (1 + 2)
  • Num 5: 32 = 31 + 1 (4 + 3)
  • Num 6: 1024 = 32 * 32 (5 * 5)
  • Num 7: 1048576 = 1024 * 1024 (6 * 6)
  • Num 8: 1048575 = 1048576 - 1 (7 - 3)
The commands output by the program are shown in brackets. These are based on ids of the generated numbers. Note the integer division for Num 3 and the reuse of the same ids for Num 6 and Num 7.

Implementation

Your code will receive as input the following values, each on a separate line:
  • Num0, the first number in the sequence.
  • Num1, the second number in the sequence.
  • T, the target number that needs to be reached.
Your code should write to output the following:
  • On the first line, the number of steps S used to compute T.
  • S lines, where each line desribes a single computation. This should be formatted as "[id1] [op] [id2]" (without the square brackets). id1 and op should be separated by a single space, similarly for op and id2. id1 and id2 are zero-based indices of the two numbers used in the computation. op is a single character representing the operator used: addition (+), subtraction (-), multiplication (*) and integer division (/).���

Scoring

Your raw score for a test case is the total number of steps you used to reach T. Note that only your last generated value will be checked. If your return was invalid then your raw score on this test case will be -1. Possible reasons include:
  • Not reaching the target number T.
  • Using more than 10,000 steps.
  • Generating a number exceeding 1,000 decimal digits (including the minus sign).
  • Division by 0.
  • Using incorrectly formatted operations.
  • Using invalid ids.
If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the smallest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalised to 100.

Test Case Generation

Please look at the visualizer source code for the exact details about test case generation. Each test case is generated as follows:
  • Num0 and Num1 are distinct numbers, randomly chosen between 1 and 999, inclusive.
  • Generate the number of digits D in the target number, randomly chosen between 4 and 100, inclusive.
  • Generate a random target number T containing D decimal digits.

Notes

  • You may need to use an arbitrary precision integer library. In Java, you can use the java.math.BigInteger class. Python3 supports large integers naturally. In C# you can use the System.Numerics.BigInteger class. For C++ you can use the following publicly available libraries at your own risk: https://mattmccutchen.net/bigint/ and https://github.com/kokke/tiny-bignum-c.
  • Although it is possible to reach every number T in a finite number of steps, here you cannot use more than 10,000 steps.
  • You cannot generate a number exceeding 1,000 decimal digits (including the minus sign).
  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • The compilation time limit is 30 seconds.
  • There are 10 example test cases and 100 full submission (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 NumberCreator.<appropriate extension>

- Java Source Code - NumberCreator.java
- C++ Source Code - NumberCreator.cpp
- Python3.6 Source Code - NumberCreator.py
- C# Source Code - NumberCreator.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.

Here are example solutions for different languages, modified to be executed with the visualizer. 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:
  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -debug. Print debug information.
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.