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

tottinbot
New poster
Posts: 2
Joined: Tue Aug 14, 2007 5:15 pm

Post by tottinbot » Wed Aug 15, 2007 6:13 am

i got WA but cant find whats wrong

Code: Select all

removed
Last edited by tottinbot on Thu Aug 16, 2007 7:10 am, edited 1 time in total.

tottinbot
New poster
Posts: 2
Joined: Tue Aug 14, 2007 5:15 pm

Post by tottinbot » Wed Aug 15, 2007 6:47 am

already found - it was because of excessive gets() before while :)

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Aug 15, 2007 8:55 am

tottinbot wrote:already found - it was because of excessive gets() before while :)
You should remove your code if you got AC.. :-)

clivant
New poster
Posts: 1
Joined: Sun Nov 11, 2007 9:00 am

Post by clivant » Mon Dec 10, 2007 7:43 am

Anyone can advise on the exact format of the output?

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

10132 - File Fragmentation WA

Post by hpjhc » Thu Sep 19, 2013 12:05 pm

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

int cmp(const void *, const void *);
void compare(int, int, int);
char str[144][260];
char s[600], t[600];
int main(void)
{
int n, i, k, len, ok;
scanf("%d", &n);
getchar();
for(i = 0; i < n; i++)
{
k = 0;
gets(s);
while(gets(str[k++]), str[k-1][0] != 0);
len = k-1;
qsort(str, len, sizeof(str[0]), cmp);
ok = 0;
if(len == 2)
printf("%s\n", strcat(str[0], str[1]));
else if(strlen(str[0]) == strlen(str[1]))
compare(0, 1, len);
else if(len >= 6)
{
if(strlen(str[1]) == strlen(str[2]))
compare(1, 2, len);
else
compare(0, 1, len);
}
else
compare(0, 1, len);
if(i < n-1)
printf("\n");
}
return 0;
}

int cmp(const void *a, const void *b)
{
int len1, len2;
len1 = strlen((char *)a);
len2 = strlen((char *)b);
return len1-len2;
}

void compare(int i, int j, int len)
{
strcpy(s, str);
strcpy(t, str[j]);
strcat(s, str[len-1-i]);
strcat(t, str[len-1-j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[j]);
strcat(s, str[len-1-j]);
strcat(t, str[len-1-i]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[len-1-j]);
strcat(s, str);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[len-1-j]);
strcat(s, str[j]);
strcat(t, str);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[len-1-i]);
strcat(s, str[len-1-j]);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[len-1-j]);
strcat(s, str[len-1-i]);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[j]);
strcat(s, str);
strcat(t, str[len-1-j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-j]);
strcpy(t, str[j]);
strcat(s, str);
strcat(t, str[len-1-i]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10132 - File Fragmentation WA

Post by brianfry713 » Thu Sep 19, 2013 9:33 pm

Input:

Code: Select all

2

011
0111
01110
111
0111
10111

011
0111
01110
111
0111
10111
output should be:

Code: Select all

01110111

01110111
Check input and AC output for thousands of problems on uDebug!

Alew
New poster
Posts: 1
Joined: Sun Sep 29, 2013 1:33 pm

Re: File Fragmentation

Post by Alew » Fri Dec 13, 2013 3:54 pm

here is my algorithm (sorry for my english):
1) compute the length of the original string and the number of ones and zeroes in it
2)make a table of the fragments(with width of the original string). Align each fragment to the left and to the right:
110***
***110
11****
****11
3)count the number of ones and zeroes in each column. If ones > zeroes then in the string there is 1 in this position;
the same for zeroes;
if ones == zeroes then it can be any of it(according to the counted number of 1 and 0 in the original string)

User avatar
Zyaad Jaunnoo
Experienced poster
Posts: 120
Joined: Tue Apr 16, 2002 10:07 am

Re: File Fragmentation

Post by Zyaad Jaunnoo » Wed Oct 15, 2014 6:17 pm

I used a brute force approach to find the correct fragment combination. Complexity = O(n^2).

Here is the pseudocode:
1) Use a map<string, int> to store the combined fragments and a count of how many fragments of that kind can be made.
2) Concatenate fragment with fragment[j], where 0 <= i, j <= number of fragments and i <> j.
3) Increment the count of map<string, int>

Solution:
The fragment we are looking for is the one having the greatest count.

Hope it helps :wink:

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

Re: 10132 - File Fragmentation

Post by TryCatchMe » Tue Dec 23, 2014 9:14 pm

I solved this problem with backtracking in 0.015. A hint to those who are lost: for each test case compute the length of the solution string by summing all the input string lengths and dividing by (number of lines / 2) and exploit this in your pruning.

Mukit Chowdhury
Learning poster
Posts: 96
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10132 - File Fragmentation

Post by Mukit Chowdhury » Wed Oct 05, 2016 9:33 am

Accepted

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest