Hi all,

The third contest of the 2019-2020 USACO season will be running from February 21st to February 24th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3673 |

3 | Um_nik | 3493 |

4 | apiadu | 3397 |

5 | 300iq | 3317 |

6 | maroonrk | 3250 |

7 | Benq | 3230 |

8 | LHiC | 3229 |

9 | TLE | 3223 |

10 | ecnerwala | 3216 |

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

1 | antontrygubO_o | 192 |

2 | Errichto | 186 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 168 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 162 |

9 | 300iq | 155 |

10 | Petr | 153 |

Hi all,

The third contest of the 2019-2020 USACO season will be running from February 21st to February 24th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/04/2020 08:50:14 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Excited for USACO as always! Wish everyone good luck :)

Do you have an exact time when we can discuss this contest?

4pm UTC (11am EST) on Tuesday, if I calculated correctly.

Has the contest finiished so that we can discuss the problems?

now it has officially finished as it as already past 4pm UTC

How to solve all problems in platinum?

Solutions

Notes:

What's the answer for N=1 in DELEG (Plat)?

O(knlogn) requires a bit of optimization to pass for HELP (Plat)?

Plat sols:

DELEGBinary search on K. Let dp[u] = max length path coming out of subtree u. Then, we have two cases depending on the parity of the number of children of u.

Odd:

We should choose one path to extend out of u and pair the other paths together. We can do this with multisets or binary search.

Even: We could pair all paths together, or we could have one path end at u, have one path extend out of u, and pair all other paths together. The way to choose the path to extend out of u is similar to the odd case.

Code: https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Deleg.cpp

TRIANGLESWLOG, x1<x2<x3, y1<y3<y2. We can prove that there is a center (xc, yc) such that x2=xc, y2=yc+k, x3=xc+k, y3=yc, x1=xc-a, y1=yc-b, a+b=k, for some k. We just iterate over all xc, yc, and k. We can find the number of (x1, y1) with diagonal prefix sums. Code: https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Triangles.cpp

HELPThere are two ways to do this: 1. Maintain the sum for each power in a DP. 2. Count the number of k-tuples of rightmost segments of connected components. This can be done by finding the number of i-tuples with increasing indexes using DP, then using some combinatorics to find the number of k-tuples.

Both DP solutions are optimized with segment trees.

Code (solution 2): https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Help.cpp

Trash 2:28 AK Screencast

'Trash'

The video is private I think

I think that a lot of people AKed much faster than I did, for example you can look at 300iq's screencast where he AKs in 1:23

Totally unrelated question

What is AK?

AK is when someone solves all of the problems

AK = All Kill?

Ohh thanks

Can you also share link to 300iq's Screencast?

I have no idea where it is, he only mentioned it to me :/

All Killed exactly

"What's the answer for N=1 in DELEG (Plat)?"

Clearly it should be INT_MAX :D

`unbovine behaviour`

For DELEG: For the root, you can simply ignore the circumstance of dp[root] = 0 if you pick a leave as root.

How to solve problem HELP(gold)?

Answer = ∑ ( 2^(n-1-the number of the segments which cover l[i] ) )

Use segment tree you can pass in O(nlogn).

But I don't how to solve HELP in Plat with this Idea.

Use expected values and then sweepline to pass all test cases, so no need to do segment tree.

I think problem P1 is particularly similar to China's NOIP2018 D1T3.

Will 710.4 be enough to pass gold?

Im guessing cutoff is not going to be like 750+, since 2 of the problems were kind of hard. But honestly, it seems like contestants are getting smarter nowadays so it is quite difficult to predict.

I think this month's cutoff was similar to last month's difficulty so I'm crossing my fingers that cutoff will be the same.

By the way, how many days does it usually take for the results to come out?

When will USACO be releasing results?

I think it would be around 5 days from now. Last month was 10 (maybe? I don't remember exactly) days after the contest, anyways.

Results are out!

800?... T_T