USACO 2016-2017 February Contest

8 лет назад, # ^ |

The people who started the contest during the last possible moment are still competing until 16:00 UTC. There's a bit less than 3 hours left.

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

I couldn't solve the first one completely but I got 5 test cases with a dumb greedy algorithm. I sorted the intervals by starting time, and sorted the other time list. Then just greedily matched intervals to times. Would love an approach for this one.

For the second one, just make a huge array of ints of size N and initialize everything to zero. Set all broken ones to 1. Select the k length subarray with least sum (using sliding window/cumulative sum).

For the third one I imagined the whole grid as a graph with complete connectivity initially. The roads were edges we could not take. Then on this new graph, I ran component division using DFS and inside the main loop I checked if the edge being considered is in the "forbidden" edge list or not. So the DFS takes O(N² R) time which passes time limit. This can be optimized using hash table/BST. Now that we have marked connected components with different numbers, we just try all pairs in the K cow list and check if they are in the same component. If they are not, add one to the counter and finally print the counter. This was a cute one.

Will I get to gold with this performance?

EDIT: Fix math notation

→ Ответить

xiaowuc1

8 лет назад, # ^ |

The highest promotion boundary cut-off over the past couple years looks like 800, so unless the promotion boundary is higher than that, you should be promoted to gold.

→ Ответить

8 лет назад, # ^ |

What were the problems for silver?

→ Ответить

1: http://usaco.org/index.php?page=viewproblem&cpid=702

8 лет назад, # ^ |

2: http://usaco.org/index.php?page=viewproblem&cpid=703

3: http://usaco.org/index.php?page=viewproblem&cpid=704

→ Ответить

8 лет назад, # ^ |

...you can't access those unless you are silver.

→ Ответить

8 лет назад, # ^ |

Didn't know that. Here's a paste. Sorry for the inconvenience.

→ Ответить

nologic

8 лет назад, # ^ |

Silvers: DP(i,j), where i and j are positions of where we "start" looking from, therefore there will be n^2 states

→ Ответить

8 лет назад, # ^ |

Assuming you are talking about Problem 1, wouldn't that time out as N = 2e4?

→ Ответить

nologic

8 лет назад, # ^ |

← Rev. 2 →

Oh wait, that's the different problem, sorry.

For that problem you can sort the intervals by their Right point, then, you can look for a lowest point(in "Chickens" array) where it can still be placed. You can do that using binary search and using a set or, as I did, a full search in O(n) time, which did result in O(n^2), but passed TL :/

Usually, the TLE is when the number of operations is >= 1e9, in this case, however number of operations were less

→ Ответить

8 лет назад, # ^ |

1e9 is an overstatement. 1e8 is nearly always safe.

→ Ответить

kliu31415

8 лет назад, # |

+21

Hints for Platinum division:

BIT
Segtree
2d range tree. Needed a few optimizations to fit into ML. There's probably a faster way.

I derped on the first one because I didn't realize that rotating just one side wasn't enough — you had to check rotating both (in addition, I solved #3 first, so I copied my 2D range tree code from it instead of just using a simple 1D BIT, greatly overcomplicating the problem :( ).

→ Ответить

srijonm

8 лет назад, # ^ |

← Rev. 2 →

We can also use a BIT for Number 2 and a kind of 2D BIT for the Number 3 (although I am not sure if it works). Also, how did you optimize the 2D range tree? I tried that for more than 2 hours but could only get it to pass 10 test cases. I had 5 minutes left when I figured out the BIT solution, but when I submitted it (with seconds to spare), it only solved 3 test cases due to a small bug.

→ Ответить

AnonymousBunny

8 лет назад, # ^ |

I used a bit with an implicit segtree in each node; passed all cases. Code: http://ideone.com/sfKpb4

→ Ответить

giraffeh

8 лет назад, # ^ |

I've used Mo's algorithm with Fenwick tree in the third problem. Although my solution is O(N * sqrt(N) * log(N)), it passes all the tests within a second.

→ Ответить

sqrtdecompton

8 лет назад, # ^ |

← Rev. 2 →

I also used sqrt bucketing with Fenwick but initially didn't AC. Messed with the bucket size a little and then it passed. Interestingly if you make bucket sizes equal to sqrt(N * log(N)) then you can bring it down to O(N * sqrt(N * log(N))).

→ Ответить

Benq

8 лет назад, # ^ |

← Rev. 3 →

2D range tree --> MLE on test case 10 :( :(

One testcase wrong oops.

Passed with O(n²) on #2 somehow!

→ Ответить

sslotin

8 лет назад, # ^ |

For 3rd I wrote a 2D BIT on a smart hashmap. http://pastebin.com/DPemaJeW

It is O(n·log²n) time and memory, and I was actually a bit surprised it passed within a second.

→ Ответить

minimario

8 лет назад, # ^ |

+15

Here is an interesting solution, which doesn't involve 2D. Maybe it works, maybe it doesn't, because I haven't gotten a chance to submit: moo

Let's call the left cows a_i and the right cows b_i. Now, let p_i = a_{b_i}. Our goal is to count the number of pairs i < j such that p_i > p_j and |b_i - b_j| > k.

We use divide and conquer. At some step, we consider some pairs such that l ≤ i < j ≤ r. Now, from conquer we only need to count the pairs where $\text{[math]}$ and $\text{[math]}$ . Let's sort all the indices from l to r by b value, and process them least to greatest. Maintain 2 BIT's storing the p values (one for [l, mid] and one for (mid, r]) and query appropriately.

→ Ответить

AlwaysMerlin

8 лет назад, # ^ |

← Rev. 3 →

Did anyone else get time limit exceeded for platinum question 3 using an O(nlog²(n)) solution? I used a segment tree containing a binary search tree (AVL tree) at every node and it took about 4 second for a large test case on my machine. Obviously it was badly over the time limit on the judge's server.

→ Ответить

kliu31415

8 лет назад, # ^ |

If you didn't optimize the constant, then you got TLE. An easy way to optimize the constant is by using a Fenwick tree for the first dimension.

→ Ответить

srijonm

8 лет назад, # ^ |

Apparently, using a Fenwick tree for the first dimension is not sufficient. I got TLE and MLE using it. Also, I think we can make the solution use O (N logN) memory by compressing the values for the lower dimension.

→ Ответить

Bedge

8 лет назад, # ^ |

What do you mean about compressing the values for the lower dimension ? Isn't using segment tree contain a BST is already having O(N log N) memory ?

→ Ответить

http://pastebin.com/vR1hgnTJ

8 лет назад, # ^ |

My solution is simply $\text{[math]}$ and it passed all the cases within the time limit (the worst case runs in 881ms)

Here are the submission verdicts:

And here is the detail of my approach: Click Me!

→ Ответить

AlwaysMerlin

8 лет назад, # ^ |

I'm not having trouble solving the problem, I replaced the AVL tree with a splay tree and my solution takes < 200ms. I was just wondering if anyone else had to struggle to optimise an O(nlog²(n)) solution. If it is the intended complexity, then it seems a bit tight.

→ Ответить

Bedge

8 лет назад, # ^ |

Me using segment tree with AVL tree and only passed 7 cases, I thought O(N log N) is need :'(

→ Ответить

q234rty

8 лет назад, # ^ |

← Rev. 2 →

My $\text{[math]}$ solution passed for problem 3.(1099ms on max test)

The core idea:Within each block,instead of a BIT,consider a data structure that supports $\text{[math]}$ update and O(1) query. UPD: It's actually 1470ms on max test,sorry.

→ Ответить

kliu31415

8 лет назад, # ^ |

Apparently if you only check rotating the bottom, you get 3/10 test cases (1, 4, 5), but if you check rotating the top, you get 8/10 test cases (miss 4 & 5). My luck is real :(

→ Ответить

Infused

8 лет назад, # |

Why is the site still stating that the contest is running?

→ Ответить

saliii

8 лет назад, # |

@xiaowuc1 Is there a better solution than 2D range tree or Sqrt decomposition + fenwick in better order?

→ Ответить

Lewin

8 лет назад, # ^ |

I had a solution using a merge sort tree with fenwick trees in each node. It uses O(n log n) space and takes O(n log^2 n) time. You can see my code here: http://pastebin.com/N1EeqNRS

→ Ответить

saliii

8 лет назад, # ^ |

Oh! cool! Can you explain the idea of the solution!?

→ Ответить

hloya_ygrt

8 лет назад, # ^ |

Same here on C++ :)

→ Ответить

P_Nyagolov

8 лет назад, # |

+89

The problems in platinum division showed a lot of creativity. Like why the hell would someone think that putting 3 DS problems in a single problemset of 3 problems is cool?

→ Ответить

arknave

8 лет назад, # ^ |

← Rev. 2 →

#2 can be solved with nothing more than DP and arrays. I do think it's a bit much to have DS questions for both 1 and 3 though (unless they also have better solutions).

→ Ответить

P_Nyagolov

8 лет назад, # ^ |

← Rev. 3 →

Can you share your code, please? And still, the fact that there is a solution which differs from an obvious one with a tree doesn't make the round less boring. As I can see kliu31415 and percywtc used trees, too :)

UPD: lol why did percywtc appear purple :D

→ Ответить

arknave

8 лет назад, # ^ |

Sure, here's my source:

→ Ответить

8 лет назад, # ^ |

And more is that, the trick I used to solve Problem 1 and Problem 3 are both involving Number of Inversions.

I think the problems each is interesting, but when the authors intend to put series of problems with similar background(cow crossing roads?). Although the solutions themselves are not the same, it is very easy that those problems involves similar tricks or approaches because the background of them limited the range of possible topics.

Still, I appreciate the author brilliant idea of preparing problems with similar background and same title(is it same for Bronze as well?). It is not that easy to come up with a large number of problems that all of them can share same background. The first moment when I realized the names of problems in next division were all same as the previous division, I was just expecting problems with greater constraints, stricter limitations to increase the difficulty of the problems, but it turns out to be in 9 of the problems, only two of them overlaps, which is quite a small number than I expected.

→ Ответить

8 лет назад, # |

← Rev. 2 →

+34

This contest is really memorable to me. As I long time did not participate USACO, my previous division was Silver. As a result, I participated in the Silver contest, and got in-contest promotion to the Gold division, and participated in the Gold contest, and got in-contest promotion again to the Platinum division, and finally, participated in the Platinum contest.

So I decided to share all my solutions and ideas to the contest from Silver division to Platinum division.

As the solutions are quite long, I decide to split the solutions into 3 parts according to their divisions. This can also let us discuss the solutions for different divisions without colliding on the same comment.

Silver Division

Problem 1. Why Did the Cow Cross the Road

By getting maximum number of pair (i, j) such that A_j ≤ T_i ≤ B_j, we can greedily match each j to some i. We can perform this by starting from the chicken with smallest T_i, greedily match this chicken to the cow (that fulfill A_j ≤ T_i ≤ B_j) with the maximum B_j. I used priority_queue as a heap to do so.

Problem 2. Why Did the Cow Cross the Road II

We can just pre-compute the prefix sum so that we can calculate the number of damaged signals with range i..i + K - 1. And thus we can iterate through all possible i to find the answer.

Problem 3. Why Did the Cow Cross the Road III

Before looking for the answer, we can first find the groups of cows that they can visit each other without crossing any road. This can be done by simply DFS, we can go from (x, y) to (x', y') only if there are no roads between them and they are adjacent grids.

At last, we can compute the answer by knowing the fact that the cows in seperated groups are distant with each other. Therefore, if we have M groups in total, and the i - th group consists of G_i cows, the answer is G₂ × G₁ + G₃ × (G₁ + G₂) + G₄ × (G₁ + G₂ + G₃).... We can quickly calculate the answer with the aid of calculating the prefix sum of G_i.

→ Ответить

8 лет назад, # |

← Rev. 3 →

+31

Gold Division

Problem 1. Why Did the Cow Cross the Road

I solved this with Dijkstra(this is my first thought after reading the problem, I am quite sure there are easier solutions). Let us denote dist[x][y][k] as the minimum cost to reach (x, y) such that this is the (k mod 3)-th step from the starting point. We will only add the cost G_i, j if the previous k is 2, otherwise, the additional cost is zero.

Problem 2. Why Did the Cow Cross the Road II

Before talking about the solution to this problem, I have to state that this is the easier version of the Problem 2 in Platinum Division.

Okay, I used 2-dimension DP to solve this problem. Here, we denote dp[i][j] as the maximum number of crosswalks that can be drawn if we just consider the first i cows on one side of the road and the first j cows on the other side of the road.

Then we can use this transition formula to compute the whole dp[][] array: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]),

And when |a[i] - b[j]| ≤ 4, we also have to consider: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1).

So the answer would be dp[n][n]

Problem 3. Why Did the Cow Cross the Road III

We can observe that pair (a, b) is a "crossing" pair if and only if the pattern a, b, a, b appears in the circle. In other words, we can just consider the pattern a, b, a and b, a, b in the input (not a circle but a straight line).

I calculate the number of occurrence of that two patterns with the aid of Mo's algorithm, and the time complexity of the whole solution is $\text{[math]}$ . I think there should be faster solutions?

→ Ответить

nologic

8 лет назад, # ^ |

-8

For gold 3rd I sorted all the segments and then processed then one by one starting from the "shortest" one, then used BIT with the sums, because the smaller intervals have been processed, their value in BIT array will be set to zero

→ Ответить