Sorting deviceProblem code: MX |
All submissions for this problem are available.
You work for a large company, and your job is to design sorting devices. Devices are built from:
- n inputs,
- n outputs,
- gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,
- connecting wires.
You are competing in a bid for a Bytelandian Ministry of Information contract to design the smallest possible device (in terms of the number of gates) which sorts any input. Each device will go through a rigorous test process on a number of data sets. However, through some Good Friends in High Places you have managed to acquire some additional information concerning the exact data sets (permutations) your device will be tested on. Make use of this, and of course your superior programming skills, to win the bid!
Input
First, two numbers, 2 <= n <= 20, 1 <= k <= 1000, the number of inputs and the number of different permutations for which your device will be tested. The next k lines contain permutations of the numbers 1 .. n.
Output
First, output p, the number of gates in your device (0 p 106). The next p lines should contain definitions of the gates used, in the form of a pair of integers, xi,yi, and exactly one of the strings "min" or "max". To be able to use the output of a gate as the input of a subsequent gate, we use the following convention. First of all, the range for inputs xi and yi is as follows: 1 <= xi,yi < n+p. The output of the i-th gate is assumed to be input n+i.
Finally, a sequence of exactly n integers in the range 1..n+p should follow, describing which of the "inputs" should be hard-wired to successive outputs of the device.
Scoring
If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect. Otherwise, you will score p penalty points for each test case solved.
Example
Input:
3 2
1 2 3
1 3 2
Output:
2
2 3 min
2 3 max
1 4 5
Score:
0.5
| Author: | admin |
| Date Added: | 15-01-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
This problem statement also
This problem statement also has missing inequality signs (first sentence in the Output section).
Would it be correct to say
Would it be correct to say that the example output is not the best possible output for the example input, because the score is 0.5 (not 1) ("Each contest will have one min/max tie breaker problem, where the best solution will receive one point ...", http://www.codechef.com/FEB10)?
The sample output may or may
The sample output may or may not be optimal, but the score in your output and the score for the problem are different. The lowest possible score achieved in the output is assigned a problem score of 1; the rest are proportional.
Might I ask how the inputs
Might I ask how the inputs were generated? Are n, k chosen uniformly, and all permutations random?
n,k are chosen by choosing,
n,k are chosen by choosing, permuations are random
I don't understand, If we
I don't understand, If we don't have to print the sorted numbers, what is the use of giving different permutations of the inputs?
All we need is 'n' to print the gate pattern.
Is this bit of information correct or have I misunderstood?
@Omkar Where the problem says
@Omkar Where the problem says "Make use of this", they mean to focus on producing a device that works for the permutations you are given. This generally requires less gates than a device that works for every possible permutation. For example, the device represented by the sample output works for each of the permutations provided but does not work for every possible permutation. The less gates the device has, the higher your score.
+1
+1
Is it possible I get Wrong
Is it possible I get Wrong Answer when my program runs more than 1 second?
If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect.
It says nothing about TLE.
@Mislav The statement you
@Mislav The statement you quoted applies when your program exits successfully within the time limit. Otherwise, you will get Compile Error, Run-time Error or Time Limit Exceeeded as usual.
Can I ask are there test
Can I ask are there test cases for which answer doesn't exist?
Not in official test cases, i mean generally...
What does p penalty point for
What does p penalty point for each test case mean? I can see the best point so as 157. Does this mean he has only used 157 gates on an average for all test cases?
Yes.
Yes.
what is the meaning of this
what is the meaning of this line?
gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,
the meaning is that: there
the meaning is that:
there are gates,
gates have two inputs
gates send either minimum or maximum of inputs to output (depends on gate)
sorry for this too trivial a
sorry for this too trivial a doubt....Each gate is characterised by xi, yi and min/max. What exactly are xi,yi? and could someone please explain how thhis is sorting..
thanks in advance
m newbie hereits my first
m newbie here
its my first time
can u please tell me how to take input
whether as .txt file or somhw else???
smbdy please tell me what xi
smbdy please tell me what xi and yi are in the above problem.....
It would be helpful if the
It would be helpful if the explaination of the output os also given
There are (n + p) quantities
There are (n + p) quantities called "inputs". Those labelled 1..n are actual inputs to the device. The "input" labelled (n + i) is the output of the ith gate. Each gate is characterised by two numbers, which are the labels of the "inputs" that the gate's inputs are connected to, and the string "min" or "max", describing what the gate does. Finally, the outputs are characterised by the labels of the "inputs" they are connected to.
If you trace the operation of the device given in the sample, with, for example, input 1 being 1, input 2 being 3 and input 3 being 2, you will find that the outputs are 1, 2 and 3, in that order, i.e. they are sorted. The device might not work for all inputs; it only needs to work for the inputs given; this may allow you to use less gates, which is your aim in this problem.