## Friday, January 20, 2012

### Hacker Cup 2012 - 3 problems solved.

I just solved 3 questions. Here are some of my comments:

1. Alphabet Soup
Just use 8 counters to count the numbers of the key letters. The solution can be easily deduced by those values.

2. Auction
My approach is trying to construct a directed graph based on the 'better' relation. This graph constructed should be acyclic. Every root you found should be Bargain product. And every leaves should be Terrible Deal product. To save the computation time, I just used an ArrayList to model the computation mentioned above.

3. Billboards
I just use brute force method for this problem. The fontsize are reducing during the iteration.
To make the verification easier, I assume there is a cursor in the billboard. When I insert a word to the billboard, the cursor move. If the cursor goes outside of the billboard, I reset and try another iteration with a smaller fontsize.

1. plzz explain Billboards once again !!

2. Auction:

Could you please explain me how the hell you are handling 10^18 integers? Twice for price and weight?!

3. Hi! Same Q here for Auction. Even if you store roots and leaves only, just enumerating all the products takes what time? I've never beat that ;(

4. I use arraylist, and i just store the bargain and bad deal info. As i increase, we don't need to keep all 10^19 nodes.

1. But surely you have to keep track of all existing products to determine which are the new bargains and terrible deals when the next product comes along?

2. We mostly likely need to calculate every Pi and Wi.
even N is very very large.

3. Of Course, you can remove the used products in the list during your calculation.

4. The timer expired. I couldn't upload my Alphabet soup code:

C'est la vie

5. Adhiraj, can use specifiy ur question?

6. I don't quite know how to do this within the 6 minutes! Checking 10^18 items doesn't seem possible in such a limited time...

7. 10^18 just the upper limit of N... It doesn't means, 10^18 must appear in the download input data set. anyhow, my algorithm is O(r*N)... where r is some constant<N.

8. It seems impossible to calculate pi and wi for all the N in 20 test cases in 6 minutes.. (as the instruction clearly says,: "Your program will need to solve the input file in less than 6 minutes."

Besides, I don't see why an auction will have so many products :P Bad facebook! :)

9. In my run I got 10 cases with numbers 10^17 like these:

789870595193472657 5360341 675784 8600975 754947 876155896 890899377 754304700 203276021

It's not an option to crunch them on my notebook in five minutes.

10. Kevin,

Earlier I solved this problem in O(r*N) but ran out of time as many test cases have N close to 10^17, then I optimized it to O(M*K) which is way lesser than O(r*N) but still I am running out of time, as some test cases have M*K close to 10^13

11. still stuck on billboards :(

12. To Anirvana:

If so, my current approach may be not sufficient. First, I assume may not need to compute Pi, Wi for all i.

Maybe there is a 'method' to skip i to next Bargain product(i+x) or next Terrible product(i+y) by current i and M,K,A,B,C,D?

Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

But when I look at these formula again, it seems not make sense that this method exists...

13. I just timed my program (with java) with Pavel's testing data:

789870595193472657 5360341 675784 8600975 754947 876155896 890899377 754304700 203276021

It just process 10^7 product in each 4 seconds. The average size of the arraylist is just 16 to 22. Memory is not a problem, just the time...

14. Kevin,

you do not need to check N (Price, Weight) pairs. Because the values for (Pi,Wi)start repeating after an interval of LCM(M,K) and you can express the number of bargains and terrible in terms of N/LCM(M,K)

Can you please check how much time your code takes to process this(http://pastebin.ca/2105167) input file?

15. Anirvana,

Thanks for your hints. This helps a lot. But I just check whether (p1,w1) pair repeats again in i iteration instead of finding LCM.

But the program still need a long time to run.

16. Auction:
How to find a terrible and bargain deals?
with this input: 11 2 3 5 7 11 13 17 19
we get sets of price and weight
2, 3
1, 1
5, 2
4, 5
3, 7
2, 6
1, 3
5, 1
4, 2
3, 5
2, 7

why there are 3 terrible and 1 bargain product?

17. Bargain:(2), price:1, weight:1
Terrible Deal:(3), price:5, weight:2
Terrible Deal:(4), price:4, weight:5
Terrible Deal:(5), price:3, weight:7

18. Kevin Wong...i've made the program..nd it works perfectly..thanx anyway...AND now im stuck with Auction...so i was wondering if u can help me out with that..10^18 input ??

19. I have an idea, but no time to implement.
Since m is <=10^7, we can use an array with int as index.

Define an array nextPi[P=1..M] = the value of next Pi+1 value when current P = Pi. We can do this because 1<Pi<=M

Define an array skip[P=1..M] = how many index(s) have to skip if current P=Pi and so that Pi+s<=P and no Pj<P where i<j<s.
This can be calculate in O(M.logM)

Using skip[], we can skip the iteration and do the faster 'better' relation search.

However, we have to use this a approach in these 4 cases:
- Price comparing with existing Bargain
- Price comparing with existing Terrible deal
- Weight comparing with existing Bargain
- Weight comparing with existing Terrible deal

20. Another idea, we can consider this is a search on a M*K grid.
and (Pm,Wk) is on each node. Every Bargain and Terrible found can greatly reduce this search space.

Also, not all points in M*K grid is generated by the random number ganerator. To determine whether (Pi,Wi) is generated from this, we can use the chinese reminder theorem.

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

For example, we first calculate array P[1..m] and W[1..k].
Then we locate the Pi and Wi in each array and find out locate
locp and locw.

If (Pi,Wi) is from the generator, there may exist e such that

e=r1*m+locp
e=r2*k+locw

and using reminder theorem, we can check if there exists e such that

e%m = locp
e%k = locw

1. http://www.cut-the-knot.org/blue/chinese.shtml

Two simultaneous congruences

n = n1 (mod m1) and
n = n2 (mod m2)

are only solvable when n1 = n2 (mod gcd(m1, m2)). The solution is unique modulo lcm(m1, m2).

(When m1 and m2 are coprime their gcd is 1. By convention, a = b (mod 1) holds for any a and b.)