## Search found 251 matches

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

### 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: 4458

### 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: 1990

### 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: 2535

### 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: 4096

### 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: 3384

### 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: 9558

### 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: 1924

### 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: 1924

### 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: 5259

### 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)
Replies: 23
Views: 16176

### 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: 4307

### 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: 4307

### 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: 11788

### 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: 18203

### 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.