We will also be posting instructions on how to join the group on our website. Hope to see you all there!

Just like all USACO people are at one with Bessie, you must be at one with William Lin. Only then will you experience the benefits of the club.

Joining the cyan trend!

My explanation on the editorial blog

D can be solved in O(V+E). We do this by first going in increasing order of node index from i...N. In the dfs we query for the node with greatest index that we can visit from a vertex v. This is denoted by f(v). We also color the nodes we visit with i representing their connected component.

Then, we essentially have the interval (i, f(i)). Because we iterate in order of node index, it is guaranteed to be the earliest disjoint interval.

Now, we iterate through all the nodes j in the interval, and if j is not colored the same as i, we add an edge between them. Dfs on j, and extend the right side of the interval to max(f(i), f(j)). We do this because if we have f(j) > f(i), there might be nodes between f(i) and f(j) that must be connected to i.

Once we are done iterating through the interval, it is guaranteed that all nodes to the right are disjoint from all to the left, so we simply set the value of i to f(i) (this makes the next iteration start from f(i)+1).

code

As soon as I saw that the round would be french, I immediately thought of baguettes, berets, and french accordian music. Good luck on the round everyone!

Can confirm: the 2 contests I took immediately after joining were like this:

I attribute all the success to joining the club.

o_o lol

I can tell you my solution (which I personally find more intuitive). I push all cars from the first array in order into a queue. I also have a "visited" array which keeps track of all cars that we have already processed. This gives us that for any 2 cars a and b such that a is in front of b in the queue, a entered the tunnel before b.

Now, we process, the second array in order. For every iteration of i we do the following:

1. While the car at the front of the queue has already been processed (check this using visited array), pop it from the front of the queue.

2. If car at index i (of the second array) does not equal the front of the queue, this means car i should be fined. We know this because the q.front() is guaranteed to have entered the tunnel before car i, and i is leaving the tunnel before q.front(). Thus, we add one to a running count, and mark car i as visited.

3. if the car at index i does equal the front of the queue, pop the element at the front of the queue.

Output the counter at the end.

My code: 62699992

I had the same idea as you as well! Looking at your code, one thing that you might not know is that you don't actually need a multiset of pairs to delete one instance of a number; if you do s.erase(s.find(x)) it will only erase one instance (I believe the first) of x in the multiset.

My code: 62729086

Note: I used %N to eliminate the need for explicitly extending the input array.

Cheers!

In my opinion, http://cp-algorithms.com/ (english version of http://e-maxx.ru/) is the best place to find explanations and implementations for algorithms in C++. In addition, one of the best resources is the problem list on the bottom of almost every algorithms page; I find that if I solve most problems on that list for a given algorithm I become much better at that algorithm. My favorite page is the segment tree page. Through its explanations I gained important intuition on how to code non-standard segment trees which has helped me a lot on contests.

In my opinion the imbalance matters because solving a harder problem differentiates the people who are skilled and not skilled. For example, tmwilliamlin168 is extremely skilled so he always solves more problems than me. tmw OFZ.

Yeah the problem was too wordy so I skipped straight to the example, figured out a weird pattern, coded it up super fast, and watched it get passed pretest with disbelief. I was fully expecting a WA but I got lucky o_o.

Yeah I agree; the one I was thinking of was really nasty to implement (lots of if cases and room for error) so i figured it wasn't worth it given how much time I had left. Watch there be some 5 line mathematical solution lol ;P.

The queue times today were amazing, best I have ever seen. Thanks Codeforces!

https://mirror.codeforces.com/problemset?order=BY_RATING_ASC&tags=shortest+paths%2C1700-3300#

I'm 15 and Im trying to get into div1 :)

Firstly, sort the indices in chronological order. Secondly, we can define dp[i] as the maximum amount of money we can obtain at time a[i]. We can then say that this amount can be represented as the best out of these 2 values:

1. We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N

2. We do use interval i: Define j as the first interval such that s[j] > e[i] (in other words, the first disjoint interval after i). Then, the value would be (the maximum possible money obtained from j..N) + p[i].

In terms of reccurence relation, this would be: dp[i] = max(dp[i+1], dp[j]+p[i])

This gives us an O(N^2) solution, which will definetly TLE. However, we notice that for all intervals i+1..N, there is always an interval j such that intervals i and j are disjoint, and that for all k from i+1..j-1, k and i are not disjoint. Therefore, we can binary search to find the value j. The total complexity therefore becomes O(NlgN)

My code

Hope this helped!

100th upvote :)

I use Xcode because I really enjoy their debugger and because the speed it takes to run programs is minimal.

Cons - does not work on non-mac devices - you need to get xcode 9.1 online from apple developer tools because xcode 10 doese not work - you need to create a new project for every program which makes github hard to use and makes you code take up a lot memory.

Is a geniosity

William Lin has no beginning. William Lin has no end. William Lin is infinite. Millions of years after our civilization has been eradicated and forgotten, William Lin will endure. William Lin is eternal. The pinnacle of evolution and existence. We are but rudimentary creatures of blood and flesh. We touch William Lin' mind, fumbling in ignorance, incapable of understanding. Organic life is nothing but a genetic mutation, an accident. Our lives are measured in years and decades. We wither and die. William Lin is eternal. Before it, we are nothing. William Lin imposes order on the chaos of organic life. We exist because William Lin allows it, and we will end because William Lin demands it. William Lin transcends our very understanding. We cannot grasp the nature of William Lin' existence.

geniosity.

Yeah youre right I think I just misread something — does the problem require better than O(N^2)?

In general, computing a dfs tree of minimum depth in a graph is np-complete. See here. Are there any additional constraints given in the problem that would make the construction of the minimum depth tree optimizable?

Would it be possible to make it available for ios users as well?

Contest on a weekend at 10:30 AM? Am I dreaming?

Comrade Stefdasca share the points that you will atain when you do this round.

vamaddur orz

10:00 on a Saturday morning! California thanks the round setters!

orz

was the contest rated?

My (bad) explanation for problem 2: so we have a vector of deques representing the current stacks of plates we also keep track of the maximum numbered plate that elsie has already washed and stacked when a plate comes to bessie: 1) if this plate has a number less than the maximum plate placed, there is no way that we can place this plate; output the current i 2) binary search for the stack whos bottom plate is as small as possible but greater than the target plate within the range of the 2 pointers (i.e upper_bound) 3) if all the plates in all the stacks are less than the target (this can be checked by looking at the bottom of the last stack), then create a new stack and move the second pointer forward 4) else if the target plate has label less than the top of the stack whos index we found during the binary search, then push the plate to the top of the stack 5) otherwise, move the first pointer to the index that we found with the binary search, and pop off all plates with numbers greater than the target plate (effectively we are getting rid of the plates that should come before the target). update the maximum plate to the tag of the last plate that we popped 6) push the target plate onto that stack 7) continue

https://mirror.codeforces.com/profile/tmwilliamlin168

yay — a contest that california people can take! good luck everyone!