909 - The BitPack Data Compression Problem
Moderator: Board moderators
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
909 - The BitPack Data Compression Problem
I seem to be the only one who can't solve this problem. The 128 byte is useless, right? There is never a reason to use it.
If only I had as much free time as I did in college...
-
- New poster
- Posts: 24
- Joined: Sun Nov 12, 2006 3:38 pm
I have some (basic) questions regarding 909:
- Is there a maximum input size?
- The input and output must be made using stdin / stdout, right? Because the problem says "The output file will consist of a file with compressed content."
(i'm new to this site, and as far as i know we're only allowed to use the standard input and output)
- Is there a maximum input size?
- The input and output must be made using stdin / stdout, right? Because the problem says "The output file will consist of a file with compressed content."
(i'm new to this site, and as far as i know we're only allowed to use the standard input and output)
judging by the runtimes of the accepted solutions, the input should be fairly small.
I don't know why I can't get AC on this problem. I just did DP, so it should be right. I never output 128. There might be problem with the judge I/O.
I also wrote another program to do the data decompression and checked that it can always recover my input.
Here's the main part of my code:
After fixing the I/O problems, I still can't get AC 
I don't know why I can't get AC on this problem. I just did DP, so it should be right. I never output 128. There might be problem with the judge I/O.
I also wrote another program to do the data decompression and checked that it can always recover my input.
Here's the main part of my code:
Code: Select all
int F[maxn],P[maxn],Q[maxn],s[maxn],n;
void print(int i) {
if(i==n) return;
if(Q[i]==0) {
putchar(P[i]+128);
putchar(s[i]);
print(i+P[i]+1);
}
else {
putchar(P[i]);
FOR(k,i,i+P[i]) putchar(s[k]);
print(i+P[i]+1);
}
}
int f(int i) {
if(i==n) return 0;
if(F[i]==-1) {
int j;
F[i] = inf;
for(j=1; j<n && j<=127 && s[i+j]==s[i]; j++)
if(f(i+j+1)+2<F[i])
F[i]=f(i+j+1)+2,P[i]=j,Q[i]=0;
for(j=0; j<n && j<=127; j++)
if(f(i+j+1)+j+2<F[i])
F[i]=f(i+j+1)+j+2,P[i]=j,Q[i]=1;
}
return F[i];
}
int main(){
int c;
n=0;
while(1) {
c=getchar();
if(c==EOF) {
break;
}
s[n++]=c;
}
assert(n>0 && n<=maxn);
memset(F,-1,sizeof(F));
f(0);
print(0);
}

Let's compare our WA submissions
I'm a third person who can't solved this problem.
I wrote two independent DP solutions on C++ and Java and both programs
received WA.
There is only 1 test in input, right?
Could anybody verifies my output?
Could anybody post part AC code which shows how
correctly handle input,output?
Test cases generator (1.in,2.in, ..., 9.in)
Output files sizes
I wrote two independent DP solutions on C++ and Java and both programs
received WA.
There is only 1 test in input, right?
Could anybody verifies my output?
Could anybody post part AC code which shows how
correctly handle input,output?
Test cases generator (1.in,2.in, ..., 9.in)
Code: Select all
#include <stdio.h>
#define F(x) freopen(x ".in","w",stdout)
void p(const char *s,int count)
{
while(--count >= 0) printf("%s",s);
}
int main(void)
{
int i,k;
unsigned int x;
char z[256];
F("1");p("122",42);fclose(stdout);
F("2");p("122",43);fclose(stdout);
F("3");p("1333",32);fclose(stdout);
F("4");p("aabb",32);fclose(stdout);
F("5");p("aabbc",26);fclose(stdout);
F("6");p("aacbb",26);fclose(stdout);
F("7");p("ab",64);p("22",1);p("ab",64);fclose(stdout);
F("8");for(i=1;i<=128;i++) {z[0]='a'+(i&1);z[1]=0;p(z,i);} fclose(stdout);
F("9");
x = 239;
for(k=1;k<=10000;k++) for(i='a';i<='z';i++)
{
z[0]=i;
z[1]=0;
x = 1664525 * x + 1013904223;
p(z,(x % 3) + 1);
}
fclose(stdout);
return 0;
}
Code: Select all
1 127 bytes
2 130 bytes
3 128 bytes
4 128 bytes
5 131 bytes
6 131 bytes
7 260 bytes
8 256
9 476264 bytes
I've got these output file size with my AC code
Code: Select all
1 168
2 172
3 128
4 128
5 156
6 156
7 260
8 256
9 490914
You're right, I didn't notice that point. My code seems to be wrong.
But I think the judge I/0 is not wrong (but week). Here's my guess.
I think that there is no case that my code outputs the wrong answer (like 1.in) in the judge I/O.
And there is a case that my code outputs the correct answer and your code doesn't.
Otherwise, I can't explain how all the otherguys got accepted.
I can't think that they all done the same mistake as me.
So I was just lucky. There was no critical case for me.
----
Sory for my poor English.
But I think the judge I/0 is not wrong (but week). Here's my guess.
I think that there is no case that my code outputs the wrong answer (like 1.in) in the judge I/O.
And there is a case that my code outputs the correct answer and your code doesn't.
Otherwise, I can't explain how all the otherguys got accepted.
I can't think that they all done the same mistake as me.
So I was just lucky. There was no critical case for me.
----
Sory for my poor English.
I wrote third absolutely wrong solution on C but it received AC.
Code: Select all
#include <stdio.h>
unsigned char a[256];
int n=0;
void f(unsigned char *a,int n)
{
int i;
if (n < 1) return;
putchar(n-1);
for(i=0;i<n;i++) putchar(a[i]);
}
int main()
{
n=0;
for(;;)
{
int l,c = getchar();if (c == EOF) break;
a[n++] = (unsigned char) c;
if (n > 1 && a[n-1] == a[n-2])
{
f(a,n-2);
l = 129;
for(;;)
{
c = getchar();if (c == EOF) break;
if (c != a[n-1])
{
ungetc(c,stdin);
break;
}
if (++l == 255) break;
}
putchar(l);
putchar(a[n-1]);
n = 0;
}
if (n == 129)
{
f(a,128);
a[0] = a[128];
n = 1;
}
}
f(a,n);
return 0;
}
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- New poster
- Posts: 24
- Joined: Sun Nov 12, 2006 3:38 pm
A few months ago I got my code accepted, than for some reason the problem appeared in my "tried but not solved" list, so I submitted again and got WA.
I rewrote the code and got AC. My output to the test cases avm posted is:
I rewrote the code and got AC. My output to the test cases avm posted is:
Code: Select all
1. 127
2. 131
3. 128
4. 129
5. 132
6. 132
7. 261
8. 256
9. 490572
My AC program gets the exact output as avm, so I think your program is still not optimal.viniciusweb wrote: I rewrote the code and got AC. My output to the test cases avm posted is:
Code: Select all
1. 127 2. 131 3. 128 4. 129 5. 132 6. 132 7. 261 8. 256 9. 490572
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.