The USACO November 2013 contest has began. Link

# | User | Rating |
---|---|---|

1 | Benq | 3539 |

2 | tourist | 3532 |

3 | wxhtxdy | 3425 |

4 | Radewoosh | 3316 |

5 | ecnerwala | 3297 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | Um_nik | 3260 |

9 | yutaka1999 | 3190 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 179 |

3 | tourist | 173 |

4 | Vovuh | 167 |

4 | PikMike | 167 |

4 | antontrygubO_o | 167 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 153 |

9 | 300iq | 153 |

The USACO November 2013 contest has began. Link

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/18/2019 17:29:14 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Thanks for reminding!!!I almost forgot about it.

Right on it... wait, it's 4 hours not 3. Crap. I though I'd get more practice before CERC, but I'd miss the train like this.

Oh yeah, major offtopic: this Sunday, CERC takes place.

Can anyone tell me what is the level of this contest ?

Is it like div2 or div1 or in between ?

When you start, you're in the bronze division. It's like B-C div2 problrms.

It has 3 divisions Bronze, Silver and Gold, each of them getting harder. If it is you first contest you need write Bronze, otherwise in division at what you was last year.

Maybe some will not be agree with me, but the level is kind of random for me... Some contests are a lot harder than others, even in the same division. This month, it seems the easiest contest since a long moment, and it's like Xellos said, "B-C" div2. But I will say it's more D div2 for third problem usually.

ads everywhere in USACO :(

Edit:I'm very sorry about this , it turned out that I'm only the one who is seeing the ads maybe there's a virus on my computer , I'm seeing flash ads and some word being a green linked if I hover on them it will open ads here's screen shot of some websitesUSACO:

http://store2.up-00.com/2013-11/1384809729661.png

codeforces:

http://store2.up-00.com/2013-11/1384809729842.png

spoj:

http://store2.up-00.com/2013-11/1384809729943.png

Really? I didn't have any. Just a slow server and one "Judgement failed".

sorry , it was a virus on my computer

Is there any neat solution for the second problem in Gold?

I was able to start just 45 minutes ago and I think it is still possible to start, so you should refrain from discussing problems for about 4 more hours

It should be fine now.

For each cow

C, partition the area in which visible cows can be (given by the circle and tangents to it fromC, non-white in the pic) like this:The number of cows in the gray area can be found by angle-sorting the points and doing prefix sums. The numbers of cows in colored areas are given by the tangent points on the circle and orientations — list all those tangent points, then angle-sweepline the answers for them. Ugly stuff.

Upd: Contest is over, solution on pastebin (basically the same idea as scott_wu's)

(I think I've had enough of Codeforces comments now.)

The contest should be over. And if you can't make sure your contest ends when it's supposed to, it's unfair anyway.

I thought the problem was quite nice. Here is my solution:

Each cow forms two tangent points with the circle. Consider the minor arc on the circle formed by those two points. It turns out that two cows can see each other if and only if their arcs intersect.

Therefore, we can just calculate the range of angles possible for each cow and solve the well-known problem of counting the number of pairwise intersections in a set of ranges (we need to be careful to handle the fact that the ranges are cyclic though). The total runtime is O(NlogN) since we must sort the list of angles.

That's exactly what I've been looking for! Thanks a lot, Scotty ;)

is there a neat way to find the coordinates of the two points where the two tangents touch the circle?

Yes. If you look at the radii of the tangent points as in Xellos' diagram, you can see that the points of tangency make angles of acos (r / R) with the location of the cow itself (r is the radius of the circle, R is the distance from the origin to the cow). We can find the angles of the tangent points by finding the angle of the cow (atan2 in C++ works great here) and then adding and subtracting acos (r / R).

I have a solution which is a bit more motivated than the one presented by scott_wu.

For each cow, there is a region it can see: it is bounded by the silo as well as the two tangent lines. The entire half-plane above the upper tangent line is visible, and similarly, the entire half-plane below the other tangent line is also visible.

In fact, we can simply add up the number of cows above the first tangent line and the number of cows below the second tangent line. Although this doesn't include the region between the cow and the silo, it also double counts the intersection of the two half-planes. Taken together, these two imperfections cancel out.

Because each pair of seeing-cows is counted twice, you simply divide the total sum by 2 at the end.

Finally, the problem is reduced to querying the number of cows in a halfplane determined by a tangent to the silo. This can then be reduced to counting the number of pairwise intersections of a set of ranges.

Here is a diagram of my solution above.

The number indicates the number of times the region is counted. Ideally, all of them would be 1, but this works too (if cow A is in cow B's "0 region", cow B is in cow A's "2 region")

Actually you only need to do one of those half-planes and you wouldn't have to divide by two at the end.

i sent a mail to Brain Dean and answered me 45 mins ago.

"I am working on them now, and hope to have them announced soon. The contest only ended an hour ago!

-- Brian"

What do you mean by "them"? Results?

Yes.

They usually publish results one week after the end of the contest... What do they mean by "soon"?

i asked him why one week later, really even in ioi its announcing in 3 days :D

Results of Usaco announced soon? Wake up man...

any hints for third problem gold?

Dynamic programming: for each subset of coins calculate the maximum number of products that can be purchased.

I don't know how to calculate the maximum number of products that can be purchased for each subset , but let's assume it can be done in O(N) for each subset so we hace complexity O(N*2^K) which is not fast enough

My time complexity is O(2^K*K*log(N)).

For each subset, we can go through every possible choice for the last coin added to the subset. Using dynamic programming we know the maximum number of products without the last coin. The maximum number of products with the last coin can be efficiently calculated using binary search and a prefix sum array.

Let's say the buying works like this: we buy first

iproducts (doesn't matter how) and next, we buyA[i][j] more products using coin numberj;A[i][j] is maximum possible. This can be calculated with bin-search or 2 pointers method, if we have the prefix sums of the sequence of products.Now, we only need

O(1), notO(N) to answer "how many products can we buy using just subsetSof coins?", by trying all possible last coins used.Complexity

O(K2^{K}+NK), codeThank you both pllk and Xellos I get it now

My bad. It is a wrong solution. :)

Is this fast enough? 16! is a large number.

My bad :)

i think problems at gold division was unbalanced , i have spent just a hour to solve first and third problems. After then i tried to find out solution for second problem for 3 hours.

It seemed to me like easy (1.), medium (2., although a bit too easy for my taste), hard (3., still had a nice solution that hex539 and scott_wu did). That's a good thing. A bad problemset is one with 3 easy or 3 hard problems, because it doesn't give you any learning experience.

But difference between hard and medium problems was too huge.

Not really. The 'hard' problem just required a good idea that lead to an easy implementation, so it seemed that way. Or maybe geometry is one of your weaker points (like mine), so it just seemed really hard to you.

Who knows? may be...

For what it's worth, the second problem was incomparably harder than the others to some of those of us who solved it as well. Like several others I spent most of my 4 hours on "sight" but only had the "AHA" moment about 15 minutes from the end.

That's definitely the hallmark of a satisfying problem, but also (IMO) one that isn't such a good fit for OI-style contest programming because there isn't much middle ground between "trivial brute force" and "100% correct".

Splitting a problem into subtasks is well possible. It's just that the authors chose not do it. Some examples for subtasks of

sight:in x% of the testcases, no 3 cows will be collinear

in x% of the testcases, all the cows will lie on another circle (or in some other way, so that it can be solved by a simpler angle-sweeping)

in x% of the testcases, the answer won't exceed

y/ will exceedAnd it just happens sometimes that the hard problem really just has a hard idea. Reminds me of day 1 of IOI 2011 (I didn't compete back there, just read the problems).

As far, as I remember, the first contest of the year is always easier than following ones.

I was shocked, but results are already available! Missed the perfect score because of one symbol :( Go check them out!

can you tell me where i can get all the data ?

Test data is available at http://usaco.org/index.php?page=nov13problems

Heh, for me it was 2 symbols. Something like this:

But I failed only one test, so it's a great luck for me)

First problem... I used set&vector for solution but it got s = Signal (crashed, exceeded memory limits, invalid syscall). Is my code giving MLE?

Code

Just a set and a vector shouldn't exceed the memlimit, but you can run it on your computer with all the testdata and check what it does.

You never define "m", but you use it on a for loop:

No, that would be a compilation error. If you look better, you'll see

`int n,k,m;`

He probably wanted to say that m is never initialized and I think he is right. There is no guarantee that m will always be 0 at the beginning.

Yes, that could be it. I'm not sure how auto-initialization works in g++ for global variables (I initialize all manually just to be sure), but

minitialized to a positive value could cause crashes quite easily.I changed but it got s again. But I was idiot. I coded O(NlogN) solution. I complied on my computer and there is not any problem with segmentation fault etc.

Since

`m`

has static storage duration, it shall be zero-initialized.Strange... two perfect scorers in gold div. One from USA, other from AUS. One from pre-college category, other from observer category. But both with same name... "Ray Li" :)

Ray Li is just that good

I know the Australian Ray Li in real life and I can tell you that they really are 2 different people. It is a funny coincidence :)