10435 - Compare Directories

ReiVaX18 · Post by **ReiVaX18** » Mon Mar 29, 2004 4:26 pm

I tried to do this problem that only 5 people have done so far and I am getting WA over and over. I made it in C++ and in Java, and both pass the public test but get WA. Could someone please give me any hint on where may I be making a mistake or some other input/output test to check?

I think I can be making an error by misunderstanding this two sentences, especially the last one:

"The common File Objects of any two directories to compare are in the same order. You must use longest common subsequences of the file names in the two directory content to get common file names."

If someone can explain me what they mean exactly I would be very pleased.

Thank you in advance,

Xavi

Per · Post by **Per** » Sat Apr 10, 2004 2:52 pm

I'm also getting WA. It's a bit worrying that the problem has no judge program, since a longest common subsequence is not necessarily unique. Could someone of the few AC folks check these cases?

Code: Select all

10728j2002
/CDrive
ACMHelper <DIR> 2
    booo <DIR> 0
    acmhelper.exe 100
/tmp
Helper <DIR> 2
    acmhelper.exe 100
    booo <DIR> 0
10asdhj2002
/CDrive
ACMHelper <DIR> 2
    acmhelper.exe 100
    booo <DIR> 0
/tmp
Helper <DIR> 2
    booo <DIR> 0
    acmhelper.exe 100
13748date7312894
/dir1/
BaseDir <DIR> 5
                DirB <DIR> 2
                File00 0
                File01 1
        Trash 33
        FileA 2347823
        DirC <DIR> 1
                SubFile 0
        FileQ 1
/dir2
BaseDir <DIR> 5
        DirB <DIR> 0
        File123123 234
        DirC <DIR> 0
        FileQ 3
        FileA 123

My output is:

Code: Select all

==== Begin of Comparison ====
Transaction #1 : Date 10728j2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    "/CDrive/ACMHelper" lacks of following file(s)
        booo <DIR> 0 object(s)
    "/tmp/Helper" lacks of following file(s)
        booo <DIR> 0 object(s)
Difference(s) encountered.

Transaction #2 : Date 10asdhj2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    No difference.
    "/CDrive/ACMHelper" lacks of following file(s)
        acmhelper.exe 100 byte(s)
    "/tmp/Helper" lacks of following file(s)
        acmhelper.exe 100 byte(s)
Difference(s) encountered.

Transaction #3 : Date 13748date7312894
Comparing "/dir1/BaseDir" with "/dir2/BaseDir".
    Comparing "/dir1/BaseDir/DirB" with "/dir2/BaseDir/DirB".
    Totally different.
    Comparing "/dir1/BaseDir/DirC" with "/dir2/BaseDir/DirC".
    Totally different.
    File size mismatch : "/dir1/BaseDir/FileQ (1)" and "/dir2/BaseDir/FileQ (3)".
    "/dir1/BaseDir" lacks of following file(s)
        File123123 234 byte(s)
        FileA 123 byte(s)
    "/dir2/BaseDir" lacks of following file(s)
        Trash 33 byte(s)
        FileA 2347823 byte(s)
Difference(s) encountered.
==== End of Comparison ====

ReiVaX18 · Post by **ReiVaX18** » Sun Apr 11, 2004 6:41 pm

my output is:

Code: Select all

==== Begin of Comparison ====
Transaction #1 : Date 10728j2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    No difference.
No difference.

Transaction #2 : Date 10asdhj2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    No difference.
No difference.

Transaction #3 : Date 13748date7312894
Comparing "/dir1//BaseDir" with "/dir2/BaseDir".
    Comparing "/dir1//BaseDir/DirB" with "/dir2/BaseDir/DirB".
    Totally different.
    Comparing "/dir1//BaseDir/DirC" with "/dir2/BaseDir/DirC".
    Totally different.
    File size mismatch : "/dir1//BaseDir/FileA (2347823)" and "/dir2/BaseDir/FileA (123)".
    File size mismatch : "/dir1//BaseDir/FileQ (1)" and "/dir2/BaseDir/FileQ (3)".
    "/dir1//BaseDir" lacks of following file(s)
        File123123 234 byte(s)
    "/dir2/BaseDir" lacks of following file(s)
        Trash 33 byte(s)
Difference(s) encountered.

also, I don't understand the longest common subsequence thing, as the test considers "p0.htm" different to "p0.html"

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Apr 13, 2004 12:08 pm

Your test cases revealed a bug in my solution: when both directories are empty, I would compare them and print: Totally different.
I corrected my program, but now it got WA !!!
My current output for your input is:

Code: Select all

==== Begin of Comparison ====
Transaction #1 : Date 10728j2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    "/CDrive/ACMHelper" lacks of following file(s)
        booo <DIR> 0 object(s)
    "/tmp/Helper" lacks of following file(s)
        booo <DIR> 0 object(s)
Difference(s) encountered.

Transaction #2 : Date 10asdhj2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    No difference.
    "/CDrive/ACMHelper" lacks of following file(s)
        acmhelper.exe 100 byte(s)
    "/tmp/Helper" lacks of following file(s)
        acmhelper.exe 100 byte(s)
Difference(s) encountered.

Transaction #3 : Date 13748date7312894
Comparing "/dir1//BaseDir" with "/dir2/BaseDir".
    Comparing "/dir1//BaseDir/DirB" with "/dir2/BaseDir/DirB".
    Totally different.
    Comparing "/dir1//BaseDir/DirC" with "/dir2/BaseDir/DirC".
    Totally different.
    File size mismatch : "/dir1//BaseDir/FileQ (1)" and "/dir2/BaseDir/FileQ (3)".
    "/dir1//BaseDir" lacks of following file(s)
        File123123 234 byte(s)
        FileA 123 byte(s)
    "/dir2/BaseDir" lacks of following file(s)
        Trash 33 byte(s)
        FileA 2347823 byte(s)
Difference(s) encountered.
==== End of Comparison ====

For the first two test cases there are two solutions; but in the judge input there is always only one solution (I checked it, and my program would have terminated with division by zero).
So perhaps try to print totally different in the case of two empty directories, and if you get Accepted then, probably the judge solution is wrong.

Per · Post by **Per** » Tue Apr 13, 2004 1:25 pm

Ah, that was it. Two empty directories should be considered totally different (the logic behind this could definitely be discussed). Funny, I thought I had tried that (involuntary, and later realised it was a mistake). Thanks!

And it seems there are no trailing slashes in the judge input (I noticed you print double slashes sometimes). I tried both versions, and both got AC.

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Apr 13, 2004 1:36 pm

I think there is no logic behind it. It is certainly a bug.
I will write an email to the problemsetter; if he wanted it like this, he should clarify this in the problem description.

ReiVaX18 · Post by **ReiVaX18** » Thu Apr 15, 2004 5:44 pm

I finally got Accepted P.E.

I was comparing all the common subdirs and after reporting file size mismatch (I thougth they wanted this by this way as the problem says: "If both have a common directory descend in that directory, with `tab'+1 and start comparing." so I searched for common dirs before searching for size mismatches) and I have not used longest common subsequence in the code so any clue why they mention it? I'm now searching for the p.e. ...

ReiVaX18 · Post by **ReiVaX18** » Sat Apr 17, 2004 4:12 pm

Also I want to say that my AC prog gives different output to this case, so if someone is trying to do this problem don't try to get same output to this case (cases in the judge have the common FileObjects in the same order)

Code: Select all

==== Begin of Comparison ====
Transaction #1 : Date 10728j2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    Totally different.
Difference(s) encountered.

Transaction #2 : Date 10asdhj2002
Comparing "/CDrive/ACMHelper" with "/tmp/Helper".
    Comparing "/CDrive/ACMHelper/booo" with "/tmp/Helper/booo".
    Totally different.
Difference(s) encountered.

Transaction #3 : Date 13748date7312894
Comparing "/dir1//BaseDir" with "/dir2/BaseDir".
    Comparing "/dir1//BaseDir/DirB" with "/dir2/BaseDir/DirB".
    Totally different.
    File size mismatch : "/dir1//BaseDir/FileA (2347823)" and "/dir2/BaseDir/FileA (123)".
    Comparing "/dir1//BaseDir/DirC" with "/dir2/BaseDir/DirC".
    Totally different.
    File size mismatch : "/dir1//BaseDir/FileQ (1)" and "/dir2/BaseDir/FileQ (3)".
    "/dir1//BaseDir" lacks of following file(s)
        File123123 234 byte(s)
    "/dir2/BaseDir" lacks of following file(s)
        Trash 33 byte(s)
Difference(s) encountered.
==== End of Comparison ====

The difference is because I search each FileObject in path1 to see if it is in path2 from the beginning and not supposing they are ordered

Moha · Post by **Moha** » Sat Oct 08, 2005 6:09 pm

I think this is impossible to use LCS in this problem, because as stated in problem definition the maximum size of a directory can be 65,000 so LCS become TLE here.

This is my question, according to this calculation and other posts in this topic why problem setter insist to use LCS on this problem?

ReiVaX18 · Post by **ReiVaX18** » Sun Oct 09, 2005 3:12 pm

I did not implement the LCS thing in this problem, I just ignored the sentence "You must use longest common subsequences of the file names in the two directory content to get common file names.". I don't know why the problemsetter put it in the problem description.

brianfry713 · Post by **brianfry713** » Thu Jan 31, 2013 1:38 am

Ignore all of the I/O in this thread. My AC program would return a RE if any of those cases were present, where two common objects are out of order. From the problem statement: "The common File Objects of any two directories to compare are in the same order".

OJ Board

10435 - Compare Directories

10435 - Compare Directories

use LCS or not? that`s the question!!

Re: 10435 - Compare Directories