Search found 48 matches

by red_apricot
Tue Dec 23, 2014 9:07 am
Forum: Volume 116 (11600-11699)
Topic: 11633 - Food portion sizes
Replies: 2
Views: 919

Re: 11633 - Food portion sizes

My model is the same as Nahiyan Kamal's. So, S-the-portion-size is any real number between max{w }/3 and max{w }. We are to find a "good" rational approximation to this optimal size. Nwo, we are not given any tolerance level as to which approximations are good enough. Maybe I'm missing something imp...
by red_apricot
Mon Dec 08, 2014 2:17 pm
Forum: Volume 116 (11600-11699)
Topic: 11612 - Sultan and Khairun Shundori
Replies: 0
Views: 667

Re: 11612 - Sultan and Khairun Shundori

OK, from what I get, we are required to find a Hamiltonian cycle with no self-intersections, and we don't care about the length? Meaning, that length does not have to be minimal among all such cycles?
by red_apricot
Fri Dec 05, 2014 6:43 am
Forum: Volume 115 (11500-11599)
Topic: 11598 - Optimal Segments
Replies: 5
Views: 3114

Re: 11598 - Optimal Segments

OK, I seem to pass all the cases I can think of, but still WA. Any ccomments on the below code?

Code: Select all

Spoiler deleted
EDIT: Accepted now, thanks Brian for pointing out nasty cases such as

Code: Select all

1
12 6
(3 2 X X) (X) (X 1) (1 X 1) (X) (X)
Good problem with good data.
by red_apricot
Fri Nov 21, 2014 10:16 am
Forum: Volume 106 (10600-10699)
Topic: 10614 - Dreadful Vectors
Replies: 11
Views: 6845

Re: 10614 - Dreadful Vectors

OK, so for cases like [1,2,3] * [4,5,6] x [7,8,9] the output should be "Bang!", since the problem statement says "*" and "x" have the same priority. Just in case anyone is wondering. EDIT: Hm, for -[1,2,3] -1-2-3 one should output "Bang!" (according to uvatoolkit.com), although it is a perfectly OK ...
by red_apricot
Fri Nov 21, 2014 4:31 am
Forum: Volume 12 (1200-1299)
Topic: 1206 - Boundary Points
Replies: 2
Views: 1586

Re: 1206 - Boundary Points

Thanks Brian. Got AC now. Yes, this is a clear-cut Convex Hull problem with small n, but with very good input.
by red_apricot
Thu Nov 20, 2014 9:59 am
Forum: Volume 12 (1200-1299)
Topic: 1206 - Boundary Points
Replies: 2
Views: 1586

Re: 1206 - Boundary Points

The problem's name is "Boundary Points", so initially I thought we have to print the points lying on edges as well, not only on corners. OK, now it is clear that this problem is clear-cut convex hull. However, I'm getting WA. My question is: if, for instance, the point is given as (-3.24324,4.4) we ...
by red_apricot
Tue Nov 11, 2014 11:55 am
Forum: Volume 12 (1200-1299)
Topic: 1201 - Taxi Cab Scheme
Replies: 0
Views: 1106

1201 - Taxi Cab Scheme

Thanks Brian for opening the thread. My Hopcroft-Karp in O(n^3) yields TLE, so I wonder is there any better way. Here one ride precedes another or they may incomarable, so LIS is not the way to go either.
EDIT: Never mind, got Accepted (with poor timing though).
by red_apricot
Tue Sep 16, 2014 3:37 am
Forum: Volume 10 (1000-1099)
Topic: 1052 - Bit Compressor
Replies: 7
Views: 5143

Re: 1052 - Bit Compressor

I got AC -- had to resort to memoisation... I changed the above code to handle cases both sample and found above, but still it was WA. Thanks.
by red_apricot
Mon Sep 15, 2014 6:37 am
Forum: Volume 10 (1000-1099)
Topic: 1052 - Bit Compressor
Replies: 7
Views: 5143

Re: 1052 - Bit Compressor

This one seems to be a nice backtracking problem, and this is my code. Anyone has an idea on why it gets WA? /* * 1052. Bit Compressor * m: the length of the original message * n: the number of 1's in the original message */ #include <assert.h> #include <ctype.h> #include <stdio.h> #include <stdlib....
by red_apricot
Fri Jul 25, 2014 5:15 am
Forum: Volume 100 (10000-10099)
Topic: 10040 - Ouroboros Snake
Replies: 20
Views: 4344

Re: 10040 - Ouroboros Snake

OK, here is my solution so far -- based solely on Euler cycles. Thanks to Per's post somewhere here I did figure out the way to generate lex-smallest Euler cycl.e The only problem is that this code works for n <= 20, and for n=21 stack overflows. Any ideas how to improve the code? /* */ #include <as...
by red_apricot
Wed Jul 23, 2014 9:33 am
Forum: Volume 100 (10000-10099)
Topic: 10040 - Ouroboros Snake
Replies: 20
Views: 4344

Re: 10040 - Ouroboros Snake

I can construct the parts of the Euler cycle, but my problem comes when those individual simple cycles have to be glued together to produce the lexicographically smallest bitstring... Short of the FKM algorithm, any ideas on how the cycles can be combined?
by red_apricot
Tue Jul 08, 2014 5:38 am
Forum: Volume 12 (1200-1299)
Topic: 1229 - Sub-dictionary
Replies: 17
Views: 8307

Re: 1229 - Sub-dictionary (Why WA)

...and also this huge one: 100 ubghztqgvtenc prxdpnwyaamtb btxbiiajcsjlp goqotulirejot lteqzvhspkijh oactcxkkhzknr mlfjeeclhjghq qmgveexsmxljo cqdlmpkzqopcg bgpckbjshokeg fwsugvvnmizit pzltzvinsbvsf cxbtstcuiqvqo nyhfqbpvuwmwj vdmulrwscqhau acdvznnlaynbz tcgdnnvqgkfgh pchvcgicjqibi hznfhjrruazow alb...
by red_apricot
Tue Jul 08, 2014 5:30 am
Forum: Volume 12 (1200-1299)
Topic: 1229 - Sub-dictionary
Replies: 17
Views: 8307

Re: 1229 - Sub-dictionary (Why WA)

Ah, what about these random-generated ones: 13 yzkg vcjqig wsd w lzjshhp omol w wsd urhfyb atde lzjshhp unqqc urhfyb urhfyb wsd vcjqig nupe nupe lzjshhp wsd gkh ygjd wsd ygjd atde qyy vcjqig omol urhfyb ygjd nupe wsd atde vcjqig unqqc unqqc qyy wsd urhfyb yzkg ygjd lzjshhp omol atde lzjshhp wsd nupe...
by red_apricot
Mon Jul 07, 2014 9:29 pm
Forum: Volume 12 (1200-1299)
Topic: 1229 - Sub-dictionary
Replies: 17
Views: 8307

Re: 1229 - Sub-dictionary (Why WA)

What is the output for this:

Code: Select all

7
a b f 
b a
f e
e f
g a f
d e
c f
My out put is

Code: Select all

4 a b e f
So, my algo is to obtain the DAG and report all the SCCs with cardinality >= 2 or with indegree 0. Still WA.
by red_apricot
Sun Jul 06, 2014 8:14 am
Forum: Volume 109 (10900-10999)
Topic: 10923 - Seven Seas
Replies: 28
Views: 11674

Re: 10923 - Seven Seas

One vagueness of the problem: "you move and then the ship moves" --- this constitutes *one* move.

Go to advanced search