The first USACO contest of the 2016-2017 season is going to run from 12/16 (Friday) to 12/19 (Monday). Let's discuss the contest and the problems here after the contest :)

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

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

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

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | PikMike | 166 |

5 | Vovuh | 166 |

7 | rng_58 | 158 |

8 | majk | 156 |

9 | farmersrice | 153 |

9 | Um_nik | 153 |

The first USACO contest of the 2016-2017 season is going to run from 12/16 (Friday) to 12/19 (Monday). Let's discuss the contest and the problems here after the contest :)

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2019 04:00:38 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I guess Mexicans aren't allowed to participate.

The firewall hasn't been built yet.

Trump: "I will build a firewall and make China pay for it".

Later...

USA team got 1 bronze medal and 3 honorable mentions at the IOI (and China didn't pay for the firewall).

Problems in English only? or ? :)

There already problems in en, ru, fr.

can anyone explain for me why the input of problem 3 — silver is 3 :(( .The 4th cow can't be reached so i think the answer is 2 @@@

deleted. I think that my comment doesn't give any hint to this problem. Anyway, excuse me)

Please do not discuss problem specifics DURING the contest >.<

Can i ask for a clarification in Silver Contest Problem 3 Mooncast?

How to solve the first Platinum Division problem? (Lots of triangles)

My solution: Angular sort, radial sweep, range query.

Complexity: O(n

^{3}log(n)).Is there O(n

^{3}) solution or better exists?And my solution TLEd -_- (I used angular sort + count number of inversions). However, I heard from minimario that an

O(n^{3}) solution exists.My

O(N^{4}/ 64) with bitsets fit in the time limit.I went from only 3 tests to full score by just removing constant factors from my complexity :D :D

I don't really mind the downvotes but just in case someone thinks I was lying: O(N^3logN)$ — 3/10, O(N^3logN) — 10/10.

The problem is technically a subproblem from codechef problem CHEFPOLY.

To solve in

O(n^{3}), do inclusion exclusion. Choose any point that is at extreme bottom left, now, for allO(n^{2}) triangles made by this point, check points lying inside inO(n). Note how all original triangles can be defined as some addition of two of these triangles and subtraction of one. Now you can process each triangle inO(1). Also the bitset solution is described here.O(300^{4}/ 6) solution is kinda obvious. you can optimize it toO(300^{4}/ (6 * 64)) by using a bitset. which is better thanO(300^{3}) .code: https://hastebin.com/cuduvepuqu.cpp

UPD: sorry, dogewizard420blazeit answered that before me

Yes.

In contest, I didn't realized such exists, and coded n^3lgn solutions. (angular sort + bit) I got TLE, so I precomputed angular sort for n^2lgn, and get AC. (I know this is dirty :D)

You can pick a point say the point leftmost of all points (point P) and fill a pre_process array dp[i][j] that means in the triangle with vertices P,i,j how many dots are there we can fill this array naively O(n^3) and then for any triple (a,b,c) we can easily find out the number of dots inside it O(1) for example the number of dots inside(a,b,c) can be equal to : dp[a][c] — dp[a][b] — dp[b][c] — 1 OR dp[a][b] + dp[b][c] — dp[a][b] (if b is between a,c if we look at it from P) so the overall complexity will be O(n^3)

(filling up the array and finding out which point is in between to other points by looking at it from P can be easily implemented by cross product)

Code here: http://paste.ubuntu.com/23662295/

Let's use trapezoidal decomposition. Loop through all segments and compute the number of points inside the trapezoid formed with the x-axis. Now, for any query triangle, lets pick the longest segment forming it and look at the third point not forming this segment. Depending on which side of the segment this third point is, we either add 2 trapezoids and subtract 1, or subtract 2 trapezoids and add 1. Either way, it's

O(n^{3}).How do you solve gold 2 and gold 3?

You can solve third problem by bfs. Here is the code.

Can you describe your algorithm with words?

I just did coordinate compression for P3 Gold, then did normal BFS with a global visited array. It passed all tests

gold 2 ==> DP[1000][1000][2]

wtf of down?! :/

About problem 2 gold :

I decide to go to through the all options and get the best answer.

Situation (x, y, k) :

. k = 1 — Holsteins cow, 2 — Guernseys cow.

. the last Holsteins cow was Holstein cow by number x,

. the last Guernseys cow was Guernsey cow by number y,

and we now near cow type k.

The ansewr for situation (x, y, k) it's minimum energy which we need fo going from (x, y, k) to (h, g, 1)

Let calculate answer for situation (x, y, k) and we want go to the (h, g, 1)

So where we can go from there ?

1) if x == h and y == g

. a) k == 1 then nowhere ( ans = 0 )

. b) k == 2 then go to the h-th Holsteins cow.

2) if k == 1

. a) we can go to ( x + 1, y, 1)

. b) if y < g we also can go to ( x, y + 1, 2 )

3) if k == 2

. a) we can go to ( x + 1, y, 1 )

. b) if y < g we also can go to ( x, y + 1, 2 )

One point : if we walked out from [1; n][1; m] then the answer will be BIG NUMBER.

So we will calculate the answer for (1, 0, 1), and it will be the answer for the problem.

First I just write recursion "go through the all options" ( and got 2/10 AC)

Then I saw that some positions (x, y, k) we calculated several times, and decided to use map for optimization ( we calculated answer for each position one time and save the answer, and each another time we will use saved answer ). ( it got 5/10 AC ).

And I decided to change map to the array because the problem has no big limitations [1000][1000][2]

( it got 8/10 AC ).

This problem helped me to understand how to convert some DFS solutions in to the BFS solutions, and I convert my DFS solution in to the BFS solution and got 10/10 AC.

I think this problem was very interesting and useful for me.

If you are interesting here is my DFS and BFS solutions.

Thank you for attention. And sorry for my bad English.

Please if it was useful put "+" here.

Please if it wasn't useful put "-" here.

Any hints for problem C in platinum division?

From what I have heard, the problem is a harder version of Problem A in this competition: http://cs.stanford.edu/group/acm/slpclive/problems/problems_2016.pdf

I've also heard that one can use Eppstein's algorithm to solve it.

My solution is O(nlg^2n). I will only explain some key ideas, since the full algorithm is hard to explain....

In contest, I was short of time, and I just submitted optimized O(nlg^3n). This misses two TC as TLE. (956/1000) This is my code. http://ideone.com/s08eao

Also, ainta told me that there is nlgn solution. I think it won't be really hard to optimize mine to nlgn...

Oops, sorry :(

Link to my solution of C (it got AC). It's an easy to understand DPlike bruteforce which runs in .

Can you explain the code?

So let's begin with some facts.

1) We can binary search on the maximum number we will get.

2) If we sort the numbers in each row, we must get at least the minimum number in each row. So we subtract from each number the minimum in its row. We do this so that we can ensure that our transitions in the following DP will be

O(K).3) How to do the check in the binary search? If we do a DP[add_sum] = number of ways to increase the minimum sum with add_sum, then we can notice that in each transition of the DP our count of numbers increases with at least 1. So we can maintain a global counter of all possible sums less than the current minimum that leads us to at most

O(K) DP transitions (if our global counter reachesKwe just return true). The complexity of the check is because of the map, but it can be improved using a hash table.4) after we find the maximal number the sum can be found in a similar manner.

My solution is

`O(n log n)`

and it's really simple to code:Let's sort pairs

`(value, row)`

for all elements in all rows (except for the smallest ones), where`value`

is the differences between the element and the smallest element in its row.Let's say that a state is a vector of positions (in the sorted array) and run Dijkstra's algorithm (starting from an empty vector). We need only two transitions: creating a new position immediately after the last one and increasing the last position by one.

There's one problem here: we can take two elements from the same row. It's bad. Let's fix it by moving the last element until all rows are unique (we touch only the last element, so it's the only one that could break). That's it.

You know, people can compete in this competition until 4h after the official finishing time. I have 30 min left and I'm seeing a lot of spoilers.

How long do results take to publish? Will it be out by tomorrow?

This is pathetic. Officially, anyone can start USACO contest at Dec 19, 23:59 UTC time and start for 4 hours. You guys are discussing problems just

after the time for the official start of the contest is overinstead of four hours after it__. Even I started the contest 2 minutes before it officially ended and although I did not use any outside help, I came here after the contest to be the first guy to talk about it. Now, I am disgusted to see that three hours before the contest ended for me, some other people had already started discussing stuff. This is pathetic.P.S. Feels fun to get promoted to platinum!

And the people discussing it early are probably the ones downvoting you.

Results are available here!

My solution for problem C was as follows:

First, notice that the approach with the priority queue has two problems: it is

O(NK) and it generate duplicates. In order to solve both of these problems, notice that once we have an element in the queue (I.e., an array of indices for each of theNcomponents), we have two options: Either we take the next best possible difference (let's call the corresponding positionpos), or we completely stop adding differences frompos. You can see that, by doing that, the decision splits the solution space into two disjoint parts.The minimum, as well as all the operations, can be simulated in

O(log(n)) with persistent segment trees. Hencr, total complexity isO((N+K)log(N+K)) Here is the code:http://pastebin.com/xHn88B3d

Note: I did not notice that the cases were disjoint in contest-time, that's why I also have hashes comparison. They are useless in the code.

Can you please explain your method with more details ? Thanks in Advance.

For Platinum P3 "Robotic Cow Herd", shouldn't the worst case complexity of the (official solution) which is a brute force, be more ? Shouldn't the enumeration run in O(M1*M2...Mn) in the worst case ?