Search found 20 matches

by Hikari9
Fri Jun 10, 2016 1:17 pm
Forum: Volume 101 (10100-10199)
Topic: 10149 - Yahtzee
Replies: 20
Views: 11566

Re: 10149 - Yahtzee

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 h...
by Hikari9
Fri Jun 10, 2016 10:34 am
Forum: Volume 10 (1000-1099)
Topic: 1052 - Bit Compressor
Replies: 7
Views: 5098

Re: 1052 - Bit Compressor

Oh, my bad. Apparently, one can't compress "11" into "10" :-?
by Hikari9
Fri Jun 10, 2016 10:24 am
Forum: Volume 10 (1000-1099)
Topic: 1052 - Bit Compressor
Replies: 7
Views: 5098

Re: 1052 - Bit Compressor

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

Code: Select all

32 27
10000010011110011
00
by Hikari9
Tue Dec 15, 2015 7:36 pm
Forum: Volume 130 (13000-13099)
Topic: 13040 - Flyovers of Khaka
Replies: 0
Views: 1299

13040 - Flyovers of Khaka

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 cre...
by Hikari9
Wed May 06, 2015 5:17 pm
Forum: Volume 7 (700-799)
Topic: 710 - The Game
Replies: 11
Views: 7030

Re: 710 - The Game

For all solvers, do take note that the only moves you can do are left turn, right turn, and straight.
by Hikari9
Fri Oct 25, 2013 6:54 pm
Forum: Volume 2 (200-299)
Topic: 257 - Palinwords
Replies: 16
Views: 5500

Re: 257 wa

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 :\
by Hikari9
Fri Sep 20, 2013 9:17 pm
Forum: Volume 101 (10100-10199)
Topic: 10125 - Sumsets
Replies: 50
Views: 15146

Re: 10125 - Sumsets

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, th...
by Hikari9
Fri Sep 20, 2013 6:42 pm
Forum: Volume 101 (10100-10199)
Topic: 10128 - Queue
Replies: 9
Views: 7698

Re: 10128 - Queue

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 of fir...
by Hikari9
Mon Sep 16, 2013 7:51 pm
Forum: Volume 104 (10400-10499)
Topic: 10451 - Ancient Village Sports
Replies: 22
Views: 9423

Re: 10451 - Ancient Village Sports

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 problem...
by Hikari9
Sun Sep 15, 2013 6:31 pm
Forum: Volume 4 (400-499)
Topic: 493 - Rational Spiral
Replies: 13
Views: 3306

Re: 493 wastes me a lot of time, and it haven't stopped.(SOS

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+750]=...
by Hikari9
Sun Sep 01, 2013 8:42 am
Forum: Volume 115 (11500-11599)
Topic: 11572 - Unique Snowflakes
Replies: 36
Views: 12176

Re: 11572 - Unique Snowflakes

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?
by Hikari9
Sun Aug 25, 2013 12:50 pm
Forum: Volume 2 (200-299)
Topic: 275 - Expanding Fractions
Replies: 47
Views: 21603

Re: 275

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. .46354883081155433287482806...
by Hikari9
Thu Aug 22, 2013 7:20 pm
Forum: Bugs and suggestions
Topic: 126 - Errant Physicists incorrect sample output
Replies: 0
Views: 1314

126 - Errant Physicists incorrect sample output

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 sa...
by Hikari9
Thu Aug 22, 2013 7:08 pm
Forum: Volume 1 (100-199)
Topic: 126 - The Errant Physicist
Replies: 25
Views: 3382

Re: 126 The Errant Physicist

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 x0y...
by Hikari9
Fri Jul 05, 2013 8:56 pm
Forum: Volume 8 (800-899)
Topic: 846 - Steps
Replies: 30
Views: 15739

Re: 846 - Steps

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

Go to advanced search