714 - Copying Books

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

Moderator: Board moderators

hlchan
New poster
Posts: 7
Joined: Sat May 25, 2002 8:15 am

714 - Copying Books

Dear all,

I have a hard time doing 714. I have tried many test cases and get correct answer. However, the online judge still reply 'wrong answer'...

Can anyone give me some hints about what points i have missed?

Thank you in advance.

hlchan
New poster
Posts: 7
Joined: Sat May 25, 2002 8:15 am

Reason for error

Finally, i find that the problem my program is integer overflow...

...

choyon_buet
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm
Location: BANGLADESH

714

can any one help me about the problem 714. i got WA . i am not even sure if i understood the problem.but it satisfies all the sample inputs.
so to make it clear to u i also sent my code here.

[cpp]
/* @JUDGE_ID: 26419ZE 714 C++ "" */
#include<stdio.h>

void main()
{
unsigned long test;
unsigned long a,b,n,m,k,i,j;
long double sum,num;
unsigned long v[500];
long long avg;

while(1==scanf("%lu",&test))
{

for(n=0;n<test;n++)
{

sum=0;a=0;

scanf("%lu%lu",&m,&k);
for (j=0;j<m;j++)
{
scanf("%lu",&v[j]);
sum+=v[j];
}
avg=(sum/k);
num=0;
for(i=0;i<m;)
{
num+=v;
if((num>avg)&&a!=k-1)

{
printf("/ ");
num=0;
a++;
continue;
}
else printf("%lu",v);
if(i!=(m-1))printf(" ");
i++;
if(i==m)break;
}
printf("\n");

}
}
}

/*end of source code*/[/cpp]

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Hello. It is a problem about partition, can't be solved by your algorithm.

Try to think another way, good for you.

Malcolm
New poster
Posts: 5
Joined: Fri Jan 23, 2004 4:34 pm
Location: Taiwan

714 Help~~

I am stuck in this problem. Anyone can help??
I tried DP and divide and conquer but these two all got TLE.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

714 - copying books, help

hi,

i used something like this but got WA.

Code: Select all

``````let memo[left][start] define best arrangements from element start to last element with using left scribes, all element in memo initialize to -1;

long long rec(int left, int start)

if(memo[left][start]!!=-1) return memo[left][start];
if(left==1) {
count sum from element start to last element and return it;
}
best=INF;
for(i=start+1;i<number element; i++) {
let temp = max (sum from element start to element i-1, rec (left-1,i);
best = min (best, temp);
}
return best;
``````
it passed all sample input, and it seems OK, but i got WA on 4 sec. anyway i dont know why many ppl can solve this prob in < 0.020 sec?

thanks before.

-titid-
Kalo mau kaya, buat apa sekolah?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Try using binary search.. =) (and a little of greed)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i can see the way that this problem can be solved by binary trees. looking at the structure, it is DP problem. i think i need more explanation.
thank you very much.

-titid-
Kalo mau kaya, buat apa sekolah?

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Hi,

I always get WA for this problem. I used Divide and Conquer recursion with memoization.

I did this way :

Let sum[x] be the summation of book pages from the first book to the x'th book, and sum[0]=0.

Code: Select all

``````long long divideandconquer(int start, int scriber) {
int p;
long long min,value;
if (scriber==1)
return sum[j]-sum[start-1];
else
{
min:=INF;
for p=start to j-1 do
{
value=max(sum[p]-sum[start-1],divideandconquer(p+1,scriber-1));
if value<min then min=value;
}
return min;
}
}``````
In the main program, I called divideandconquer(1,jum_scriber);

Maybe I made some mistakes here?

I have tried a lot of cases, and it worked well. Is there any tricks?
Could someone please give me some inputs outputs?

Thanks for any help.

Regards,
Anggakusuma

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

714 (Copying books) - greedy approach?

Hi.

Can this problem be solved using a greedy algorithm? I've so far devised a dynamic programming O(n^3) algorithm, but the judge gives me wrong answer (when there is more than one optimal solution, and I have to minimize the work assigned to the first scriber, second and so on - the particular case where the solution to the subproblem doesn't need to be optimal). My DP algorithm is very similar to the one Angga describes in http://online-judge.uva.es/board/viewtopic.php?t=5599.

I've read, however, that this problem can be solved with greedy. I would really appreciate if anyone could explain this approach in more detail, or at least help me with the DP method.

Thanks in advance.

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Re: 714 (Copying books) - greedy approach?

Tomislav Novak wrote:Can this problem be solved using a greedy algorithm?
Yes, it is.

The basic idea is:
Search the maximum number of pages assigned to the scribers. For every number of maximum pages you searched, you can check whether that number is too big or too small by assigning the books to the scribers greedily (follow the rule given in the prob. description).

tsaiminghan
New poster
Posts: 1
Joined: Sun Oct 02, 2005 11:44 am

714 Copying Books i don't know why w.a.

i don't know what's wrong.
can anyone tell me why the answer is wrong or give more test case?

#include<stdio.h>
int test(int max);
void p(int max);
int books[500];
int set[500];
int pages;
int m,k;
void main(){
int n,i;
int upper_bound,lower_bound,mid;
scanf("%d",&n);
while(n--){
scanf("%d%d",&m,&k);
upper_bound=lower_bound=0;
for(i=0;i<m;i++){
scanf("%d",&pages);
books=pages;
upper_bound+=pages;
}
lower_bound=upper_bound/k;
while(lower_bound!=upper_bound){
mid=(lower_bound+upper_bound)/2;
if(test(mid)) upper_bound=mid;
else lower_bound=mid+1;
}
/*printf("%d\n",upper_bound);*/
p(upper_bound);
}
}
int test(int max){/*gobel m,k*/
int i,j=1;
int temp=0;
for(i=0;i<m;i++){
temp+=books;
if(temp>max){
temp=books;
j++;
}
}
return (j>k)?0:1;
}
void p(int max){
int i,j=k-1,l;
int temp=0;
for(i=m-1;i>=0;i--){
if(j==i+1){
for(l=0;l<j;l++)
set[l]=l;
break;
}
else{
temp+=books;
if(temp>max){
temp=books;
set[j-1]=i;
j--;
}
}
}
for(i=0,j=0;i<m;i++){
if(i!=0) printf(" ");
printf("%d",books);
if(i==set[j] && j<k){
printf(" /");
j++;
}
}
printf("\n");
}

#include<stdio.h>
int test(int max,int left,int k);
void p(int max,int left,int n);
int books[500];
int pages;
int m,k;
void main(){
int n,i;
int upper_bound,lower_bound,mid;
scanf("%d",&n);
while(n--){
scanf("%d%d",&m,&k);
upper_bound=lower_bound=0;
for(i=0;i<m;i++){
scanf("%d",&pages);
books=pages;
upper_bound+=pages;
}
lower_bound=upper_bound/k;
while(lower_bound!=upper_bound){
mid=(lower_bound+upper_bound)/2;
if(test(mid,0,k)) upper_bound=mid;
else lower_bound=mid+1;
}
/*printf("%d\n",upper_bound);*/
p(upper_bound,0,k);
}
}
int test(int max,int left,int k){/*gobel m,k*/
int i,j=1;
int temp=0;
for(i=left;i<m;i++){
temp+=books;
if(temp>max){
temp=books;
j++;
}
}
return (j>k)?0:1;
}
void p(int max,int left,int n){
int i,j;
if(n==1){
for(i=left;i<m;i++)
printf("%d ",books);
printf("\n");
}
else{
for(i=left+1;i<m;i++)
if(test(max,i,n-1)){
for(j=left;j<i;j++)
printf("%d ",books[j]);
printf("/ ");
p(max,i,n-1);
return;
}

}
}

[/quote]

sobhan naderi
New poster
Posts: 7
Joined: Sat Sep 02, 2006 8:59 am
Location: Sweden/Stockholm
Contact:
Use binary search to find the maximum number of pages and then check whether it is possible to find a configuration or not.

the total time as much as would be 500*log(500*10000000) at most
Sobhan Naderi Parizi

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Output for this input

I'm getting WA too... Can someone who got AC post the correct output for the input below? thanks!

Code: Select all

``````5
9 3
9 8 1 7 6 2 3 4 5
3 2
1 2 1
8 4
10 2 10 2 15 20 1 30
30 8
46 18 71 6 35 59 35 52 83 62 85 71 72 88 46 100 8 5 89 85 61 80 59 43 39 51 31 100 90 40
500 120
198429 225879 591107 583645 268500 151557 563518 248740 722030 674754 235494 165111 4520 807760 7269 710494 636769 334106 963142 541561 171837 78214 5965 883949 226710 299323 900222 102726 122447 163449 307908 873977 702390 901413 140877 843943 656618 304012 907339 34834 658439 148739 243226 352932 473060 122583 390594 545667 566414 769880 54794 927040 819584 300102 761380 412128 566990 766983 318949 691513 377512 157581 131870 155107 47900 261108 618196 849399 78421 650093 429882 664391 80298 592935 628864 370927 214123 492610 978070 61186 297876 235107 170694 414682 523083 901046 437256 306467 573591 359337 875292 778025 470884 701014 31795 345026 324202 791498 696259 900218 333581 770868 976227 701569 204631 312424 590689 135264 31786 850965 100374 642051 278100 311220 364042 446340 711410 5176 68123 756459 13430 189598 323062 63556 177330 535293 506933 866114 302950 30504 680091 868833 319799 503602 319554 961825 227936 774472 167523 456540 768584 831825 957276 292280 773926 128255 881208 991461 358430 762594 148155 225787 23283 46559 549856 505529 960914 242559 755090 753257 164380 608422 329481 922946 179008 203746 221602 476370 250162 493750 721156 595250 774471 135868 631691 960930 134439 152474 580281 869130 427253 894328 852244 275992 304562 228685 825766 165977 337864 608874 77083 83037 959566 836837 791824 454050 561105 776791 834506 480150 966327 281397 319832 395378 771665 442373 970685 467177 439158 159457 75347 935617 539027 343771 179989 418739 137422 529877 141552 174986 492927 177445 598931 232239 377814 661774 339044 361603 979889 820655 568922 662296 910813 894657 538153 203560 333530 625555 61562 510683 477338 255431 166783 836501 85264 83957 719628 101784 281429 443673 955446 780613 787113 243172 892947 612250 16267 419960 946403 279025 965493 749942 431565 409349 585400 93642 618251 749098 980731 685603 415042 976746 475490 660470 578759 487447 271643 638432 393958 891775 767131 676623 535567 232413 700618 348825 971863 445381 296164 2629 59751 431585 673073 864507 758631 785422 325968 140684 657034 355143 509594 636610 950725 932263 444819 516898 542988 834674 865585 881331 16093 963873 718120 796405 553691 331891 718001 51733 290238 80315 459943 376249 545094 433518 508487 386036 683954 860464 313346 120405 114055 268164 594847 122581 239915 658833 7172 568797 215259 428107 532799 55728 911849 475560 240223 698220 886813 455973 392124 270443 224029 661415 865820 739092 136893 551824 692232 841494 971008 280350 638878 448007 741625 968839 336399 302198 613335 154362 808391 497471 557747 847473 772339 37606 286386 618458 764286 777064 399574 301393 437041 185330 470170 129889 59897 23952 20660 210430 860125 593983 682568 196016 590736 790523 209102 302526 5104 996233 920238 681565 182650 683855 626972 880027 830125 695347 780381 201717 195558 289103 735989 755440 810417 701663 60882 900789 127515 223784 563781 937038 343232 730319 325741 883902 942707 297927 680658 299050 753989 12233 797143 604734 129908 536677 324282 496847 702928 452511 434497 244819 571622 365775 871803 115496 909997 293049 16069 759937 524808 447231 125365 487528 298355 674720 35886 750638 349355 138458 311402 36476 360745 668991 770441 990497 353708 21727 204313 330968 486560 938009 427241 582572 396421 52658 507560 51008 205684 573839 834945 411782 780269 161774 355807 250602 238580 637995 637956 642036 968597 489363 953260 910383 776319 17240 566176 672394 704016 928455 666896 557124``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
My accepted code returns..

Output
Ami ekhono shopno dekhi...
HomePage