11400 - Lighting System Design

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

Moderator: Board moderators

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

11400 - Lighting System Design

Hi, this problems seems like a Min-Cost-Max-Flow problem, but the cost of the sources complicate everything, can anyone give me a hint? Thanks, Eric.

PD: if it is not right to post this problem here i will delete it.
PD2: where there any tricky cases for the problem 11403 ( Binary Multiplication ).

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:
Think DP.

Hint:
Sort the categories by voltage. Run through this list. At each category you can either buy all the lamps you need now (hence you also buy the source for this category), or you can choose not to buy anything now and hence pass on all the lamps from this category and whatever you did not buy before to the next. If you think about it, this defines a 2D state space (the current category and when you bought lamps last time).

For 11403: what did the trick for me was to print a newline after every test case (as opposed to printing one between each case as is stated in the text).
For help with problems, visit http://www.uvatoolkit.com/

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Thank you very much!. Eric.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
I've gotten so far about 25 WAs so I'm really confused. I would like to see the correct output from an AC program for this input set (these are random tests for 1<=n<=6). Thanks in advance!

Code: Select all

``````5
43018 319 5 76
129866 531 4 77
18653 85 2 25
49999 818 3 71
104564 391 3 47
1
78592 90 1 49
1
113314 877 9 64
5
30606 522 4 60
75799 425 3 22
3562 639 9 81
47290 50 2 100
65478 950 10 100
2
54376 266 7 80
20986 679 2 50
5
116769 267 1 22
53261 208 8 91
71378 729 3 33
36286 903 7 78
73671 809 7 54
6
75918 239 4 37
86410 305 3 59
28415 449 9 75
67237 892 10 78
112770 429 1 74
28997 249 6 49
5
90685 384 5 3
43800 269 6 15
117507 652 3 55
16365 780 7 56
131188 426 9 18
6
111637 142 5 43
52375 694 8 70
128189 300 7 100
95942 286 5 89
51248 66 9 9
38346 147 5 20
3
30524 139 1 18
95821 646 7 70
43630 635 4 75
6
94017 504 2 4
55203 270 5 68
120408 724 9 76
1668 765 6 53
70072 301 2 16
10544 779 8 34
3
49214 880 2 3
87566 562 2 100
16483 397 6 43
4
61732 269 1 83
42331 566 4 54
123135 892 4 32
61721 205 6 82
4
60112 18 9 57
30189 293 2 96
48921 417 7 68
55780 289 1 29
5
2541 958 3 84
20353 406 2 77
23991 48 7 65
19299 591 3 36
129925 89 3 37
4
44306 219 6 41
49883 582 10 50
128864 51 3 85
62729 319 7 59
5
125422 832 8 40
67269 847 8 62
55204 983 10 26
124299 306 6 76
118580 304 1 96
6
102510 790 6 2
95296 655 6 57
14262 998 8 69
41336 910 1 85
113489 847 10 31
83947 621 3 54
5
106560 388 5 93
89141 585 3 15
126431 73 6 15
69210 368 9 38
95700 580 2 2
5
125839 13 5 9
43626 814 1 10
99685 787 3 2
123930 865 4 27
58754 702 7 46
6
26615 508 1 28
42390 771 7 1
26228 154 3 85
38812 710 4 90
45124 720 7 8
126225 268 6 21
5
49613 200 6 93
69991 428 8 48
87297 603 5 11
87493 867 2 23
90581 218 9 75
6
28994 430 8 58
109879 451 7 73
40017 1000 10 34
80773 612 7 30
51 130 8 88
40525 611 10 65
3
46643 633 10 5
82942 405 2 94
18021 827 10 68
3
119098 551 6 52
56926 413 7 44
6689 156 5 67
1
96185 247 1 9
6
45471 764 1 57
60998 974 8 84
29940 314 8 46
68944 770 2 26
1601 802 5 48
50575 324 1 59
3
83343 663 7 68
9321 414 3 47
92554 865 3 95
5
1112 592 4 3
52054 685 4 55
105396 973 6 20
51366 330 5 71
67466 982 4 93
3
62325 669 8 14
37432 179 10 6
127172 234 8 2
4
111661 423 1 77
116260 708 4 53
17452 190 3 11
75523 208 10 67
5
83704 949 4 66
39749 733 3 33
114815 586 9 62
107346 996 3 10
36674 905 7 92
3
99352 186 6 34
22553 762 4 64
80454 2 6 83
3
95337 158 2 10
125977 689 7 86
123381 482 9 13
2
58265 921 9 48
104509 985 10 21
3
126172 309 6 90
121146 88 7 86
68573 488 6 42
4
98862 956 2 100
49395 301 4 8
16368 267 4 1
40255 503 4 55
5
82469 806 1 18
58698 298 6 12
95899 226 2 72
93478 568 9 49
41804 845 6 93
3
67464 605 8 97
55321 726 2 19
93651 128 1 78
1
76022 86 3 73
4
34682 480 9 45
104174 290 3 7
74284 79 5 53
17426 742 8 19
2
21618 150 2 75
83538 267 6 10
6
63853 54 7 50
76861 519 6 6
451 961 4 2
7995 65 1 37
100662 525 6 41
61678 243 3 40
2
67639 797 5 55
49045 416 10 84
5
54712 84 5 3
87582 242 6 1
83056 878 10 23
77008 677 10 69
6614 791 3 56
3
82651 60 8 36
131446 953 3 38
38792 239 9 28
6
3340 889 7 83
64838 762 2 19
93227 18 10 86
107294 443 5 58
80402 295 3 29
85439 241 4 45
5
9581 530 1 13
55607 472 3 69
18862 655 5 70
30258 769 2 20
42787 475 10 3
5
34546 400 7 74
54629 110 2 14
48720 426 10 34
34085 998 9 22
9804 107 7 100
5
9827 473 8 62
54696 894 10 60
49237 646 1 96
40134 183 8 94
38073 578 10 16
5
80585 703 2 50
50866 55 3 76
25076 272 3 65
25620 422 5 61
117125 746 5 53
4
50449 906 2 51
109749 894 8 70
32495 110 3 59
26593 599 4 8
2
30290 968 10 1
14917 602 10 87
3
58934 26 7 31
90613 546 10 79
69529 2 8 38
2
31983 606 7 90
28399 362 1 33
3
76967 558 4 21
81345 140 9 96
90650 737 6 97
1
47294 581 3 74
3
46292 507 2 11
106655 381 9 56
16732 89 10 23
5
23566 939 8 96
86764 865 9 54
22213 1 3 61
108337 996 10 84
118278 755 1 96
3
68946 343 9 16
98135 49 5 16
105246 267 7 51
4
110698 825 2 58
45289 63 10 100
90551 654 4 98
75978 416 7 38
3
46525 539 10 43
107411 839 10 90
72007 205 10 13
6
80765 68 9 6
61252 915 9 39
76620 23 4 73
10817 661 1 78
83218 110 9 35
83080 158 2 84
6
7448 310 7 21
100194 710 1 58
122328 353 9 1
92534 347 4 89
112916 866 6 40
79468 433 8 23
6
91531 572 1 80
115686 322 8 30
111354 701 10 23
103920 725 4 30
80990 983 1 71
14146 124 6 21
6
126735 857 10 28
16928 284 5 86
101693 655 9 42
76880 876 8 69
53850 163 2 50
57463 801 10 77
6
55694 757 7 36
9526 247 1 82
4713 244 8 82
63721 703 6 77
56233 911 6 74
88465 402 5 1
3
116389 966 8 95
72251 899 1 78
102252 325 6 68
1
3826 895 7 39
2
92842 439 4 32
6603 141 5 74
6
101795 549 3 76
12664 104 4 74
98127 49 5 98
18979 634 5 40
121267 722 7 28
69774 8 4 65
6
31977 579 8 44
41195 557 4 92
130813 942 8 8
62816 674 2 88
31655 386 8 97
52197 272 10 55
5
115964 545 2 38
77286 275 9 49
946 493 8 56
40006 251 2 15
28952 198 4 25
2
130852 403 9 24
56660 837 7 80
4
76106 412 5 33
32695 699 3 71
47742 608 10 36
37624 740 9 4
3
63657 257 3 47
16973 478 2 17
64924 953 6 13
3
82915 966 9 56
65554 155 2 74
124961 659 9 65
2
95198 388 5 34
79130 558 10 56
1
39009 57 8 71
3
56018 98 3 22
97520 256 9 54
15096 822 10 17
2
69763 186 2 71
42410 699 7 49
6
104942 564 6 34
5965 89 3 49
1328 819 3 74
96151 587 9 93
125174 976 10 57
127948 618 6 97
3
7218 580 7 59
67830 348 4 60
97222 568 1 13
6
76296 342 2 2
62746 309 10 55
115141 67 1 17
97778 109 9 81
42766 183 7 21
6794 106 7 24
2
68770 41 1 4
65360 150 4 68
3
25775 995 3 86
15566 273 2 48
72368 951 1 49
3
92682 592 4 1
20771 860 4 81
9602 732 1 52
2
101603 533 5 12
27089 832 2 93
5
52806 58 2 30
24371 949 6 36
117189 408 7 99
38838 125 5 54
37325 611 3 53
6
99871 441 10 2
4812 351 9 80
69548 962 9 42
114034 354 1 87
54405 937 5 56
10080 221 7 84
6
102300 521 5 41
121623 544 3 27
97775 418 4 46
105640 500 1 57
46668 28 7 97
44004 849 3 47
1
49155 441 7 61
4
11406 472 9 65
28309 667 3 67
103186 230 7 73
92493 24 8 49
5
97945 501 6 87
121105 910 1 81
100910 388 3 43
121429 560 1 71
12729 384 4 50
3
113727 69 7 68
22375 962 8 82
62081 404 6 34
3
71140 650 1 50
93046 501 10 97
28879 794 7 89
3
81864 20 10 47
129161 780 4 54
119983 868 8 50
1
102620 593 5 10
1
57487 658 8 47
4
120625 761 3 72
84507 808 9 27
23917 620 1 86
108517 849 5 21
0
``````

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:
You can check it on my page http://www.uvatoolkit.com.
Last edited by greve on Wed Oct 28, 2009 6:56 pm, edited 1 time in total.
For help with problems, visit http://www.uvatoolkit.com/

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
Thanks Greve, that's really fantastic site!
I've found the error in my code.

d8888
New poster
Posts: 2
Joined: Wed Aug 13, 2008 11:32 am

Re: 11400 - Lighting System Design

Can anyone teach me why I got TLE in this problem?
I tried to modify data structure several time, but result was still the same.
Also, according to previous posts, the technique used in this problem is DP, and I used DP with memorization, so I really can't figure where I did wrong.
Thanks!

Code: Select all

``````//============================================================================
// Name        : acm11400.cpp
// Author      :
// Version     :
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct record
{
int voltage;
int cost_power;
int nlight;
int cost_light;
};

vector<map<int,int> > mem;
int ncat;
const int MAXCAT=1024;
vector<record> aray;

void Search(int rank,int extra)
{
//printf("called rank %d extra %d\n",rank,extra);
if(rank==ncat-1)
{
mem[rank][extra]=aray[rank].cost_power + aray[rank].cost_light* (aray[rank].nlight+extra);
return;
}
if(mem[rank].find(0)==mem[rank].end())
{
Search(rank+1,0);
}
int a=mem[rank+1][0]+aray[rank].cost_power + aray[rank].cost_light* (aray[rank].nlight+extra);
if(mem[rank].find(extra+aray[rank].nlight)==mem[rank].end())
{
Search(rank+1,extra+aray[rank].nlight);
}
int b=mem[rank+1][extra+aray[rank].nlight];
mem[rank][extra]=a<b?a:b;
}

class RecordSort
{
public:
bool operator()(const record  &a,const record &b)
{
return a.voltage < b.voltage;
}
};

int main()
{
RecordSort sorter;
mem.resize(MAXCAT);
while(1)
{
scanf("%d",&ncat);
if(ncat==0)
{
break;
}
aray.clear();
aray.resize(ncat);
for(int i=0;i<ncat;i++)
{
mem[i].clear();
scanf("%d",&aray[i].voltage);
scanf("%d",&aray[i].cost_power);
scanf("%d",&aray[i].cost_light);
scanf("%d",&aray[i].nlight);
}

sort(aray.begin(),aray.end(),sorter);

Search(0,0);
printf("%d\n",mem[0][0]);
}
return 0;
}
``````