Hi all,
The third contest of the 2021-2022 USACO season will be running from February 25th to February 28th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Hope the problems are fun!
Hope the bugaboos are fun!
ah yes, we can't forget the bugaboos. Hopefully, Brian Dean will have pity on Silvers lol.
How did it go? ;)
very badly
such foreshadow ＜(。_。)＞
Wish everyone luck!
lets hope for no triple-qi combos
is it open to everyone? if yes , how can i participate?
Let's hope for 3 data structure problems in plat by xiaowuc1
Do you genuinely want to solve 3 data structure problems? I don't have issues solving them in ICPC competitions (for me it's most of the times applying standard techniques), but I like to participate in IOI-style because having only 3 problems allows to make them harder not only in terms of implementation, but most importantly in terms of ideas.
That's why I want to solve data structure problems
You still have at least 28 ruby data structures problems to do. Get back to work.
What are 'ruby' data structure problems? Are you talking about the programming language Ruby?
It's the problem level of a famous online judge in Korea. https://boj.kr
Ruby tier is the hardest.
i doesn't participate previous contest. can i participate in this contest ? if yes, then how ? cause i doesn't find any link which redirect me to February contest. i'm little bit confused. pls anyone help to understand how it works. thanks in advance
Finding the contest is the first test.
Jokes aside, literally the first thing you see on the USACO website is the announcement for the February contest, and there is a sentence saying "For more details, please visit the contest page here." All you have to do is to click on the word "here" and you get redirected to a page, where if the contest period has started, you can start your 4 hour block there, but at the moment, we have to wait another 2 hours and 30 minutes.
[user:Bungmint]thank you very much for detailed explanation. i check this 1 hour before writing this comment, and in this moment nothing about february contest not posted. but know i saw it. and i'm very glad really)) I have been trying to participate in this competition for a long time, but because of the huge amount of work I do not have time. I think this time I managed to do it
.
Please wait until the contest is over for everyone before discussing anything contest-related including but not limited to your scores or anything about the problems.
I am in the Gold Division, so I have not and cannot look at Silver Division problems. Besides, discussion about them is not allowed until after the window ends.
To answer your generic question, USACO Silver problems likely correspond to the 1200-1700 interval. It varies a lot by contest, but certainly silver questions' difficulties do not exceed 1700, nor drop below 1200, barring irregular circumstances.
Keep in mind that the premise of your question is somewhat flawed. USACO contests have only 3 problems and 4 hours whereas Codeforces contests have $$$\ge$$$ 5 problems and last $$$2$$$ to $$$3$$$ hours. With USACO, you devote your exclusive attention to a relativity small subset of problems for much more time. Hence, someone with a CF rating of 1500, may be able to regularly solve 1700-equivalent problems in USACO, due to the increase in time limit and lack of pressure.
Also, USACO and CF problems are fundamentally different in nature. USACO problems are frequently fairly implementation heavy, whereas CF problems require you to think for more time and type less.
(disclaimer: haven't taken this month's contest, speaking from recent history)
Silver has been unreasonably buffed as of late. It's expected nowadays for a silver contest to have at least 1 problem above the 1700 rating range, and even 2 half of the time.
For reference, the silver problems last month would be around 1800, 1400, and 2200 rated by my eye estimate. The hardest problem had a lot of weak testcases that fell to different heuristics, and you essentially needed to either solve it or get really lucky with which "cheese" approach you used to promote.
USACO problems have gotten more CF-like as of late too. (more math heavy etc.)
I didn't look at recent USACO Silver problems, from the last two contests. I was basing it off of problems from 2020 and before, which I recognize is probably not the best idea.
I looked at the most recent 3 problems. I would hesitate to agree with your assessment. I think the last problem was probably around 1900 or 2000, which is much higher than my upper bound of 1700. Definitely much harder than in the past, but not 2200.
I think that this website has a solid indicator for the ratings of the past Silver problems: https://codetiger.me/project/usaco/ although some ratings are a bit inconsistent due to the lack of voters on some problems.
There definitely have been Silver problems that could be considered over the rating of 1700 including Meetings and Cow Steeplechase II.
Yes, you are right — in hindsight, I was largely basing my data on the four USACO Silver contests I had partaken in, which happened to be easier than usual.
There are many problems that are over 1700 rating, including one 2200 problem.
Thanks for the correction!
What is test 5 on Platinum Problem 2. Sleeping in Class? I had an $$$O(NX + QD/X)$$$ solution where $$$D$$$ = number of divisors of the sum of $$$a_i$$$. (I split the prime divisors into two parts)
Was the intended solution $$$O((N + Q)K + 2^K*D)$$$ where $$$D$$$ is the number of divisors of sum and $$$K$$$ is the number of distinct primes dividing the sum?
My solution is $$$O(NK+DK+Q)$$$（Perhaps $$$O(NK+DK+Q\log D)$$$ if you use map). Let $$$s_i$$$ denote the prefix sum of $$$a$$$, then for a query $$$x$$$, we need to find the number of $$$i$$$ that satisfies $$$x|s_i$$$, which is equivalent to for any prime divisor $$$k$$$, we have $$$f(s_i,k)\ge f(x,k)$$$, where $$$f(a,b)$$$ denotes the maximum $$$q$$$ such that $$$b^q|a$$$. Besides, $$$x$$$ has to be a divisor of $$$s_n$$$ to make the answer non-zero, which means we can only consider all primes divisible by $$$s_n$$$. By doing prework we can find the answer to all divisors of $$$s_n$$$ using the similar techinique as in arc136d in $$$O(DK)$$$ time.
How to do the problem 2 from Silver Division. I tried using Meet in the Middle. But it did not work on any of the later testcases where N<=40.
It works. I solved this problem using Meet in the middle + two pointers.
If the sections with the same values on both sides are very long in succession, the two pointers seem to be timed out. How did you solve this problem?
No it doesn't affect. All the index pairs you traverse will also just be the sum of the number coordinates you can get in the first half plus the second half. I am bad at English so if you don't understand you can see my implementation : https://ideone.com/c2Qwta. My solution pass < 1500ms
tried meet in the middle + binary search but tle'd for bigger tests lol. Lesson: Use two ptrs when possible
My $$$O(2^{\frac{n}{2}} \cdot n^2)$$$ solution with binary search gets AC safely below the time limit (< 2s). Though I only perform binary search $$$O(2^{\frac{n}{2}})$$$ times, so that may be the reason.
My code.
Platinum problem 1 resembles JOI Final 2014 Problem 5 :o
How to do the problem 1 from Gold Division.
I got 9 test cases :(
Each cow will recive exacly 1 gift and give exacly 1 gift, the In-degree and Out-degree of each vertex is 1 and the final graph will be several cycles.
Let's dp(i,mask) = we are in vertex i, mask is the bitmask of the vertices unvisited + the begin of the current cycle and the least significant bit of mask is the begin of the current cycle (let's call this lsb). This is important to save complexity (we don't have to save the begin of the cycle as a state). The transitions are:
For each j, if bit j is active in the mask, j can recive the gift i and j != lsb : dp(i,mask)+= dp(j,mask-(1<<j))
If lsb can recive the gift i, we can finish the cycle and continue with the new mask and the new lsb : dp(j,mask)+= dp(lsb of (mask-(1<<lsb)), mask-(1<<lsb))
To answer the queries, let's consider mask1 = bitmask of H and mask2 = bitmask of G, the answer is dp(lsb of mask1,mask1)*dp(lsb of mask2,mask2).
Here is my code
Sorry for my bad english.
Let us create an oriented graph such that there is an edge $$$(i -> j)$$$ iff for person i it would be preferred to attribute to $$$i$$$ value $$$j$$$ (i.e. $$$j = i$$$ or $$$j$$$ appears before $$$i$$$ in the $$$i$$$ th cows preferences). Then, any good rearrangement would be described by a set of hamiltonian cycles in this graph such that the sets formed by the vertices in each cycle are all disjoint and their reunion forms the set $$${1, 2, .., N}$$$.
Assume we have calculated all ways to put all elements from some mask in a single hamiltonian cycle. To calculate how many total rearrangements in a submask $$$msk$$$ exist, or $$$dp[msk]$$$, let us first fix some (and only one) bit $$$b$$$ that is found in $$$msk$$$. Then, take all submasks of $$$msk$$$ containing $$$b$$$. Let one of them at some step be $$$sbmsk$$$ (with $$$b$$$ $$$\in$$$ $$$sbmsk$$$). If you would know how many ways you can permute $$$sbmsk$$$ in a single cycle, and if we know in how many ways we can permute however $$$msk / sbmsk$$$ (i.e. $$$dp[..]$$$), then multiplying these two numbers forms a candidate value for dp[msk]. Adding all of these up concludes our calculation of $$$dp[msk]$$$
At a query, we separate G-cows and H-cows. Then the answer is $$$dp[G-mask] * dp[H-mask]$$$.
Time complexity: $$$O(3^n)$$$
Let us fix the first element of the cycle. One may observe that if we have a cycle $$$a_1, a_2, a_3, .. , a_k$$$, then any circular permutation of this cycle would normally also be counted.
Assume $$$start$$$, the first element of the cycle is also the smallest. Now to calculate how many cycles there are, let us fix a mask $$$msk$$$ denoting how many elements we have selected so far in our chain, along with $$$last$$$, the last element in the cycles we are counting. Let us also denote $$$chain[msk][last]$$$ the sought number (I recall you, this is the number of chains using elements in $$$msk$$$ ending in $$$last$$$).
Now, if $$$last$$$ has an edge towards $$$start$$$, then the number of cycles with $$$msk$$$ contains $$$chain[msk][last]$$$. To calculate $$$chain[msk][last]$$$, we fix the element that we consider before last in this candidate chain ($$$from$$$) (and also appears in $$$msk$$$). If this node has an edge towards $$$last$$$, add $$$chain[msk / last][from]$$$ to our calculations. Otherwise, skip.
Time complexity: $$$~O(2^n * n^2)$$$
I got 500 on gold division. 0% chance of promotion, right?
Based on the past gold cuts prolly lol. Like the lowest cutoff was something like 600 in 2020
Just my thoughts, but it really feels like Silver and Gold were sorted in descending order of difficulty. Also while the ideas in silver were more standard, they were all or nothing and you could easily get stuck on constant factor optimization in P1 and P2.
In silver:
P1 — Got $$$(2n)^3$$$ edges construction, then wasted 30+ mins thinking of $$$O(n ^ 2)$$$ / $$$O(n ^ 2 \log n)$$$ before getting $$$n^3$$$ edges idea.
P2 — Obviously meet in the middle. Spent 1 hour on constant factor optimization due to poor implementation skills though T_T.
P3 — Main condition about advancing folders is obvious, after that its just fairly simple implementation.
In gold:
P1 — Got $$$O(3^n \cdot n)$$$ fairly quickly, then bricked on a $$$O(2^n \cdot n^2)$$$ for rest of contest due to overcounting.
P2 — Cool problem, intended answer became clear after coding the subtask.
P3 — Guessed the answer as soon as I read $$$0 \leq y \leq 10$$$, it feels much easier than P1 or P2. Though I'm probably biased since a subtask of a problem I set used the same trick, except on Manhattan distance. Still, it was definitely cool to realize why the trick extends to Euclidian distance as well, I had never thought about it before.
How did you manage to do problems from both divisions — did you in-contest promote from silver to gold?
Yeah, the previous contest was my first USACO contest. After solving bronze fairly quickly, I underestimated silver and started it even though I only had around 1.5 hours free. Bricked and left after not getting a single full solve in 1 hour so obviously did not promote.
This time silver started out similar (no full solve for 1.5+ hours), but managed to full solve it and promote after around 3 hours.
where can i find editorial?
U gotta wait til the results come out. Then the editorial should be on the contest page just as any other USACO contests.
My sol. for P1 Bronze div. I got the full score in it also it should give TLE for the case of n = 1e5 and all the elements in the array are zeroes (if it exists) My sol. for P2 I really liked this problem , the main observation is that when we move a cow from the right to the left the position of all cows with positions less than that of the currently moved cow increases by one so we can use ordered set to count the number of cows with higher positions than the current one that has been moved to the left efficiently My sol. for P3 it's a basic backtracking problem we can just generate all the strings that can be made and store them in a map
Will the Chinese translation be out soon? (Or will it be out?) Some Chinese OJ is waiting for them
Interesting fact: I was upsolving the silver problems, and on "Robot Instructions", replacing
map<pair<int, int>, ...withunordered_mapwith the hash function from the editorial increased my score from 50% to 100% o.O