Page 1 of 2

502 - DEL command

Posted: Wed Jun 12, 2002 10:54 am
by Andrey Popyk
How to solve it without very huge full search?

Posted: Thu Jun 13, 2002 8:26 am
by wyvmak
well, i'm not sure if very huge full search. but i applied the following idea: try to get the answer from the input, rather than trying the answer to match the input. ie. get a pattern from the deleted files, i get the 'tightest' possible rule, then i apply this rule to the files to be kept, if it would delete some kept files, that means there's no answer. coz the 'tightest' rule should differentiate the files best already. you cannot find a better way to differentiate the two sets of files.

Posted: Sun Jul 07, 2002 7:50 pm
by Caesum
Can anyone supply some more samples for this ? With the following input:
7

-BP.EXE
-BPC.EXE
+TURBO.EXE

-BP.EXE
-BPC.EXE
+TURBO.EXE

-blah.exe
-clay.exe
+bedh.exe

-p.

+BP.EXE
+BPC.EXE
-TURBO.EXE

-BP.EXE
-BPC.EXE
-TURBO.EXE

-BP.EXE
-BPC.EXE
-TURBO.EXE
-TURBO.EXP
My program gives the following output:
DEL BP*.EXE

DEL BP*.EXE

DEL ?la?.exe

DEL p.

DEL TURBO.EXE

DEL ??*.EXE

DEL ??*.EX?
which looks reasonable.......

Posted: Mon Jul 08, 2002 8:12 am
by wyvmak
what about:

-ABC.EXE
-ADC.EXE
-BCD.EXE
+ABCD.EXE
+AB.EXE

Posted: Mon Jul 08, 2002 7:18 pm
by Caesum
DEL ???.EXE

Posted: Mon Jul 08, 2002 9:00 pm
by xenon
Did you consider:

Code: Select all

-BP.EXE
-BPC.EXE
-BPTEXT
+TURBO.EXE
I'm solving the problem this moment, but I just realised this is valid input.

Posted: Mon Jul 08, 2002 9:03 pm
by Caesum
DEL BP*.*

I give up

Posted: Tue Jul 09, 2002 12:44 am
by xenon
Been submitting solutions for a couple of hours now, and still WA.
I give up :oops:

Posted: Tue Jul 09, 2002 12:56 am
by Caesum
Theres something we are not seeing here I think :) I noticed Picard just submitted an ok solution :evil:

Posted: Tue Jul 09, 2002 2:24 am
by Picard
i just resubmited my earlier solution because found some bugs with the inputs in this topic. (although it was accepted earlier)
i get the same outputs as you for these inputs. i don't really know what could be the trick to be accepted. i'am too tired to understand my own algorithm... :oops:

Posted: Tue Jul 09, 2002 4:51 pm
by xenon
Maybe the wildcard should be as general as possible (although that is not stated in the problem description). So for

Code: Select all

-BP.EXE
-BPC.EXE
+TURBO.EXE
the command should be DEL ?P*.*, as in the example, and not DEL BP*.EXE, as both our programs produce.

If that's the case, I think the discription really is wrong and should be restated.

I'm not going to adjust my program to do this (this would mean rewriting it, I fear), unless it's certain that this causes the WAs.

Happy hunting,
-xenon

Posted: Tue Jul 09, 2002 5:07 pm
by Picard
i use DEL BP*.EXE too. the same approach: first build the "tightest" rule, then check for the files kept.
btw the problem has special correction program, i would expect if it's not impossible any good wildcard should be accepted.

Posted: Tue Jul 09, 2002 6:01 pm
by xenon
Picard: so your program produces DEL BP*.EXE and gets accepted. Well, that's a great relief.
Could you please confirm that the program gives DEL AB?. in both cases:

Code: Select all

2

-ABC
-ABD
+ACC
+ACD

-ABC.
-ABD.
+ACC.
+ACD.
And not DEL AB? in either the first or the second case? It would be a great relief too. :lol:

Posted: Tue Jul 09, 2002 6:17 pm
by Picard
both cases DEL AB?.
(but i think DEL AB? would be correct too)

Finally AC!

Posted: Tue Jul 09, 2002 8:40 pm
by xenon
I just got accepted!
It was my keepfile-checker that was erronious.
The program gave incorrect answers on all of the following cases:

Code: Select all

8

-A
-AA
-AAA
+AAAA

-AB
-AA
+AAAA

-AB
-BB
+ABAA

-X.A
-X.AA
+X.AAA

-X.AB
-X.AA
+X.AAA

-X.AB
-X.BB
+X.ABA

-X.A
-X.AA
+X

-X.AA
-X.AAA
+X.A
Once I fixed them all, sweet AC was there. Steam must be coming from the Judge's ears (and mine :wink: ).

The answers are obvious, so I don't give them :lol:

Happy hunting,
-xenon