Search found 251 matches

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

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
by serur
Sun Jun 27, 2010 10:45 pm
Forum: Volume 5 (500-599)
Topic: 550 - Multiplying by Rotation
Replies: 7
Views: 4276

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.
by serur
Fri Jun 04, 2010 9:20 pm
Forum: Volume 117 (11700-11799)
Topic: 11785 - Hypercube
Replies: 1
Views: 1896

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".
by serur
Fri Apr 09, 2010 7:08 pm
Forum: Volume 117 (11700-11799)
Topic: 11755 - Table Tennis
Replies: 3
Views: 2384

11755 - Table Tennis

Input:

Code: Select all

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

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.
by serur
Sat Mar 06, 2010 5:36 am
Forum: Volume 115 (11500-11599)
Topic: 11598 - Optimal Segments
Replies: 5
Views: 3165

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...
by serur
Wed Feb 10, 2010 7:00 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 9051

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...
by serur
Mon Feb 01, 2010 3:12 pm
Forum: Volume 117 (11700-11799)
Topic: 11766 - Racing Car Computer
Replies: 2
Views: 1784

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.
by serur
Mon Feb 01, 2010 8:59 am
Forum: Volume 117 (11700-11799)
Topic: 11766 - Racing Car Computer
Replies: 2
Views: 1784

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...
by serur
Sat Jan 23, 2010 5:43 pm
Forum: Volume 105 (10500-10599)
Topic: 10558 - A Brief Gerrymander
Replies: 6
Views: 5052

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?
by serur
Fri Jan 22, 2010 8:37 am
Forum: Volume 106 (10600-10699)
Topic: 10626 - Buying Coke
Replies: 23
Views: 15833

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
by serur
Thu Jan 21, 2010 10:41 am
Forum: Volume 117 (11700-11799)
Topic: 11753 - Creating Palindrome
Replies: 8
Views: 3954

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...
by serur
Tue Jan 19, 2010 8:52 pm
Forum: Volume 117 (11700-11799)
Topic: 11753 - Creating Palindrome
Replies: 8
Views: 3954

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?
by serur
Wed Jan 06, 2010 7:07 am
Forum: Volume 116 (11600-11699)
Topic: 11686 - Pick up sticks
Replies: 44
Views: 10559

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.
by serur
Sun Jan 03, 2010 12:42 pm
Forum: Volume 8 (800-899)
Topic: 880 - Cantor Fractions
Replies: 24
Views: 17296

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.

Go to advanced search