### Kaga2s's blog

By Kaga2s, 6 years ago, ,

The USACO November 2013 contest has began. Link

• +2

 » 6 years ago, # |   +1 Thanks for reminding!!!I almost forgot about it.
 » 6 years ago, # | ← Rev. 2 →   +1 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.
 » 6 years ago, # |   +1 Can anyone tell me what is the level of this contest ?Is it like div2 or div1 or in between ?
•  » » 6 years ago, # ^ |   0 When you start, you're in the bronze division. It's like B-C div2 problrms.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 6 years ago, # ^ |   +16 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.
 » 6 years ago, # | ← Rev. 6 →   0 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.pngcodeforces:http://store2.up-00.com/2013-11/1384809729842.pngspoj:http://store2.up-00.com/2013-11/1384809729943.png
•  » » 6 years ago, # ^ |   +6 Really? I didn't have any. Just a slow server and one "Judgement failed".
•  » » » 6 years ago, # ^ |   0 sorry , it was a virus on my computer
 » 6 years ago, # |   +18 Is there any neat solution for the second problem in Gold?
•  » » 6 years ago, # ^ |   +8 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
•  » » 6 years ago, # ^ |   +5 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 from C, 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -9 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.)
•  » » » » 6 years ago, # ^ |   +6 The contest should be over. And if you can't make sure your contest ends when it's supposed to, it's unfair anyway.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +54 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.
•  » » » 6 years ago, # ^ |   0 That's exactly what I've been looking for! Thanks a lot, Scotty ;)
•  » » » 6 years ago, # ^ |   0 is there a neat way to find the coordinates of the two points where the two tangents touch the circle?
•  » » » » 6 years ago, # ^ |   0 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).
•  » » 6 years ago, # ^ |   +13 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +10 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")
•  » » » » 6 years ago, # ^ |   0 Actually you only need to do one of those half-planes and you wouldn't have to divide by two at the end.
 » 6 years ago, # |   0 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"
•  » » 6 years ago, # ^ |   -7 What do you mean by "them"? Results?
•  » » » 6 years ago, # ^ |   0 Yes.
•  » » 6 years ago, # ^ |   +11 They usually publish results one week after the end of the contest... What do they mean by "soon"?
•  » » » 6 years ago, # ^ |   0 i asked him why one week later, really even in ioi its announcing in 3 days :D
•  » » 6 years ago, # ^ |   +24 Results of Usaco announced soon? Wake up man...
 » 6 years ago, # |   0 any hints for third problem gold?
•  » » 6 years ago, # ^ |   +13 Dynamic programming: for each subset of coins calculate the maximum number of products that can be purchased.
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   +5 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.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Let's say the buying works like this: we buy first i products (doesn't matter how) and next, we buy A[i][j] more products using coin number j; 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), not O(N) to answer "how many products can we buy using just subset S of coins?", by trying all possible last coins used. Complexity O(K2K + NK), code
•  » » » » » 6 years ago, # ^ |   0 Thank you both pllk and Xellos I get it now
•  » » 6 years ago, # ^ | ← Rev. 4 →   +5 My bad. It is a wrong solution. :)
•  » » » 6 years ago, # ^ |   +5 Is this fast enough? 16! is a large number.
•  » » » » 6 years ago, # ^ |   +5 My bad :)
 » 6 years ago, # |   +16 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.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 But difference between hard and medium problems was too huge.
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   0 Who knows? may be...
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 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".
•  » » » » » » 6 years ago, # ^ |   +8 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 exceed And 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).
•  » » 6 years ago, # ^ |   0 As far, as I remember, the first contest of the year is always easier than following ones.
 » 6 years ago, # |   +18 I was shocked, but results are already available! Missed the perfect score because of one symbol :( Go check them out!
•  » » 6 years ago, # ^ |   0 can you tell me where i can get all the data ?
•  » » » 6 years ago, # ^ |   0 Test data is available at http://usaco.org/index.php?page=nov13problems
•  » » 6 years ago, # ^ |   0 Heh, for me it was 2 symbols. Something like this: a.resize(n); -> a.resize(sz); But I failed only one test, so it's a great luck for me)
 » 6 years ago, # | ← Rev. 3 →   0 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
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   -8 You never define "m", but you use it on a for loop: for(int i=0 ; i
•  » » » 6 years ago, # ^ |   0 No, that would be a compilation error. If you look better, you'll see int n,k,m;
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » » 6 years ago, # ^ |   +3 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 m initialized to a positive value could cause crashes quite easily.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 6 years ago, # ^ |   0 Since m has static storage duration, it shall be zero-initialized.
 » 6 years ago, # |   +31 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" :)
•  » » 6 years ago, # ^ |   +5 Ray Li is just that good
•  » » 6 years ago, # ^ |   +3 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 :)