10576 - Y2K Accounting Bug

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

Moderator: Board moderators

Post Reply
Almorrana
New poster
Posts: 3
Joined: Thu Nov 06, 2003 9:07 pm

10576 - Y2K Accounting Bug

Post by Almorrana »

I read and read multiple times the problem, but I don't understand what exactly to do. Any help or clarification?
thx
Top
Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
Contact Caesum

Post by Caesum »

maybe this will help:

Code: Select all

month	mprofit	reports
1	59	
2	59	
3	59	
4	59	
5	-237	-1
6	59	-1
7	59	-1
8	59	-1
9	59	-1
10	-237	-1
11	59	-1
12	59	-1
total	116
it shows that in month 1 they made 59 profit.... in month 5 they made 237 loss...
the eight reported numbers were in month 5 = -1 = sum of months 1..5, month 6 = -1 = sum of months 2..6, etc and so they made 8 losses as reported. the total profit at the end of the year was 116 though.....
Top
Almorrana
New poster
Posts: 3
Joined: Thu Nov 06, 2003 9:07 pm

Post by Almorrana »

Ohh thanks Caesum, now i got it... it's a simple problem hehe :oops:
Top
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:
Contact Sajid

Post by Sajid »

Caesum,
I could find it out, but what about 2nd case and deficit ?
Sajid Online: www.sajidonline.com
Top
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Initially I had difficulty in understanding the problem, but later when I did get the theme of it, I found it very easy.

I used (backtracking + pruning).

There is another easier solution. Run a loop from 1 to 2^12 and look for adjacent 1s in its binary representation.

--------------------------------------------------------------------------------------
Backtracking will always give you the correct solution, but it is selective pruning that will help you in passing the time limit.
Top
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Contact Larry

Post by Larry »

sohel: backtracking is inherently faster though, because of pruning.

I used an algorithm that basically greedily optimizes itself, before I realize the small months. AC anyhow, so it's all good I suppose.
Top
Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad »

Think about how many cosecutive 5 months can there be in a year.

1st -> 5th
2nd -> 6th
...
8th -> 12th

Now you need to assume all combinations of surplus & deficit for
all 12 months. For each combination check if all the consecutive
5 months result in deficit.

Rest of the problem should be trivial.

I run a loop of 0-4095 to generate all combinations of surplus & deficit.
Then check for validity of such combinations.
Top
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

A greedy approach works, which can get your code Accepted with 0.00.000 CPU time!!!! Try it!! :P :P
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Top
Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia

Post by Alexei Rybalkin »

Please, help.
What's wrong with my greedy algorithm?
[pascal](The bug was trivial and after adding some few changes the code was accepted. Conclusion: greedy algorithm works)[/pascal]
Thank you.
Top
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Contact Abednego

Post by Abednego »

Is 0 a deficit or a profit?

Nevermind. It makes no difference to the judge.
If only I had as much free time as I did in college...
Top
CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

Post by CC »

can somebody tell me how to solve this problem by Greedy
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10576 - Y2K Accounting Bug

Post by brianfry713 »

Input:

Code: Select all

4101497 6710350
2163550 3542387
539544 1111636
5085080 9666273
8789211 9365365
2370883 2797193
8079545 8073613
7691405 8552823
4145575 4573139
5730098 1906418
4507667 5009248
8546532 2087309
2734747 1082545
9028441 255967
5973691 5738302
2448652 8989505
2531893 75189
1186825 4612202
6794827 5587789
4953154 6271905
1585451 5584039
3657652 7324038
8393213 9664996
4238135 3865409
8288179 5055140
64388 2484585
7088246 2795846
3878391 1127272
1383239 9822994
5561296 5423184
6929042 7356931
7432120 526301
7654855 9460935
7565076 1135297
9923554 4449683
2550074 2518231
2358621 1509005
3690354 8724078
5105839 3268186
8323326 444841
2929427 3394018
8706216 8387715
2031339 17673
9840667 5100959
524144 3414579
3287862 7918316
960969 7453186
9430473 3236334
4371631 8615824
5581859 6995549
9513780 4295185
5804191 648285
9372363 4388753
7656939 2010897
2455738 6994554
2904924 5980266
6884333 5385165
5402839 1611140
9228452 1432024
4846603 7759858
8194526 9752596
7205782 650817
3887151 9155495
7771320 9152607
6148156 8258782
2553968 5869531
6517817 8178289
5083394 874511
2885408 8406532
5401087 2740334
1236952 5341146
3242664 822363
4949856 637637
2069661 8645503
8921713 4178308
6447256 6916265
7567082 9632592
8788087 6169390
5321997 3970586
2229368 9075759
4945291 3986505
4681146 7299688
8174199 1463108
2385992 9764541
5021227 3575959
1433458 7787079
1125795 6258179
6895816 4676122
5837977 6075651
2770311 8965477
8398094 7276042
6908634 9217567
5386957 8481529
2452115 5696722
7288833 3225306
7211811 7197835
4497524 2234124
6213584 4409310
4173851 5188075
8764035 8599577
AC output:

Code: Select all

5970576
3138852
Deficit
2015548
Deficit
Deficit
35592
Deficit
Deficit
32532
Deficit
Deficit
Deficit
Deficit
1412334
Deficit
Deficit
Deficit
7242228
Deficit
Deficit
Deficit
Deficit
2236356
Deficit
Deficit
Deficit
1489725
Deficit
828672
Deficit
Deficit
Deficit
Deficit
Deficit
191058
Deficit
Deficit
Deficit
Deficit
Deficit
1911006
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
509752
Deficit
Deficit
Deficit
Deficit
4872744
Deficit
Deficit
8995008
1708257
Deficit
7733392
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
1687228
2326725
Deficit
3405604
Deficit
Deficit
Deficit
15712182
8108466
4142162
5752716
8250416
Deficit
4330838
8671608
Deficit
Deficit
13318164
Deficit
Deficit
6732312
Deficit
9169540
Deficit
Deficit
83856
Deficit
10825644
Deficit
986748
Check input and AC output for thousands of problems on uDebug!
Top
Post Reply

Return to “Volume 105 (10500-10599)”