10132 - File Fragmentation

[hank]

I got Wrong Answer.
But I can't find the wrong.
Anybody can give me some test data of problem 10132?
I think it will be helpful.
Thanks!
[c]#include "stdio.h"
#include "string.h"
#define MAX 2080
struct{
int data[MAX];
int length;
int used;
}f[300];
int n,len,stop;
int intcmp(int a[],int i,int j)
{
int t,s[MAX];
for(t=0;t<f.length;t++)
s[t]=f.data[t];
for(t=0;t<f[j].length;t++)
s[t+f.length]=f[j].data[t];
for(t=0;t<len;t++)
if(s[t]!=a[t]) return 1;
return 0;
}
void recursive(int parent,int level,int nowfile[])
{
int i,j,k;
if(stop) return;
if(level==n){
for(i=0;i<len;i++)
printf("%d",nowfile);
printf("\n");
stop=1;
return;
}
for(i=1;i<=n;i++){
if(f.used) continue;
if(level==2&&f[parent].length+f.length==len){
for(k=0;k<f[parent].length;k++)
nowfile[k]=f[parent].data[k];
for(k=0;k<f.length;k++)
nowfile[k+f[parent].length]=f.data[k];
}
if( level%2==0 && f[parent].length+f.length!=len ) continue;
if( level%2==0 && level!=2 && intcmp(nowfile,parent,i)!=0 ) continue;
f.used=1;
recursive(i,level+1,nowfile);
f[i].used=0;
}
}
void main()
{
int N;
int i,j,k;
char arr[MAX];
int d[MAX];
scanf("%d\n",&N);
for(;N;N--){
scanf("\n");
n=0;
len=0;
while( gets(arr) ){
if(strlen(arr)==0) break;
++n;
for(j=0;arr[j];j++)
f[n].data[j]=arr[j]-'0';
f[n].length=strlen(arr);
f[n].used=0;
len+=f[n].length;
}
len/=n;
len*=2;
for(i=1;i<=n;i++){
stop=0;
f[i].used=1;
recursive(i,1,d);
f[i].used=0;
if(stop) break;
}
printf("\n");
}
}[/c]

(I use "recursion" to find the solution)

[Caesum]

Try this input:

1

00
00
1
1

[technobug]

I have solved it sucessfully at programmingchallenges.com but got wrong answer at uva's site....

I have tried a simple approach and a more robust one (with some better pruning)... i am only posting the simple one which is smaller.

I don't believe there is something that I might be missing:
- last line might be empty or EOF, both are ok
- if it doesnt find any possible solution, displays an empty line (such situation is not mentioned in the problems description)
- if the number of file fragments found is not even, what should I do?

i think the problem description could be a little bit more clear on those topics...

[cpp]
#include <iostream>
#include <string>
#include <vector>


using namespace std;

int totalWords;
int totalLevel;

int minSize;
int maxSize;

int totalSize;

string targetWord;

class palavra {
public:
string text;
bool usado;
int tamanho;
bool existeOutra;
};

vector<palavra *> mapas;

bool tentaLinha(int level) {

int t, alvo;

// se for o ultimo nivel, esta ok
if(level==totalLevel) {
return true;
}

for(int i=0;i!=totalWords;i++) {
if(!mapas->usado) {
mapas->usado = true;
for(int i2=0;i2!=totalWords;i2++) {
if(!mapas[i2]->usado
&& mapas->tamanho+mapas[i2]->tamanho == totalSize
&& mapas->text+mapas[i2]->text == targetWord ) {
mapas[i2]->usado = true;
if(tentaLinha(level+1)) return true;
mapas[i2]->usado = false;
}
}
mapas->usado = false;
}
}

return false;

}

void add(string p) {
palavra *nova = new palavra;
nova->text = p;
nova->tamanho = p.size();
if(nova->tamanho < minSize) {
minSize = nova->tamanho;
}
if(nova->tamanho > maxSize) {
maxSize = nova->tamanho;
}
totalWords++;
mapas.push_back(nova);
}

void reset() {

mapas.clear();
totalWords = 0;
minSize = 300;
maxSize = 0;
totalSize = 0;

}

int main(char **argv,int argc) {

int v;
cin >> v;

string p;
getline(cin,p);
getline(cin,p);

int min, max;
palavra *smin, *smax;

string mapao[144][144];

while(v--) {

reset();

while(getline(cin,p)) {
if(p[0]==0) {
break;
}
add(p);
}

totalLevel = totalWords / 2;
totalSize = minSize + maxSize;

// se for nivel 1, eh facil
if(totalLevel==1) {
cout << mapas[0]->text << mapas[1]->text << endl;
goto final;
}

// comeca com a primeira linha palavra X
for(int i=0;i!=totalWords;i++) {
mapas->usado = true;
for(int i2=0;i2!=totalWords;i2++) {
if(i2!=i && mapas->tamanho+mapas[i2]->tamanho==totalSize) {
mapas[i2]->usado = true;
targetWord = mapas->text+mapas[i2]->text;
if(tentaLinha(1)) {
cout << targetWord << endl;
goto final;
}
mapas[i2]->usado = false;
}
}
mapas->usado = false;
}

cout << "" << endl;
final:
if(v!=0) {
cout << endl;
}

}

return 0;

}

[/cpp]

[anupam]

may be it was a multiple input problem...

[technobug]

hmmm... it prints a blank line between test cases and no blank line at the end, aint that right?

i will add some input/output soon

[technobug]

input file:

Code: Select all

9

1
1

00
00
1
1

0
0

1
0

0
1

011
0111

011
10111
0111
0111

1234
56
12
3456

011
0111
01110
111
0111
10111
011101
11

output:

Code: Select all

11

001

00

10

01

0110111

01110111

123456

01110111

[technobug]

which means, multiple input should be ok, right?

[technobug]

did you manage to solve it?

[technobug]

what should be done in case there is no possible solution or there is not an even number of lines in the input?

[sclo]

what should be done in case there is no possible solution or there is not an even number of lines in the input?

such cases do not exist. Also the only allowed characters in the file are '0' and '1'. All the fragments are nonempty, and there are always at least one solutions. Therefore some kind of brute force approach is enough to solve this problem.

[seulkiro]

I used backtracking to solve this problem and got AC 0.020.

Anyone got AC by naive brute force approach to compare all the possible pairs?

[cynthiadriana]

I got Wrong Answer but I can't find what's wrong.
Can anyone please give me test data for the problem 10132?
Thanks

[cpp]
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void tabla (vector<string>);
int n=0;

int main (void){
int numcasos,i,pl;
string p;
vector<string> caso;
cin>>numcasos;
getline (cin,p);
getline (cin,p);
for (i=0;i<numcasos;i++){
caso.clear();
getline (cin,p);
pl=p.length();
while (pl>0){

n+=pl;
caso.push_back(p);
getline (cin,p);
pl=p.length();
}n=2*n/caso.size();
tabla (caso);
}
system ("pause");
return 0;
}

void tabla (vector<string> caso){
int t=caso.size();
string mat[t][t],h="";
for (int i=0;i<t;i++)
for (int j=0;j<t;j++){
h=caso[i]+caso[j];
if (i==j || h.size()!=n)
mat[i][j]="";
else
mat[i][j]=h;
}
int conteo;
for (int i=1;i<t;i++){
conteo=0;
if (mat[0][i]!="")
for (int j=0;j<t;j++)
for (int k=0;k<t;k++){
if (j!=k && mat[j][k]==mat[0][i])
conteo++;
}
if (conteo>=t/2){
cout<<mat[0][i]<<endl;
return;
}
}
}
[/cpp]

[cynthiadriana]

Well... I just figured it out... It had something to do with the fact that a concatenation isn't reciprocal

[temper_3243]

hi,
what is way to solve the following problem elegantly.
http://acm.uva.es/p/v101/10132.html
File Fragmentation

Code: Select all

one way i could think of is 

first compute the length of the string by adding all inputs and then dividing by number of fragments, let the final string be of length k.

now take any 2 or n strings (who sum is greater than or equal to k) , we get a pattern  z,
now repeat the pattern from 2 until  x  where x is equal to the length of all string in the input.

Try to fit in the pieces without gap (this is the difficult part)



011 			
0111			
01110			
111			
0111			
10111			
011101			
11 			





Does anyone have a better algorithm or different kind of algorithm that is easy to code

[asif_rahman0]

Hints:
1) Make a relation table.
2) Order have to consider
3) If there is no unique solution, any of the possible solutions!