OJ Board

I've been getting WA for the past couple days playing with this, and I honestly am baffled as to the case(s) I'm missing. I've generated thousands of sample input games (~10k so far), ran them through the UVA Toolkit, and in every case my optimal score matched the toolkit's output. Typically I'll ...

Oh, my bad. Apparently, one can't compress "11" into "10"

I'm confused. Why is the answer for this test case NO? Can't the last two bits be decompressed into 111?

Problem description says:
"So the Government has decided to let Bodi travel each road only once and build some flyovers, which connects two notable places, so that he can complete his visit to all the notable places while going through every road in Khakha city."

I'm confused. Is this euler path ...

For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.

I think there is something wrong with the judge for this problem then. I submitted a program that checked for palindromes of lengths 3 and 4 only, and it got Accepted. However, it does not pass your input :\

well, as far as optimizations go, you can make up to O(n^3), heck even O(n^2).

O(n^4): brute force
O(n^3): DP - sort all data, make a for-loop for a, b, c, then get maximum a+b+c that is in the set (use hash_map for constant check)
O(n^2): DP - sort all data, store in memo all distinct pairs a+b ...

There is a formula for this problem using math ( I derived it using combinatorics )

After tedious calculations, I found out that the answer is just the equation

F(n,p,q) = abs ( stirling ( n-1, p+q-2 ) ) * nCr ( n, p+q-2 ) )

where abs(x) is absolute value,
stirling(n,k) is the stirling number ...

This is a precision-error prone problem. I had to tweak a lot in my code to get Accepted.
Well, after a lot of WAs, I found out the precision of the judge for this problem.

1. Read and compute values as doubles
2. Print answer as a float
3. Don't use epsilons

There are many formulas for this ...

You can actually check for reoccurences of fractions using a 2D boolean array to eliminate the O(nlogn) tree checking.
(although make sure to simplify the fraction first :D)
bool vis[1500][1500]; // will be able to hold for inputs upto 510000

...

// checking part
if( den!=0 && vis[num+750][den ...

The simplest O(n) algorithm implementation is basically a hashed map.
But it only helps slightly in runtime - I got 0.362s for STL map O(nlogn) while 0.212s for my hash map implementation...
Are there any alternatives that runs in O(n) aside from hash map?

A lot of input :D

Sample input:
0 3
231 369
337 727
105 440
546 709
181 932
188 566
59 590
38 722
171 342
109 739
38 114
489 526
320 601
145 818
612 899
2 594
0 728
20 380
614 838
945 946
0 0


AC output:
.
This expansion terminates.

.62601
The last 5 digits repeat forever ...

This problem has a glitch. Apparently, the sample output is not parallel with the output description.

It says that "The pair of lines that contain a product should be the same length--trailing blanks should appear after the last non-blank character of the shorter line to achieve this."
But in the ...

For everyone getting Presentation Error ,
apparently the judge program doesn't trim any trailing spaces... the heck -_-

I hope that the judge would fix their mistake.
In any case, matching this input/output would help :D

Sample Input:
x2
y-y
x2y2+3xy-4
x2-3x3+x5
24x-67xy7
-x5
x32+y21+2x3y42-1
-x ...

There is no strict precision to this problem. You just need to manipulate the formula.

Given two integers a, b, we want n such that n*(n+1) = 4*(b-a)-1
(Pascal Triangle formula)

In addition, when the range (a to b) is odd, we actually have n^2 = 4*(b-a)-1 because of the extra n .
Thus, we can get ...