USACO 2016-2017 US OPEN

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

← Rev. 3 →

I think the contest will held in usaco.org according to clist.by

UPD: Yes, I was true.

→ Ответить

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

The contests is running.

→ Ответить

GiraffeCoder

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

+26

The input/output file name of problem Switch Grass in Platinum division is incorrect. It should be "grass.in/.out".

→ Ответить

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

← Rev. 2 →

-73

Is the second test case of problem 1 pelatinum correct?!

UPD: it's correct

→ Ответить

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

+28

The contest isn't over yet.

→ Ответить

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

-13

Common...!!!

One test of the first problem which mey be wrong!!!

→ Ответить

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

I doubt that their test cases are wrong, but if they are, you should just email them.

→ Ответить

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

What's the Email?

→ Ответить

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

[email protected]

→ Ответить

jasonvictoryan

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

I had the same wrong test,which is test 2.I think there is something we do not considered.

→ Ответить

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

+21

I think the test case is correct. I know people that have gotten it.

→ Ответить

szawinis

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

It's definitely correct. My AC solution passed it.

→ Ответить

PriyankaChopra

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

So hard contest... How to solve SWITCH GRASS from platinum?

→ Ответить

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

← Rev. 2 →

I think there is still 1 hour in the contest. Edit: When I started the contest, I checked the latest time you could start the contest, and it was four hours ago.

→ Ответить

PriyankaChopra

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

clist

→ Ответить

Benq

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

Unlike last time, this contest was 5 hours instead of 4 (clist didn't take this into account).

→ Ответить

AnonymousBunny

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

Didn't get it in contest but I think this should work: sort the edges in increasing order of their weights and suppose at some point of time edge u-v is the lightest active edge. This means that for all edges which are lighter than this edge, the id's of their vertices are equal. Now the key observation is that in most of the cases this implies the id's of u and v are equal too. So you only need to consider the "important" edges- i.e. add the edges one by one in increasing order of weight, and reject edge u-v if u and v are already in the same connected component. Notice that is basically Kruskal's algorithm for finding a minimum spanning tree, so it suffices to solve the problem on a tree. This should be easy by keeping a bunch of multisets for each node.

→ Ответить

satyaki3794

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

Can you please explain how you will solve the problem for a tree using multisets?

→ Ответить

AnonymousBunny

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

← Rev. 5 →

Here's my implementation (gets AC): code. For each vertex I maintain a map of multisets which store for each color the list of its children with that color and an additional multiset which stores the weights of the optimal children of each color. Details should be clear from the code.

→ Ответить

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

You can still start the contest on the website, so discussion should probably not happen yet.

→ Ответить

radoslav11

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

How to solve Platinum 2?

I wrote an $\text{[math]}$ solution which passed just 3 test (the same as the stupid one with checking the all adjacent vertices). The basic idea is to divide the updates in sqrtM equal parts .Did someone do that and if so

→ Ответить

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

+13

Notice that in any cycle of the graph, if there are at least two types of grass, then there are at least two edges that connect different types of grass. Therefore, the largest edge in any cycle will never be used as the answer, so it can be removed. This is equivalent to reducing the graph to its minimum spanning tree. The rest is just lazy propagation to update the children of the node changed in each update.

→ Ответить

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

+15

How does the lazy propagation work?

→ Ответить

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

+10

Let each node store the distance to its parent. Order these values such that for each node, all its children (and only its children) exist as a subarray, and that all children with the same grass type are also consecutive. Build a segment tree on this array. Now when we update node I from A to B, we make invalid all its children with type B (add infinity to all these nodes), and similarly make valid all children with type A (subtract infinity from these nodes). This is a range update, so we use lazy propagation. We should change the validity of node I as well, depending on the grass type of its parent. To get the answer, just query for the minimum value in the entire range. There are some annoying details to take care of, such as how changing the grass types of the nodes changes their ordering, but it can be done.

→ Ответить

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

← Rev. 2 →

I also saw this in-contest, but couldn't figure out how to change the ordering of the children if one of their grass types changed. Can you elaborate on this section?

→ Ответить

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

Simply leave extra spaces in the array to move nodes around. Before building the array, read the queries and calculate where the extra spaces are needed.

→ Ответить

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

Cool! thanks :)

→ Ответить

downvoteplz

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

← Rev. 2 →

Are you sure about your complexity? My $\text{[math]}$ (~ 10^9 operations) passed 7 cases out of 10.

→ Ответить

radoslav11

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

Oh actually its something like $\text{[math]}$ but I still don't think it should have TLEd on everything. Probably it TLEd because of a big constant. Thanks for the response. At least now I know that I probably got the idea for the solution.

→ Ответить

DBradac

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

It can actually be solved in $\text{[math]}$ , but the solution has many little complications to avoid the log factor. One of the cooler things I to avoid using set is buckets to create a structure which provides insertion and deletion of elements in O(1) and minimum query in $\text{[math]}$ which is fine since you have only Q queries for minimum. However, I haven't submitted it, does anyone know when will the problems be available for upsolving?

→ Ответить

rajat1603

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

+62

→ Ответить

send_nodes

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

It's actually one of the most beautiful problems I've seen :D

→ Ответить

ko_osaga

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

+56

That's weird. I think you should solve more beautiful problems.

→ Ответить

FieryPhoenix

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

← Rev. 2 →

-14

How do you solve it?

→ Ответить

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

I agree lol. Did you solve it in contest? How did you do on the other problems?

→ Ответить

bad matrix multiplication

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

So how do you solve it?

→ Ответить

Benq

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

→ Ответить

ko_osaga

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

← Rev. 2 →

+20

Anyone have something faster than O(100 ^ 4 * lg(100000)) in platinum P3? Such solution should pass (as it's hard to make constant factor large. I think it will go down as low as /16 ~ /50) but I wonder if there is any solution with better asymptotics.

→ Ответить

pacu

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

My guess (which could be completely wrong) was that there is no faster solution aside from improvements in matrix multiplication. This problem seems to be equivalent, in some sense, to multiplying and exponentiating matrices.

→ Ответить

-is-this-fft-

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

← Rev. 2 →

Technically you can go down to something like $\text{[math]}$ because matrix multiplication can be optimized.

→ Ответить