10132 - File Fragmentation

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10132 File Fragmentation WA!~

Post by hank » Wed Jan 29, 2003 3:36 pm

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Wed Jan 29, 2003 8:51 pm

Try this input:

1

00
00
1
1

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

10132 - File Fragmentation

Post by technobug » Fri Mar 05, 2004 1:37 am

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Mar 05, 2004 5:33 pm

may be it was a multiple input problem...
"Everything should be made simple, but not always simpler"

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Mar 05, 2004 6:41 pm

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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Mar 05, 2004 6:44 pm

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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Mar 05, 2004 6:45 pm

which means, multiple input should be ok, right?

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Mar 17, 2004 5:16 pm

did you manage to solve it?

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Mar 17, 2004 5:19 pm

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Mar 14, 2006 9:44 pm

technobug wrote: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.

User avatar
seulkiro
New poster
Posts: 6
Joined: Sun Feb 15, 2004 2:13 am
Location: Canada
Contact:

Post by seulkiro » Sun Nov 26, 2006 1:49 am

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

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

cynthiadriana
New poster
Posts: 2
Joined: Mon Feb 05, 2007 1:32 am

10132 File Fragmentation - WA (need more test data)

Post by cynthiadriana » Mon Feb 05, 2007 1:39 am

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
New poster
Posts: 2
Joined: Mon Feb 05, 2007 1:32 am

Solved!

Post by cynthiadriana » Mon Feb 05, 2007 5:13 am

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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

File Fragmentation

Post by temper_3243 » Sun Mar 04, 2007 1:57 pm

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Wed Mar 14, 2007 11:24 am

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

Post Reply

Return to “Volume 101 (10100-10199)”