Hi all,

The third contest of the 2016-2017 USACO season will be open from February 10th to February 13th. This will be our last contest before the US Open. Feel free to discuss the problems here after the contest is over!

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

1 | Petr | 3325 |

2 | OO0OOO00O0OOO0O0…O | 3289 |

3 | Um_nik | 3278 |

4 | Syloviaely | 3274 |

5 | tourist | 3206 |

6 | Radewoosh | 3197 |

7 | V--o_o--V | 3167 |

8 | mnbvmar | 3096 |

9 | dotorya | 3086 |

10 | FizzyDavid | 3023 |

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

1 | tourist | 183 |

2 | rng_58 | 168 |

3 | csacademy | 161 |

4 | Petr | 160 |

5 | lewin | 151 |

6 | Swistakk | 150 |

7 | matthew99 | 142 |

8 | BledDest | 141 |

9 | Errichto | 140 |

10 | adamant | 139 |

Hi all,

The third contest of the 2016-2017 USACO season will be open from February 10th to February 13th. This will be our last contest before the US Open. Feel free to discuss the problems here after the contest is over!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2018 06:43:30 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Is the contest over? Anyone minds to share any problem's solution for silver division?

It's not over.

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.

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

`int`

s of sizeNand initialize everything to zero. Set all broken ones to 1. Select theklength 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^{2}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 theKcow 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

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.

I did the same thing that you did for #1, but i sorted the intervals by ending time. Code: (it's in java) http://pastebin.com/CvzvfXR6

What were the problems for silver?

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

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

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

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

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

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

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

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

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

Hints for Platinum division:

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 :( ).

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.

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

I used almost the same code, but it failed 5 cases. Was it because I was declaring the new nodes on the spot?

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

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

One testcase wrong oops.

Passed with

O(n^{2}) on #2 somehow!For 3rd I wrote a 2D BIT on a smart hashmap. http://pastebin.com/DPemaJeW

It is

O(n·log^{2}n) time and memory, and I was actually a bit surprised it passed within a second.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 cowsb_{i}. Now, letp_{i}=a_{bi}. Our goal is to count the number of pairsi<jsuch thatp_{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 and . Let's sort all the indices fromltorbybvalue, 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.Did anyone else get time limit exceeded for platinum question 3 using an

O(nlog^{2}(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.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.

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.

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 ?

For each lower level tree, we can calculate the update values in N log N time. Then we can sort them and binary search before each update/query. (I am talking about the 2D range tree/BIT solution)

My solution is simply 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!

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^{2}(n)) solution. If it is the intended complexity, then it seems a bit tight.Me using segment tree with AVL tree and only passed 7 cases, I thought O(N log N) is need :'(

What's a range tree?

My 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 update and

O(1) query. UPD: It's actually 1470ms on max test,sorry.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 :(

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

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

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

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

Same here on C++ :)

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?

#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).

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

Sure, here's my source:

http://pastebin.com/vR1hgnTJ

And more is that, the trick I used to solve

Problem 1andProblem 3are 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.

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 DivisionProblem 1. Why Did the Cow Cross the RoadBy getting maximum number of pair (

i,j) such thatA_{j}≤T_{i}≤B_{j}, we can greedily match eachjto somei. We can perform this by starting from the chicken with smallestT_{i}, greedily match this chicken to the cow (that fulfillA_{j}≤T_{i}≤B_{j}) with the maximumB_{j}. I used`priority_queue`

as a heap to do so.Problem 2. Why Did the Cow Cross the Road IIWe 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 possibleito find the answer.Problem 3. Why Did the Cow Cross the Road IIIBefore 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

Mgroups in total, and thei-thgroup consists ofG_{i}cows, the answer isG_{2}×G_{1}+G_{3}× (G_{1}+G_{2}) +G_{4}× (G_{1}+G_{2}+G_{3}).... We can quickly calculate the answer with the aid of calculating the prefix sum ofG_{i}.Gold DivisionProblem 1. Why Did the Cow Cross the RoadI 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 (kmod3)-th step from the starting point. We will only add the costG_{i, j}if the previouskis 2, otherwise, the additional cost is zero.Problem 2. Why Did the Cow Cross the Road IIBefore talking about the solution to this problem, I have to state that this is the easier version of the

Problem 2inPlatinum 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 firsticows on one side of the road and the firstjcows 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 IIIWe can observe that pair (

a,b) is a "crossing" pair if and only if the patterna,b,a,bappears in the circle. In other words, we can just consider the patterna,b,aandb,a,bin 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 . I think there should be faster solutions?

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

Platinum DivisionProblem 1. Why Did the Cow Cross the RoadWe can transform the problem into counting the number of inversions on one side if we keep shifting the sequence on the other side. For instance, the sample can be transformed into considering the second sequence as 3, 4, 5, 1, 2 (if we decide to shift the second sequence).

We can maintain the number of smaller elements that came after the element

ifor eachiwith Segment Tree. For simplicity, we denote this number ascount_{i}. The number of inversion of the permutation will be the sum ofcount_{i}. And each time we move the first elementkto the back, the valuecount_{k}becomes 0, and allcount_{i}withi>kwill increase 1. Maintaining the values ofcount_{i}with Segment Tree, we can easily update and calculate the number of inversions withO(logN)Problem 2. Why Did the Cow Cross the Road IIAs I mentioned above, this problem is an harder version of

Problem 2inGold Division. I just improve my solution toO(NlogN) instead ofO(N^{2}).We can observe that for every

abs(a_{i}-b_{j}) ≤ 4,dp[i][j] is the maixmum of alldp[x][y] withx<iandi<j. Therefore, by iteratingi, we can reduce thedp[][] array to one-dimension,dp[], wheredp[j] denotes the number of crosswalks for just the firstiand firstjelements on two sides withabs(a_{i}-b_{j}) ≤ 4. We can maintain thisdp[] with Segment Tree. For everyi, we should pre-compute all the valuesjsuch thatabs(a_{i}-b_{j}) ≤ 4. Then, when we iterateifrom 1 ton, we can updatedp[j] as the maximum value amongdp[1..(j- 1)] plus one.Problem 3. Why Did the Cow Cross the Road IIIBy renumbering the input so that the first

nnumbersA_{1..n}are 1, 2, ..,n. We can just consider the second set ofnnumbersB_{1..n}, and thus simplify the problem as calculating the number of pairs (i,j) such thatB_{i}>B_{j}andA[B_{i}] -A[B_{j}] >K.Recalling that during the process of merge sort, we can calculate the number of inversions as well. Here I used this trick and handle the rule

A_{i}-A_{j}>Kas well. Every time we merge the two sorted sequences, let's saySandT, we can maintain a Segment Tree which can help us that for each elementS_{i}, after finding the maximumjsuch thatS_{i}>T_{j}, we can calculate the number of elements inT_{1..j}thatA[T_{x}] +K<A[S_{i}] orA[T_{x}] -K>A[S_{i}]. So, every time we increasej, we can update the ranges 1..(A[T_{j}] -K- 1) and (A[T_{j}] +K+ 1)..N.Thus, the time complexity of my whole solution should be

ConclusionsActually this is my first time sharing solutions of many tasks of one contest, and also as I participate quite early in the 4 days window, my memory to the problems are not very fresh. I apologize for any mistakes or stupid things I have made in this text.

I would be appreciated if you could share your thoughts to my solutions as well :D

Last but not least, the only problem I can't solve during the whole contest (may someone help me?) — Why did the cow cross the road?

So why exactly did the cow cross the road?

We may never know the full reason, but it is certain that Farmer John's cows do end up crossing the road quite frequently:DTo get to the udder side...

If I am looking at my results, they will die before they get to the other side. :D

for the same reason Why_did_the_chicken_cross_the_road

Results are out: http://usaco.org/index.php?page=feb17results