## Search found 119 matches

Thu Mar 19, 2009 11:13 am
Forum: Algorithms
Topic: minimal boxes
Replies: 1
Views: 1567

### minimal boxes

You are given n 3D empty boxes. you have to pack them such that the total number of boxes are minimum. You can pack box A in box B if A.x < B.x AND A.y < B.y AND A.z < B.z. (n<=500) problem 013 from mipt. How do we solve this problem ? My algorithm was 1) sort the boxes. ( X increasing , Y and Z dec...
Wed Mar 18, 2009 8:55 pm
Forum: Algorithms
Topic: 15 queens
Replies: 1
Views: 2345

### 15 queens

Any hints how to solve 15 queens in less than 2 secs ? Not precalculating answer. I could do this only in 3 secs.basic brute force with bitmasks. something like while (poss != 0) { poss^=place = poss & -poss; dotry(row|place, (left|place)<<1, (right|place)>>1); } . I do also cut down the time using ...
Sun Mar 15, 2009 3:50 pm
Forum: Algorithms
Topic: how to find righmost and leftmost K( >=1 ) digit in n^m?
Replies: 4
Views: 2118

### Re: how to find righmost and leftmost K( >=1 ) digit in n^m?

for the last right k digits you can do modular exponentiation with base 10^k. like 2^5 % 10 if you want the last 1 digit or 2^20 % 100 if you want last 2 digits. First k digits can be got by logarithms as long as your log function is accurate. first 10 digits of k=3^53 is ? log10(k) = 53* log10(3) =...
Sat Feb 28, 2009 12:49 am
Forum: Volume 115 (11500-11599)
Topic: 11579 - Triangle Trouble
Replies: 20
Views: 10347

### Re: 11579 - Triangle Trouble

i got AC on this problem but i missed the insight using the sort and checking the triplets for validity area. Can you tell me why this is true ? I could figure out that with a fixed base, the area of triangle is maximum when the other 2 sides are almost equal to each other. I reasoned it as follows ...
Fri Feb 27, 2009 1:35 pm
Forum: Volume 115 (11500-11599)
Topic: 11582 - Colossal Fibonacci Numbers!
Replies: 8
Views: 1825

### Re: 11582 - Colossal Fibonacci Numbers!

You and sohel are right. It is a fibonacci sequence , so a first occurance of 0,1 starting with index > 2 solves the problem..My bad
Fri Feb 27, 2009 12:44 pm
Forum: Volume 115 (11500-11599)
Topic: 11582 - Colossal Fibonacci Numbers!
Replies: 8
Views: 1825

### Re: 11582 - Colossal Fibonacci Numbers!

Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case. If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2 how do you find the period of this ? Any thing easier than KMP. If the values were u...
Fri Feb 27, 2009 8:16 am
Forum: Volume 115 (11500-11599)
Topic: 11582 - Colossal Fibonacci Numbers!
Replies: 8
Views: 1825

### Re: 11582 - Colossal Fibonacci Numbers!

i got accepted by a lame method. How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers. Anyone used floyd. vahid, you are doing it wrong. a^b %n != a^b % p where p is the period, it could be within p<=6*...
Thu Feb 26, 2009 11:58 pm
Forum: General
Topic: Something wrong with links to problems
Replies: 3
Views: 4573

### Re: Something wrong with links to problems

Search this forum for "You are not authorised to view this resource". You have to append com_onlinejudge.
Tue Feb 24, 2009 10:06 pm
Forum: Algorithms
Topic: Longest ordered subset
Replies: 15
Views: 4780

### Re: Longest ordered subset

---------------------------------------Point P -------------Point X ************ ************ ---------------------Point Y ******************** -------------------------- Point Z *************************** *************************** *************************** The sequence of points is X , Y,Z,P....
Tue Feb 24, 2009 11:51 am
Forum: Algorithms
Topic: Longest ordered subset
Replies: 15
Views: 4780

### Re: Longest ordered subset

{ 1,1 }, { 2,3 }, { 3,2 }, { 4,3 }-> 1st,3rd,4th { 1,1 }, { 2,3 }, { 3,2 }, { 3,4 }-> 1st,2nd,4th { 1,2 }, { 2,3 }, { 3,2 }, { 4,4 }-> 1st,2nd,4th , When we come to (4,4) we should select (2,3) not (3,2) even though (3,2) < (4,4). Dp algorithm is correct but in the range tree , it has to return a se...
Tue Feb 24, 2009 9:50 am
Forum: Algorithms
Topic: Longest ordered subset
Replies: 15
Views: 4780

### Re: Longest ordered subset

for j = 1..i-1: if y[j] <= y[i] and z[j] <= z[i]: v[i] = max(v[i], v[j] + 1) When you say this . { 1,1 }, { 2,3 }, { 3,2 }, { 4,3 }-> 1st,3rd,4th { 1,1 }, { 2,3 }, { 3,2 }, { 3,4 }-> 1st,2nd,4th When you are at (6,3) , you have to check for both (5,1) (4,2) in first case and (4,3) (5,2) in second c...
Mon Feb 23, 2009 11:54 pm
Forum: Algorithms
Topic: Longest ordered subset
Replies: 15
Views: 4780

### Re: Longest ordered subset

How do you compute when there are 2 largest values ? Why isn't it the smallest largest value. What if we have x,y < (x1,y1) (x2,y2) ie x<x1 && y<y1 and x<x2 && y<y2 but x1 < x2 and y1> y2. Which one do i choose ? My understanding of your post is if we have a sequence x1 < x2 < x3 <x4... for x1 you f...
Mon Feb 23, 2009 11:23 pm
Forum: Algorithms
Topic: Longest ordered subset
Replies: 15
Views: 4780

### Re: Longest ordered subset

Can you throw some light on it ? . But how does range trees apply here .
Sun Feb 22, 2009 5:32 pm
Forum: Algorithms
Topic: Expected value and combinatorics problem
Replies: 0
Views: 1312

### Expected value and combinatorics problem

i've been trying to solve expected value and combinatorics problems in uva contests or topcoder but i fail them miserably. Most of the times when i see a solution i can understand that. How do i improve on this area ? Any books for practice or set of problems that gradually makes you better. Most of...
Sun Feb 22, 2009 3:34 am
Forum: Algorithms
Topic: minimize sum of manhattan distance
Replies: 2
Views: 3260

### Re: minimize sum of manhattan distance

Thanks for the hints. I missed the independent part , the combining part. This gets correct for my random inputs. Any suggesions on the below code or better ways. I get complexity as O(nlogn*d) where d is the dimension. doX() sort(v.begin(),v.end(),cmpx); int n=v.size(),i; vector<int> diff(n,0); int...