how to solve this problem ?
Can you post links to similar problems.
Search found 119 matches
- Mon Sep 07, 2009 10:14 am
- Forum: Volume 116 (11600-11699)
- Topic: 11659 - Informants
- Replies: 31
- Views: 8625
- Sun Aug 30, 2009 2:42 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 20577
Re: 10020 - Minimal Coverage
input: 1 4 0 1 2 5 1 3 3 4 0 0 output: 3 0 1 1 3 2 5 #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cctype> #include<cassert> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<deque> #include<map> #include<set> #include<iterator> #inclu...
- Sat Aug 29, 2009 9:08 pm
- Forum: Volume 116 (11600-11699)
- Topic: 11643 - Knight Tour
- Replies: 12
- Views: 3009
Re: 11643 - Knight Tour
I added this test case to your input and my AC output is 5 8 1 1 2 2 4 4 5 5 1 5 2 4 5 1 4 2 Case 1: 6 Case 2: 8 Case 3: 34 Case 4: 12 Case 5: 18 Case 6: 24 Case 7: 26 Case 8: 4 Case 9: 6 Case 10: 16 btw you can try your input outputs at uvatoolkit.com for hints look at this thread http://forums.top...
- Thu Aug 27, 2009 10:55 pm
- Forum: Volume 116 (11600-11699)
- Topic: 11651 - Krypton Number System
- Replies: 5
- Views: 3026
Re: 11651
thanks , nice trick.
- Tue Aug 25, 2009 3:58 pm
- Forum: Volume 8 (800-899)
- Topic: 802 - Lead or Gold
- Replies: 20
- Views: 10953
Re: 802 - Lead or Gold
i got AC on 10089 but this problem is giving me trouble when i've vectors like (0,0,q) or (0,q,r). If all were positive i could convert it to 10089 by multiplying the lcm of (p,q,r) to make the ratio equations equal. But this zero is messing the whole thing. Any tricks , can we add newEPS=1e-3 in pl...
- Tue Aug 25, 2009 1:01 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10089 - Repackaging
- Replies: 41
- Views: 14564
Re: 10089 - Repackaging
I've a O(n) after sorting. If the angle between 2 consecutive ,x{n} and x{n+1} > 180 , then we report false because we can translate the axis to x{n+1} and it will be < 180. Good stuff. Thanks mf for teaching me this. Generalising this to n - dimensions is a good. All i understand is reduce it to n-...
- Tue Aug 25, 2009 9:17 am
- Forum: Volume 100 (10000-10099)
- Topic: 10089 - Repackaging
- Replies: 41
- Views: 14564
Re: 10089 - Repackaging
I knew that one. Didn't see it . It is just subtraction of 2 vectors and then making the independent components equal to 0. Now, to answer why it's useful. To check that you can make a zero vector, you basically need to check that your collection of vectors spans an angle of 180 degrees or more, i.e...
- Tue Aug 25, 2009 1:49 am
- Forum: Volume 100 (10000-10099)
- Topic: 10089 - Repackaging
- Replies: 41
- Views: 14564
Re: 10089 - Repackaging
Well, isn't it obvious? A linear combinations of vectors (s2 - s1 , s3 - s1 ) is zero if and only if the same linear combination of vectors (s1 , s2 , s3 ) is a vector with three equal components, namely, all equal to this linear combination of s1 's. It's just simple algebra and manipulations of s...
- Tue Aug 25, 2009 1:10 am
- Forum: Volume 100 (10000-10099)
- Topic: 10062 - Tell me the frequencies!
- Replies: 235
- Views: 36645
Re: 10062 - Tell Me the Frequencies!
uvatoolkit.com has program which accepts inputs and produces outputs for AC solution. You can generate some test cases and check it if it is the same as uvatoolkit.com. It doesn't have source , only it produces output for AC solution.
- Mon Aug 24, 2009 12:26 pm
- Forum: Volume 116 (11600-11699)
- Topic: 11651 - Krypton Number System
- Replies: 5
- Views: 3026
11651 - Krypton Number System
any hints ?
- Sun Aug 23, 2009 7:13 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10089 - Repackaging
- Replies: 41
- Views: 14564
Re:
Hi! I have an other algorithm that is correct, and got AC. My algorithm goes like this : We treat is as the vectors on the plane. if the package is (s1,s2,s3) it is count as an vector [s2-s1,s3-s1]. And our problem is to find whether starting from point (0,0) you can return there. And that's all.. ...
- Sat Aug 15, 2009 4:28 pm
- Forum: Algorithms
- Topic: Longest ordered subset
- Replies: 15
- Views: 4748
Re: Longest ordered subset
i implemented Range tree which works for unique (x,y) pairs ie all x's and y's are different. How do we incorporate for equal values .My buildtree goes into infinite loop if i have unique x values because i split on left and right based upon median . If x < med then left, otherwise x>=med right. Now...
- Sat Aug 15, 2009 3:03 am
- Forum: Algorithms
- Topic: Longest ordered subset
- Replies: 15
- Views: 4748
Re: Longest ordered subset
i'm really thankful to your replies and help on problems. I sometimes don't understand or vaguely understand what you wrote. I come back later and on an another day i re-read it and understand it. Only this time it was months ago :) Well i tried commenting that line and running it and it passed. But...
- Fri Aug 14, 2009 3:24 pm
- Forum: Algorithms
- Topic: Longest ordered subset
- Replies: 15
- Views: 4748
Re: Longest ordered subset
def increase(self, x, y, val): """Changes the value of point (x, y) to the maximum of val and its old value.""" self.increase1(y, val) if self.mid is not None: if x < self.mid: self.left.increase(x, y, val) ************* self.right.increase1(y, val) ******************** else: self.right.increase(x,...
- Mon Aug 10, 2009 6:45 am
- Forum: Algorithms
- Topic: optimal binary search trees
- Replies: 1
- Views: 1817
optimal binary search trees
in the obst optimization by knuth we do min (C[i,k-1] + C[k+1,j]) for all k such that r[i,j-1]<=k<=r[i+1,j] why doesn't this k run n/2 times or n/4 times in each loop , why is it a constant ? I view it as all nodes of left tree's -> right subtree and right tree's -> left subtree. If the total nodes ...