Search found 251 matches

Fri Aug 06, 2010 12:29 pm
Forum: Volume 1 (100-199)
Topic: 121 - Pipe Fitters
Replies: 36
Views: 2337

Re: #121 - Pipe Fitters

By the way what's the output for this:

Code: Select all

``2.43 2.43``
This input was inspired by the fact sqrt(2) = 1.41, so the answer should be

Code: Select all

``5 skew``
.
However, most of the AC code returns

Code: Select all

``4 grid``
Sun Jun 27, 2010 10:45 pm
Forum: Volume 5 (500-599)
Topic: 550 - Multiplying by Rotation
Replies: 7
Views: 4236

Re: 550 Time Limit

@yiuyuho: you are right, the fact that L*(B^n-factor) is divisible by (B*factor-1) does not gurantee, that x -- the corresponding quotient -- is n digits long.
But my solution gets AC. The problem is erroneous, if somebody has a really correct solution, please post here your comments.
Fri Jun 04, 2010 9:20 pm
Forum: Volume 117 (11700-11799)
Topic: 11785 - Hypercube
Replies: 1
Views: 1876

Re: 11785-WA in hypercube .

Hey, I didn't check your code, but the thing is: there can be edges (i,j) such that either i < 0 or j < 0.
The answer is, of course, "NO".
Fri Apr 09, 2010 7:08 pm
Forum: Volume 117 (11700-11799)
Topic: 11755 - Table Tennis
Replies: 3
Views: 2357

11755 - Table Tennis

Input:

Code: Select all

``````1
WWWWWLLLLLWWWWWLLLLLWWWWWLLLLLWWWWWLLLLL
1.000 0.000
``````
Output: 0.00000
Sun Apr 04, 2010 12:01 pm
Forum: Volume 116 (11600-11699)
Topic: 11626 - Convex Hull
Replies: 5
Views: 3843

Re: 11626 --getting WA

The only tricky case I can think of is a rhombus:

Code: Select all

``````1
8
0 -2 Y
1 -1 Y
2 0 Y
1 1 Y
0 2 Y
-1 1 Y
-2 0 Y
-1 -1 Y
``````
output is the same. And I got it AC with upper envelope + lower envelope also.
Sat Mar 06, 2010 5:36 am
Forum: Volume 115 (11500-11599)
Topic: 11598 - Optimal Segments
Replies: 5
Views: 3096

Re: 11598 - Optimal Segments

My algo is: value is 0, if the i-th cell is special, otherwise it is given in the input; sm = sm[i-1] + value , thus the weight of the segment [i,j] is calculated as follows: (1ULL << sm[j]-sm[i-1]); pref = pref[i-1] + (is_special ? 1 : 0); Now suppose (j,k) be such a state that we have optimally di...
Wed Feb 10, 2010 7:00 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 8937

Re: 11394 - Digit Blocks

I solved it with multinomial coefficients -- i.e. without any DP except for a set to store some duplicating bitmasks. Got AC in 1.560. I now wonder how those fellows solve it in 0.000? We just enumerate all the bitmasks, and if the corresponding sum of digits is divisible by 5, we form all permutati...
Mon Feb 01, 2010 3:12 pm
Forum: Volume 117 (11700-11799)
Topic: 11766 - Racing Car Computer
Replies: 2
Views: 1756

Re: 11766 - Racing Car Computer

It was I who was lying when I said that (a,b) uniquely defines the configuration. Obviously it does not.
Mon Feb 01, 2010 8:59 am
Forum: Volume 117 (11700-11799)
Topic: 11766 - Racing Car Computer
Replies: 2
Views: 1756

Re: 11766 - Racing Car Computer

I haven't solved the problem yet. Still, I have a few remarks: i-th car is definitely lying if a[i]+1+b[i] > n; every pair (a[i],b[i]) _uniquely_ defines the configuration of the cars Now, if a particular car -- say, j-th -- is definitely lying in the above sense, and i-th car's data is plausible, t...
Sat Jan 23, 2010 5:43 pm
Forum: Volume 105 (10500-10599)
Topic: 10558 - A Brief Gerrymander
Replies: 6
Views: 4995

Re: 10558 - A Brief Gerrymander

1. Do Avenues run from South to North and Streets from West to East?
To put it simply, Avenues are vertical lines and Streets are horizontals, right?
2. "Riding" is a large rectangle we have obtained by S horizontal and A vertical cuts?
Fri Jan 22, 2010 8:37 am
Forum: Volume 106 (10600-10699)
Topic: 10626 - Buying Coke
Replies: 23
Views: 15723

Re: 10626 - Buying Coke

I would rather say that

Code: Select all

``ones_left = original_money - 8*cokes_bought - 5*fives_left - 10*tens_left``
Thu Jan 21, 2010 10:41 am
Forum: Volume 117 (11700-11799)
Topic: 11753 - Creating Palindrome
Replies: 8
Views: 3837

Re: 11753 - Creating Palindromes

Reversing the sequence and finding the length of its longest common subsequence with the original sequence. Th? answer is n-LCS. Now, LCS problem is still O(n^2). There is also a O(rlog(n)) algo, where r is the number of pairs (i,j) such that ai = bj...
Tue Jan 19, 2010 8:52 pm
Forum: Volume 117 (11700-11799)
Topic: 11753 - Creating Palindrome
Replies: 8
Views: 3837

11753 - Creating Palindrome

All I can think of is a lazy DP: the minimum cost of making a palindrome of s[i:j] is stored in a map if the cost is <= K...
Of course this is still O(n^2), but I thought that K's being small will make up for this deficiency... Any ideas?
Wed Jan 06, 2010 7:07 am
Forum: Volume 116 (11600-11699)
Topic: 11686 - Pick up sticks
Replies: 44
Views: 10375

Re: 11686 How can

Now I see how that color stunt is helpful in dfs. In the sample input above one edge is given twice, so it is easy to mistake it for a cycle during dfs, if one doesn't use colors.
Sun Jan 03, 2010 12:42 pm
Forum: Volume 8 (800-899)
Topic: 880 - Cantor Fractions
Replies: 24
Views: 17079

Re: 880 - Cantor Fractions

I would like to strongly emphasize that UVa264 and UVa880 are not one and the same: for instance, for input

Code: Select all

``7``
you would have

Code: Select all

``TERM 7 IS 1/4``
and

Code: Select all

``4/1``
respectively.