11211 - Digital Logic

[little joey]

Reading the description, I feel unsure about what exactly is a legal circuit.

1. Can input lines be ignored (not connected to any gate or output line)?
2. Can two or more output lines be short circuited (have the same input line or gate)?
3. Can the two inputs of a gate be short circuited (connected to the same input line or gate, to create constants and inverters)?

The following I/O contains all three cases; is it legal?

input

Code: Select all

1
1 1 1 0
2 11 4 13 2 11 4 13 2 11 4 13 2 11 4 13 
0

output

Code: Select all

Case 1: 1
5 1 3 3
4 3 5 4

1: input lines 1 and 2 are not used.
2: output lines 1 and 4 are connected to the same input line (4).
3: both input lines of the gate are connected to the same input line (3).

[rujialiu]

little joey, the judge program outputs "Yes" for your input and output

[little joey]

Thanks. Now I have to think about an efficient way to implement my ideas...

[little joey]

That was one tough cookie... took 20+ submissions to get it under 45 seconds. Can't wait to see Rio smashing the runtime.

BTW Rujia, excellent problem set; keeps me off the street for a few days. I noticed that you yourself didn't submit the problems on UVA. Are you sure your solutions run within the time/memory requirements?

[sunny]

BTW Rujia, excellent problem set; keeps me off the street for a few days. I noticed that you yourself didn't submit the problems on UVA. Are you sure your solutions run within the time/memory requirements?

should be excellent for a solver like liitle joey but impossible for most of us.
only 3 were beyond my reach

[rujialiu]

That was one tough cookie... took 20+ submissions to get it under 45 seconds. Can't wait to see Rio smashing the runtime.

BTW Rujia, excellent problem set; keeps me off the street for a few days.

Thanks Though many of them are adapted from old contests, adapting them is quite annoying...For example, most of the original judge solution was not strong enough, so test cases are weak too. I'm very happy to see people like you trying hard to solve them. And (as you may notice), I'm ready to provide hints / clarifications for these problems.

I noticed that you yourself didn't submit the problems on UVA. Are you sure your solutions run within the time/memory requirements?

I'd answer "Yes", since the whole contest material I submitted include judge solutions.... And the timelimit is set according to it. The reason I did not submit my solution is.....

I think the first solver might be happy to see his name appears in the ranklist ALONE -- at least for a short time

anyway, i can submit the judge solution for harder problem after it is solve by at least two people. But usually they're not very fast, at least not intentionally optimized (otherwise you'll get a tighter timelimit, which would drive people crazy, hehe).

For example, all my judge solution for my tiny contest runs much slower than Rio's current best submission. That's great!

[rujialiu]

BTW Rujia, excellent problem set; keeps me off the street for a few days. I noticed that you yourself didn't submit the problems on UVA. Are you sure your solutions run within the time/memory requirements?

should be excellent for a solver like liitle joey but impossible for most of us.
only 3 were beyond my reach

Well, in my opinion, brute force problems are unlike other kinds of problems - you need to TRY! Many algorithms look silly but they work fine So don't always be expecting a fanscinating algorithm before actual coding.

and... there are 5 easier problem in the problemset: C, E, G, H, K. Try to solve them first

[little joey]

I think the first solver might be happy to see his name appears in the ranklist ALONE -- at least for a short time

anyway, i can submit the judge solution for harder problem after it is solve by at least two people. But usually they're not very fast, at least not intentionally optimized (otherwise you'll get a tighter timelimit, which would drive people crazy, hehe).

For example, all my judge solution for my tiny contest runs much slower than Rio's current best submission. That's great!

I appreciate your argument. It was just that trying to solve a problem that nobody solved yet, makes you doubt that it's solvable at all. Which I shouldn't in your case, of course
The other thing is that comparing runtimes can be a big hint for the method used. In case of this problem: the fact that your solution runs almost 3 times as fast as mine is a clear indication that I still miss something...

[baodog]

A fast solution is possible by using enough bit operations
and prunning aggresively.