### xiaowuc1's blog

By xiaowuc1, 5 months ago,

Hi all,

The first contest of the 2021-2022 USACO season will be running from December 17th to December 20th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is live now! Please read the contest rules carefully, especially regarding how to ask clarifications or contact the contest organizers. Do not spoil anything (including but not limited to your scores or anything about the problems) about the contest until the end of the contest (four hours after the stated deadline of the contest).

Edit 2: Results have been released.

• +255

 » 5 months ago, # |   +25 What are one's chances at plat with 1780 rating (peak 1930)? I've solved virtually all past gold problems since 2015.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +60 I think they're quite high, if this year's contests are like last year's. You got this :DI hope to plat as well xDEDIT: omg I did it!!!
•  » » 4 months ago, # ^ | ← Rev. 5 →   0 Hello CF, today starts the second USACO 2021-2022 contest!!USACO 2021-2022 Schedule. Dec 17-20: First Contest. Jan 28-31: Second Contest. Feb 25-28: Third Contest. Mar 25-28: US Open. TBD (Late May): Training Camp. Aug 7-14: IOI 2022 in Indonesia.
•  » » » 4 months ago, # ^ |   0 Thanks!
 » 5 months ago, # |   0 Thank you for your contests. Would you please also clarify the exact time of each contest?
•  » » 5 months ago, # ^ |   +14 It's not xiawuc's contest, as far as I know. It's run by Brian Dean.
•  » » 5 months ago, # ^ |   +30 The contests are open for several days, Dec 17-20, so you can pick the time window that suits you best. The time starts when you log into the contest, and you only have 1 attempt
 » 5 months ago, # |   +11 Can a specialist with rating 1413 (peak 1553) reach gold in 2 contest?
•  » » 5 months ago, # ^ |   +9 I guess we will find out soon :p all the best.
•  » » » 5 months ago, # ^ |   0 ok I failed, ended silver with 433 pts. 666 was doable. Silver 1 : sad noises :
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 I made Gold when I was ~1400 and had peak 1512 iirc. I got a 400 in December and a 1000 in January.
•  » » 5 months ago, # ^ |   0 I made gold then struggled in pupil for a year lol.
 » 5 months ago, # |   -8 can one give the contest unofficially ?
•  » » 5 months ago, # ^ |   0 yes you can
 » 5 months ago, # |   0 Where can i register for the contest ?
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   0 You dont have to register for the contest — just login and click on start contest on the contest page when you are ready for your window.
•  » » » 5 months ago, # ^ |   0 thanks
 » 5 months ago, # | ← Rev. 2 →   -47 Hope I reach Gold this contest — I am stuck on Silver for the last 2 years although I think my CF rating is high enough to clear Silver.
•  » » 5 months ago, # ^ |   +2 Hope I can reach Gold as well.
•  » » 5 months ago, # ^ |   +6 oh
 » 5 months ago, # |   0 what's the duration for a contest in USACO? Does it vary in leagues(bronze, silver, gold, platinum)?
•  » » 5 months ago, # ^ |   0 The contest is 4 hours for each division. You can take this for any 4-hour window from Dec 17th-20th. Also if you promote in-contest, your timer resets (so for example if you ace Bronze, then you promote to Silver and have another 4 hours for that contest)
•  » » » 5 months ago, # ^ |   0 I could not find any info on this but could you get promoted twice, if you full score two times?
•  » » » » 5 months ago, # ^ |   +4 Yep, technically it's possible to promote to platinum in your first contest by acing everything.
 » 5 months ago, # |   0 Good luck everyone!
 » 5 months ago, # |   0 Anyone ready to increase rank after practicing over summer?
•  » » 5 months ago, # ^ |   +42 No.
•  » » » 5 months ago, # ^ |   0 Ouch.
 » 5 months ago, # |   0 What is the exact start & end time? I can't find it anywhere.
 » 5 months ago, # |   +40 I'm excited to get destroyed by plat problems!
 » 5 months ago, # |   0 I login already but didn't see the start contest button. Can anyone help me ? Thanks
•  » » 5 months ago, # ^ |   0 It doesn't start until tomorrow
•  » » » 5 months ago, # ^ |   0 Oh thanks. But do you know the exact time ?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 You can take it anytime between friday and monday I'm not sure about timezones though just don't wait until last-minute
•  » » » » » 5 months ago, # ^ |   0 Okie thanks a lot
 » 5 months ago, # |   0 If you ace a division, does your timer restarts? If yes, does it start automatically or I will have the right to start whenever I want before 20th dec?
•  » » 5 months ago, # ^ |   0 Yes, your timer restarts when you are promoted to a higher division. You have the right to start your 4-hour contest whenever you like before 20th December. Good luck!
 » 5 months ago, # | ← Rev. 2 →   +48 Since the rules about the usage of the prewritten code are explicitly strict I want to clarify a couple of things. I'm not necessarily having anything against it, just want it to be more clear :) I suppose the rule literally concerns everything in the code so, for example, you have to type every include manually. Can you do all the includes and convenience stuff just once during one particular contest and reuse it between problems? Maybe one could even reuse something like a segment tree between 2 tasks, is this allowed? Or is it supposed to be from scratch in every single problem? If yes to the previous question — can you start doing this 10 minutes before the contest?
•  » » 5 months ago, # ^ |   +39 In the future, you should email the contest organizer these sorts of questions, as the contest organizer does not monitor this forum.The answer to question 3 is very clearly no, independent of the answer to question 2, as that would be considered pre-written code, even if you do it right before you start the contest. The rules very clearly state that using pre-written code is forbidden.The answer to question 2 is probably (again, confirm with the contest organizer) yes. The intent of the rule is to emulate starting from scratch in a "clean" environment, so once you typed out the code, you should be able to copy/paste it freely within a problem or across problems.
 » 5 months ago, # | ← Rev. 3 →   +12 If I promote from x to yCan I participate the next day and whenever? for y
•  » » 5 months ago, # ^ |   +7 Yes you can if you promote in-contest and it's before the deadline, your timer also resets.
 » 5 months ago, # | ← Rev. 2 →   -41 I did not do well on gold. I wonder can I submit the solution out of contest to check whether my fixed version is right or should I wait until after 20th Dec ?
•  » » 5 months ago, # ^ |   +12 You will have to wait until after the problems are available for practice. You can also check whether your solution is right with someone who may have solved that problem you resolved after the official conclusion of the contest. Also, note that the contest ends at around 7 AM on December 21st ET.
 » 5 months ago, # | ← Rev. 2 →   -105 sry
•  » » 5 months ago, # ^ | ← Rev. 3 →   -66 sry
•  » » » 5 months ago, # ^ |   +58 In the future, it'd be best to read the announcement and rules more carefully: Do not spoil anything (including but not limited to your scores or anything about the problems)
•  » » » » 5 months ago, # ^ |   +5 i got it, im sorry, i lost all my contribution already in literally a month i will be like 'i was so stupid back then'
•  » » 5 months ago, # ^ |   0 Thank youmy frmied!!!!!! With this information, I now know the problems givennin the contest and i can easily AK after i solve each one outside contest!!!!
 » 5 months ago, # |   +11 If we get AC on most of testcases of a problem will we get some points from that problem or not?
•  » » 5 months ago, # ^ |   +5 You can get partial score i.e getting 5/10 testcases in 1 problem will give around 333/2 points
•  » » » 5 months ago, # ^ |   +1 How can we see score?
•  » » » » 5 months ago, # ^ |   0 You have to calculate your score manually, I think.
•  » » » » » 5 months ago, # ^ |   +16 Does samples count towards scores?
•  » » » » » » 5 months ago, # ^ |   +9 Yes, they’re basically free points.
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +6 except, by law, you aren't allowed to just read the examples and print the example directly, as your program isn't computing anything per se (thus, a program that is just reading the input and checking if it correspond with some example to print some output would not be accepted). Hope, though, this will be the case, because spoiler
•  » » » » » » » » 5 months ago, # ^ |   +11 Aren't you allowed to do so in case you have something else in your solution though? Meaning that if you are trying to solve a certain subtask which does not include every samples, you are allowed to print out sample answers. I think you are referring to the sixth note in the General Technical Details, which counters only solely printf solutions. (Furthermore, not allowing stuffs like that would be unreasonable, as USACO refuses to judge solutions which does not completely pass samples, and since some problems are essentially two independent problems, it would be impossible to solve one without at least solving a subtask for the other.)
•  » » » » » » » » 5 months ago, # ^ |   +69 In fact, I don't really understand this rule. Does it mean that programs that do not contain any computational procedures, but only print statements, are forbidden?For example, suppose my program contains a corner case, am I violating this rule by directly outputting the answer to such case?Or, if I just guessed a random formula for a problem to pass all the examples. Is this a violation of the rule?
•  » » » » » » » » » 5 months ago, # ^ |   +4 nah corner cases r finePrograms that consist of essentially nothing more than print statements may be disqualified. If feedback for certain test cases is provided during a contest, you are NOT to submit repeated programs consisting of essentially print statments in order to reverse-engineer the inputs. Programs must actually compute the requested answers, not just print results from a pre-computed lookup table.
 » 5 months ago, # | ← Rev. 222 →   -106 .
•  » » 5 months ago, # ^ |   +9 Please reread this page carefully as it states all the contest rules. Note that this includes sharing your score and giving insight about the problem.
•  » » 5 months ago, # ^ |   +22 now i know a reason to improve in jitterclicking
 » 5 months ago, # |   0 Can I participant in this contest?
•  » » 5 months ago, # ^ |   +15 Anyone can still participate in the contest. Make sure to register for an account, and start the contest when you're ready. Good luck!
•  » » » 5 months ago, # ^ |   0 Thank you so much :)
 » 5 months ago, # |   +2 when will the editorial be published?
•  » » 5 months ago, # ^ |   +47 The contest is still running. It should be available after the contest.
 » 5 months ago, # |   +6
 » 5 months ago, # |   +1 The contest is over now? How do you all perform?
 » 5 months ago, # |   +4 Any idea for silver's problem 1? (The contest has already end acording to the usaco site)
•  » » 5 months ago, # ^ |   +3 Consider the farms between two cows of Farmer Nhoj, using two cows of farmer john you can get all the farms between any two cows Farmer Nhoj. So for each such segment find maximum value of tastiness you can get using only 1 cow Lets call it $P_i$. and tastiness if you use two cows be $Q_i$. For a moment use 2 cows on each segment. Now number of cows used might be greater than $N$. So greedily Decrease the value by finding the minimum delta (that is either convert 2 cows to 1 cow for some segment, or 1 cow to 0).
•  » » » 5 months ago, # ^ |   0 Thanks
•  » » » 5 months ago, # ^ |   +16 For each segment, if using 1 cow you gain $P_i$ while using 2 cows you gain $Q_i-P_i$, We also can easily prove that $P_i\geq \frac{Q_i}{2}$. Hence if we use 2 cows, then the event of 1 cow would be considered already. Then we have a sorted list of values, for each cow we used.
•  » » 5 months ago, # ^ |   0 Greedily select the intervals from starting. Start from the leftmost position and continue till you can select the patches. Also start as far as you can from the first patch you are selecting.
•  » » 5 months ago, # ^ |   +14 I didn't participate in silver so I can't submit but here's my idea.Consider the $M$ cows, they divide the grass into $M+1$ intervals(if a grass is on one of these cows, just delete them).It's obvious that the placement of the $N$ cows in different intervals are independent.If we put two cows in one interval, we will put them in position $L+1$ and $R-1$ (the interval is $[L,R]$), so every grass in the interval will be choose (we just need one cow if the interval is the leftmost one or the rightmost).If we put one cow in one interval, one consecutive segment of the grasses will be chosen and we will find the maximum one.Define the total value of one interval $V2$, we consider the two ways of placing the one cow. Put it in $L+1$ Put it in $R-1$ It shows that these two segments of grasses will cover all the grasses in the interval, so if we define $V1$ as the maximum value of placing one cow, we know that $2*V1\ge V2$, which means $V1\ge V2-V1$.Now will put the $N$ cows one by one into the intervals. Put one cow in the interval with $0$ cows has the value $V1$. Put one cow in the interval with $1$ cow has the value $V2-V1$. Just sort all the values ($V1$,$V2-V1$) and take the maximum $N$ ones and it will be valid.(Because due to the observation $V1\ge V2-V1$, value $V1$ will always be taken before value $V2-V1$, so this method must be valid.)Complexity: $O(nlogn)$
 » 5 months ago, # |   +3 How to solve silver problem 3?
•  » » 5 months ago, # ^ |   +3 You can subtract the number of invalid pairs from $N^2$.Notice that invalid pairs are of the form: $a_1 + a_2 \gt k$ $b_1 + b_2 \lt k$ these are $2$ dsjoint sets.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +27 If you go from 0 to 2M, you see the event $a_i+a_j$ your results increase by 1, while you see $b_i+b_j$ your results decrease by 1. Complexity $O(M^2)$.
•  » » » 5 months ago, # ^ |   -8 Isn't O(N^2) too slow?
•  » » » » 5 months ago, # ^ |   +8 It is $O(M^2)$, sorry for the typo, since $a_i$ and $b_i$ are bounded by $M$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Observe that M was quite less. So store the count of all possibilities of ai + aj and bi + bj. Now you can create a difference array, and iterate for all possible sums from 0 to 2*m, add cnt[] to the difference array for sum values of a (because range starts here) and -cnt[] to the difference array for sum values of b (because range ends here). Finally, calculate the prefix sum to get the answers for all k. Overall time complexity : O(max(n,m2))
 » 5 months ago, # |   0 Okay... How to solve Gold 1 ?For t=1 i solve it with dp[i-th element][choose or not], but t=2 I try to use dp[i-th element][previous one statue][current state]status 0 = not choose1 = choosed and will make pair with later one2 = choosed and paired with previous onei wrote the dp for a long time and finally find the bug at the last minute but can not submit.Can anyone tell me is it correct?
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 For t=2, how will you check that any pair of not chosen elements are not within a range of k with this dp state? Also, there is an easy greedy approach for t=1 as well. First observe that if you know which elements you have to keep single, then greedily you should select the remaining consecutive elements to pair up. For t=1, there will be some disjoint ranges. You can separate ranges when abs(a[i+1]-a[i])>k. Now a particular range will always contain an odd number of elements, there will be several cases to remove at max one element, start pairing from the end and calculate the min value until you can pair from the end. Codell cal(vector > &a) { ll n=sz(a),ans=inf; if(n==0) return 0; ans=a[n-1][1]; rf(i,n-2,0) { if(i&1) { if(abs(a[i+1][0]-a[i-1][0])<=k) ans=min(ans,a[i][1]); if(abs(a[i+1][0]-a[i][0])>k) break; } else ans=min(ans,a[i][1]); } return ans; } 
•  » » » 5 months ago, # ^ |   0 I used DP, but my state is whether the last 3 guys are used. It's getting wrong answer, and I cannot fix it. here#include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; const ll MAXN = 1e5; ll dp[MAXN][2][2][2][2]; vector> val; ll K; const ll INF = 1e17; ll memoize(int ind, bool b1, bool b2, bool b3, bool b4) { if (ind < 0) { return 0; } if (dp[ind][b1][b2][b3][b4] != -1) { return dp[ind][b1][b2][b3][b4]; } vector v = {b1, b2, b3, b4}; for (int i = 0; i < v.size(); i++) { for (int j = i + 1; j < v.size(); j++) { if (!v[j] && !v[i] && ind - i >= 0 && ind - j >= 0) { if (abs(val[ind - i].first - val[ind - j].first) <= K) { return INF; } } } } //b4 represents our current guy dp[ind][b1][b2][b3][b4] = INF; if (ind == 0) { if (!b1 && !b2 && !b3 && !b4) { return (dp[ind][b1][b2][b3][b4] = 0); } return (dp[ind][b1][b2][b3][b4] = INF); } else if (ind == 1) { if (b1 && b2 && !b3 && !b4) { if (abs(val[0].first - val[1].first) <= K) { return (dp[ind][b1][b2][b3][b4] = val[1].second + val[0].second); } } if (!b1 && !b2 && !b3 && !b4) { return (dp[ind][b1][b2][b3][b4] = 0); } return (dp[ind][b1][b2][b3][b4] = INF); } if (b1) { //this means that we want to fill b1 if (b2) { //b2 needs to be filled if (abs(val[ind].first - val[ind - 1].first) <= K) { ll prev = INF; for (int b5 = 0; b5 <= 1; b5++) { for (int b6 = 0; b6 <= 1; b6++) { prev = min(prev, memoize(ind - 2, b3, b4, b5, b6)); } } return (dp[ind][b1][b2][b3][b4] = prev + val[ind].second + val[ind - 1].second); } return INF; } else if (b3) { //we want to fill b1 & we want to pair it with b3 if (abs(val[ind].first - val[ind - 2].first) <= K) { ll prev = INF; for (int b5 = 0; b5 <= 1; b5++) { for (int b6 = 0; b6 <= 1; b6++) { for (int b7 = 0; b7 <= 1; b7++) { if (ind >= 4 && !b5 && abs(val[ind - 1].first - val[ind - 4].first) <= K) continue; if (ind >= 5 && !b6 && abs(val[ind - 1].first - val[ind - 5].first) <= K) continue; if (ind >= 6 && !b7 && abs(val[ind - 1].first - val[ind - 6].first) <= K) continue; prev = min(prev, memoize(ind - 3, b4, b5, b6, b7)); } } } return (dp[ind][b1][b2][b3][b4] = prev + val[ind].second + val[ind - 2].second); } return INF; } return INF; } if (!b1) { return (dp[ind][b1][b2][b3][b4] = min(memoize(ind - 1, b2, b3, b4, true), memoize(ind - 1, b2, b3, b4, false))); } } int main() { freopen("fairphoto.in", "r", stdin); //freopen("fairphoto.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); ll T, N; cin >> T >> N >> K; val.resize(N); ll tot = 0; for (int i = 0; i < N; i++) { cin >> val[i].first >> val[i].second; tot += val[i].second; } if (T == 1) { cout << 2; return 0; } for (int i = 0; i < N; i++) { for (int d1 = 0; d1 <= 1; d1++) { for (int d2 = 0; d2 <= 1; d2++) { for (int d3 = 0; d3 <= 1; d3++) { for (int d4 = 0; d4 <= 1; d4++) { dp[i][d1][d2][d3][d4] = -1; } } } } } ll myMax = 0; for (int d1 = 0; d1 <= 1; d1++) { for (int d2 = 0; d2 <= 1; d2++) { for (int d3 = 0; d3 <= 1; d3++) { for (int d4 = 0; d4 <= 1; d4++) { myMax = max(myMax, tot - memoize(N - 1, d1, d2, d3, d4)); //memoize(4, d1, d2, d3, d4); } } } } cout << myMax << '\n'; } Help?
 » 5 months ago, # |   -17 I think it's not very healthy how almost every Platinum problem is being set by the same person for quite a while now.
•  » » 5 months ago, # ^ |   +52 Why?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -25 Every author comes up with problems that share a distinct taste, which inevitably favors some contestants— just look at the number of counting problems. Personally, many of these statements feel quite artificial, and just not very interesting.
•  » » » » 5 months ago, # ^ | ← Rev. 4 →   +166 Well, at least the counting problem wasn't mine this time. :) I think it's not very healthy how almost every Platinum problem is being set by the same person for quite a while now. I agree with this, it's not very healthy for me. Unfortunately, there are not very many Platinum proposals in the database that are not by me ...
•  » » 5 months ago, # ^ |   +56 Totally agree, I think people who are not xiaowuc1 should stop setting Platinum problems
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +44 Can you be hired to set platinum problems? I think USACO would benefit from some data structures problems and some matroid intersection problems.
 » 5 months ago, # |   +49 How to solve Pt 2 ?
•  » » 5 months ago, # ^ | ← Rev. 5 →   +55 First, split the two types of cows into two arrays sorted by their position, afterwards, $t=1$ is pretty simple, since you can use $dp[i][j]$ = minimum sum of weights of unpaired cows if we've paired up or left unpaired the first $i$ cows of the first type and the first $j$ cows of the second type. For this dp we won't have to worry about the maximal matching part since the needed cost is minimal so we won't ever leave unpaired two cows which could have been paired together. For $t=2$ though, the maximal matching requirement becomes a problem, so the first ideea here would be something like $dp[i][j][k][0/1] =$ maximum sum of weights of unpaired cows if we've paired up or left unpaired the first $i$ cows of the first type and the first $j$ cows of the second type, and we aren't allowed to leave any cow unpaired in the next $k$ cows of the first or second type (given by the 0/1). This works in $n^3$. In order to optimize this, let's define $dp[i][j][0] =$ maximum sum etc. ---||--- if we don't have any restriction going forward (we can leave a cow on either sides unpaired) , $dp[i][j][1] =$ ---||--- if we are only allowed to leave a cow unpaired on the left side , and $dp[i][j][2] =$ ---||--- if we are only allowed to leave a cow unpaired on the right side. Notice that in all of these states, we can always pair up the next cows.Let's see how to calculate this, I'd suggest doing it forward. Say we're in a state of the form $(i,j,0)$ meaning we paired up all the first $i$ cows on the left, $j$ cows on the right, and we can now leave a cow unpaired on either side, then, we can either: pair up the cows $i+1$ and $j+1$ (if possible) going to $dp[i+1][j+1][0]$ leave a cow unpaired. WLOG, let's assume we leave the $(i+1)$th cow on the left unpaired, this means we now have some $k$, for which we aren't allowed to leave any right cow unpaired among the next $k$ cows. So, if we assume we are going to pair up the next $k$ cows on the right with the next $k$ cows on the left (and if this is possible) this means, this dp could update $dp[i+1+k][j+k][0]$. But maybe, we're gonna leave some more cows unpaired on the left, since there isn't anything stopping us, so we should also update $dp[i+1][j][1]$. It turns out these two are sufficient, since whenever we're going to leave a cow unpaired on the left, that'll also update a dp of type $0$ in some $k'$ steps (I'm not sure how clear I explained this, but if you try to prove it, it will probably make sense). Finally, the transitions from other types of dp (such as $dp[i][j][1]$) are very similar, the only difference is the fact that we aren't allowed to leave a cow unpaired on some side.Damn! this is a big block of text, sorry for that but idk how to format xD.
 » 5 months ago, # |   +69 Okay so for Silver problem 3 there is a very funny solution that works in $\mathcal O(n+m\log m)$ time. For all pairs $(i, j)$ setup polynomials $P_{i, j} = \sum_{k = a_i+a_j}^{b_i+b_j} x^k$Notice how the numbers $t_i$ we want from $0$ to $2M$ are essentially the coefficients of monomials $x^i$ in the sum $\sum_{i, j} P_{i, j}$. In order to solve this problem efficiently note that $(1-x)P_{i, j} = x^{a_i+a_j}-x^{b_i+b_j+1}$ and thus when we sum this over all pairs, we obtain a sum of $\dfrac{(\sum_{i} x^{a_i})^2 - x(\sum_{i} x^{b_i})^2}{1-x}$. Now we can use FFT and $\mathcal O(m)$ computations to solve the problem completely.
 » 5 months ago, # |   +8 Does anybody knows how to re-open problems (or have screenshotted the problems)? (I would really like to ask the solutions from strong CPers who haven't participated in the contest, but I don't remember the samples.)
 » 5 months ago, # |   +18 There is a subproblem I encountered which seems pretty standard but I couldn't come up with a good idea quickly.Given a set of $n$ segments and online point queries you need to return all segments that contain this point and you haven't returned before.I strongly feel like it should have a clean $n \log n$ solution that is not too hard to implement but for now I can only solve it in $n\sqrt n$ with some slightly unpleasant code complications. Does anybody know it or have any ideas?
•  » » 5 months ago, # ^ |   +45 You can maintain a segment tree over the values.If there is a segment (a,b) you basically need to add the index of the segment to the log(n) nodes which cover the (a,b) range.When there is query you can extract the values present in the log(n) nodes which cover the query index i.You have to erase all the values in these nodes also
•  » » » 5 months ago, # ^ |   +16 Oh wow, it's very nice and clean indeed) Thank you! Can't believe I spent a very considerable amount of time on that.
•  » » » » 5 months ago, # ^ |   +19 Fun fact: this kind of segment tree is given as the definition of segment tree on Wikipedia.
•  » » » » » 5 months ago, # ^ |   +11 :D
•  » » 5 months ago, # ^ |   +13 Here's another (maybe dumber lol) method: for each left endpoint $a$, sort all segments $(a, b)$ in increasing $b$ order. Then maintain a segment tree which stores the maximum $b$ for each $a$. Finding whether there currently exists a segment which contains $x$ can be done by seeing if the max of values in the range $[0, x]$ is at least $x$. To get the segment, the segment tree can also return the index of the max, and then it can be replaced with the next longest segment which begins at $a$.
 » 5 months ago, # |   0 For bronze, how did you guys get the last test case for the first problem? I got TLE the first time, then WA the second.
 » 5 months ago, # |   0 Can someone give me some hints about bronze problems pls ? I found them really interesting.
•  » » 5 months ago, # ^ |   0 For problem 1, go over every letter, then check forwards and backwards for how many lonely photos. For problem 2, start from the ends For problem 3, it's just implementation, no trickiness
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I think you had implemented the solution by partial sum but it gets TLE on the last testcase because It uses $O(n ^ {2})$Time.
•  » » 5 months ago, # ^ |   0 For problem 2, I used divide and conquer. It might have been overkill
 » 5 months ago, # | ← Rev. 2 →   +10 Is there a way to solve Platinum problem 1 in less than $O(N+K\log^2 K)$ time?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +11 The problem reduces to dijkstra on O(N+K) vertices and O(N+KlogN) edges, however, only O(K) edges are non-zero, so I suspect that you can solve it in O(N+KlogN) with some modified priority_queue.
•  » » » 5 months ago, # ^ |   +10 I got that it reduces to Dijkstra on $O(K)$ vertices and $O(K\log K)$ non-zero edges. It's possible my graph differs from yours.
•  » » 5 months ago, # ^ |   -19 Fibonacci Heap? $O(NlogN+KlogN)$
•  » » 5 months ago, # ^ |   +18 My solution works in $O((N + K) \log (N + K))$ time.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +60 I think my solution works in $O((n+K)\log(n+K))$ but I can't find it now. It tested so in random cases(but very slow).I used a segment tree to optimize Dijsktra directly, instead of adding $K\log n$ edges.Reverse the graph first.For every ticket, insert $[l_i,r_i]$ into the segment tree.For each node on the segment tree, only the cheapest ticket might become the next one to use, let its value be ${mn}_p$, and it may start from any station in the segment, let $d_p$ denote the smallest ${dis}_i$ among $l\sim r$(where $l$ and $r$ are endpoints of the segment).Every time find $\min{{mn}_p+d_p}$, by carefully implenting it we can get a $O(n\log n)$ solution.But it seems that the constant is rather huge(a lot of maintained on segment tree), I spent a lot of time optimizing it.
 » 5 months ago, # | ← Rev. 2 →   +1 How to solve 2nd problem of silver division? I tried to do that with DSU but was unable to get the minimum distance between two pairs of DSUs.
•  » » 5 months ago, # ^ |   +5 To calculate the cost between two connected components you can use lower_bound to find the closest element in the second set for each one in the first.Now you can simply brute force the connected component that will be connected to 1's and n's component as it allowed to add at most 2 edges.To reach O(n*lg(n)) complexity we shall consider each element of the smaller set when calculating the cost.
 » 5 months ago, # |   0 Gold P1#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct segmentTreePoint { vector v; vector vec; vector addLater; void upd(int dum, int tl, int tr, int &l, int &r, int val) { if (tr < l || tl > r) { return; } if (tl >= l && tr <= r) { addLater[dum] += val; return; } int mid = (tl + tr) >> 1; dum = dum << 1; upd(dum, tl, mid, l, r, val); upd(dum + 1, mid + 1, tr, l, r, val); } void upd(int l, int r, int val) { upd(1, 0, v.size() - 1, l, r, val); } int get(int x) { int cur = x + v.size(); int ans = 0; while (true) { ans += addLater[cur]; if (cur == 0) { break; } cur /= 2; } return ans; } void resz(int n) { v.assign((1 << (int)ceil(log2(n))), 0); vec.assign(v.size() * 2, 0); addLater.assign(v.size() * 2, 0); } }; struct Changer { set occurences; string s; segmentTreePoint pref; int right(int x) { auto it = occurences.upper_bound(x); if (it == occurences.end()) { return -1; } return (*it); } int left(int x) { auto it = occurences.lower_bound(x); if (it == occurences.begin()) { return -1; } it--; return (*it); } void generate(int n) { pref.resz(n + 1); s.assign(n, '#'); } void generate_string(string str) { generate(str.length()); s = str; occurences.clear(); for (int i = 0; i < s.length(); i++) { if (s[i] != '#') { occurences.insert(i); } } for (int i = 0; i < s.length(); i++) { pref.upd(i + 1, i + 1, pref.get(i)); if (left(i) == -1) continue; if (s[left(i)] == 'H' && s[i] == 'L') { pref.upd(i + 1, i + 1, 1); } } } void remove(int x) { if (s[x] == '#') { return; } occurences.erase(x); if (s[x] == 'L') { s[x] = '#'; if (left(x) == -1 || s[left(x)] == 'L') { //left(x) == -1 --> ....*L*...H...H. //s[left(x)] == 'L' --> ..H..L...*L*..... return; } if (right(x) == -1) { //cout << "YES\n"; if (s[left(x)] == 'H') { //....H..*L*...... pref.upd(x + 1, s.length(), -1); } else { //....L...*L*... return; } return; } if (s[right(x)] == 'H') { //....H...*L*...H.. pref.upd(x + 1, s.length(), -1); } else { //...H....*L*...L pref.upd(x + 1, s.length(), -1); pref.upd(right(x) + 1, s.length(), 1); } } else { s[x] = '#'; if (right(x) == -1 || s[right(x)] == 'H') { //right(x) == -1 --> ..H..*H*..... //s[right(x)] = -1 --> ....L..*H*...H...... return; } if (left(x) == -1) { if (s[right(x)] == 'L') { //..........*H*...L.. pref.upd(right(x) + 1, s.length(), -1); } else { //..........*H*...H.. return; } return; } if (s[left(x)] == 'L') { //.....L....*H*...L.... pref.upd(right(x) + 1, s.length(), -1); } else { //.....H....*H*...L.... return; } } } void add (int x, char c) { if (s[x] == c) { return; } remove(x); s[x] = c; occurences.insert(x); if (c == 'L') { if (left(x) == -1) { //....*L*..L. return; } if (right(x) == -1) { if (left(left(x)) == -1) { if (s[left(x)] == 'H') { //...H....*L*... pref.upd(x + 1, s.length(), 1); } else { //...L....*L*... return; } } else if (s[left(left(x))] == 'L') { if (s[left(x)] == 'H') { //.L..H..*L*..... pref.upd(x + 1, s.length(), 1); } else { //..L...L...*L* return; } } else if (s[left(left(x))] == 'H') { if (s[left(x)] == 'H') { //...H...H....*L* pref.upd(x + 1, s.length(), 1); } else { //...H...L....*L* return; } } return; } else { if (s[left(x)] == 'L') { //....L....*L* return; } else if (s[left(x)] == 'H'){ if (s[right(x)] == 'H') { //.H..*L*..H. pref.upd(x + 1, s.length(), 1); } else if (s[right(x)] == 'L'){ //.H...*L*..L... pref.upd(right(x) + 1, s.length(), -1); pref.upd(x + 1, s.length(), 1); } } } } else if (c == 'H'){ if (right(x) == -1) { //..L..*H*..... return; } //there is stuff to the left if (left(x) == -1) { if (right(right(x)) == -1) { if (s[right(x)] == 'H') { //.....*H*....H return; } else { //.....*H*....L pref.upd(x + 1, s.length(), 1); } } else if (s[right(right(x))] == 'L') { if (s[right(x)] == 'H') { //......*H*.H..L. return; } else { //......*H*.L..L. pref.upd(x + 1, s.length(), 1); return; } } else if (s[right(right(x))] == 'H') { if (s[right(x)] == 'H') { //...*H*....H....H return; } else { //.........*H*....L....H pref.upd(right(x + 1), s.length(), 1); return; } } } else if (left(x) != -1){ if (s[left(x)] == 'H') { if (s[right(x)] == 'H') { //..H..*H*..H.. return; } else if (s[right(x)] == 'L'){ //...H....*H*...L.. return; } } else if (s[left(x)] == 'L'){ if (s[right(x)] == 'H') { //.L..*H*..H. return; } else if (s[right(x)] == 'L'){ //.L...*H*..L... pref.upd(right(x) + 1, s.length(), 1); } } } } assert(c == 'H' || c == 'L'); } void print() { cout << s << '\n'; for (int i = 0; i <= s.length(); i++) { cout << pref.get(i) << ' '; } cout << '\n'; generate_string(s); for (int i = 0; i <= s.length(); i++) { cout << pref.get(i) << ' '; } cout << '\n'; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int p[n]; map oc; for (int i = 0; i < n; i++) { cin >> p[i]; oc[p[i]] = i; } oc[0] = -1; set s; map>> myMap; for (int i = 0; i < n; i++) { auto it = s.upper_bound(p[i]); pair p1; if (it != s.begin()) { it--; p1 = {0, *it - 1}; } else { p1 = {-1, -1}; } pair p2 = {max(p1.second, p1.first) + 1, p[i] - 1}; pair p3; p3.first = max(max(p2.second, p2.first), max(p1.first, p1.second)) + 1; it = s.upper_bound(p[i]); if (it == s.end()) { p3.second = n; } else { p3.second = *it - 1; } pair p4; p4.first = max(max(max(p3.second, p3.first), max(p2.first, p2.second)), max(p1.first, p1.second)) + 1; p4.second = n; s.insert(p[i]); //cout << p1.first << " " << p2.first << " " << p3.first << " " << p4.first << '\n'; if (p1.second != -1) { myMap[p1.first].push_back({'#', i}); } if (p2.second != -1) { myMap[p2.first].push_back({'H', i}); } if (p3.second != -1) { myMap[p3.first].push_back({'L', i}); } if (p4.second >= p4.first) { //cout << p4.first << '\n'; myMap[p4.first].push_back({'#', i}); } } Changer changer; changer.generate(n); string str; str.assign(n, '#'); int cntr = 0; for (auto& q: myMap) { cntr++; for (auto& pr: q.second) { //cout << pr.first << " " << pr.second << ' '; str[pr.second] = pr.first; if (pr.first == '#') changer.remove(pr.second); else changer.add(pr.second, pr.first); } int x = changer.pref.get(max(oc[cntr - 1], oc[cntr]) + 1); cout << x << '\n'; } return 0; }  Gold P3#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; struct Checker { int n; vector> adj; vector color; vector parent; int cycle_start, cycle_end; bool dfs(int v) { color[v] = 1; for (int u : adj[v]) { if (color[u] == 0) { parent[u] = v; if (dfs(u)) return true; } else if (color[u] == 1) { cycle_end = v; cycle_start = u; return true; } } color[v] = 2; return false; } bool find_cycle() { color.assign(n, 0); parent.assign(n, -1); cycle_start = -1; for (int v = 0; v < n; v++) { if (color[v] == 0 && dfs(v)) break; } if (cycle_start == -1) { return true; } else { vector cycle; cycle.push_back(cycle_start); for (int v = cycle_end; v != cycle_start; v = parent[v]) cycle.push_back(v); cycle.push_back(cycle_start); reverse(cycle.begin(), cycle.end()); return false; } } }; bool contiguous (set s) { if (s.empty()) return true; vector v; for (int i: s) { v.push_back(i); } return (v.size() == v.back() - v[0] + 1); } pair range (set s) { if (s.empty()) { return {0, 0}; } vector v; for (int i: s) { v.push_back(i); } return {v[0], v.back()}; } void solve () { int N, M; cin >> N >> M; bool fine = true; vector> adj1(2 * N + 1); vector> adj2(2 * N + 1); map> myMap; for (int i = 0; i < M; i++) { int n; cin >> n; int p[n]; map> oc; for (int j = 0; j < n; j++) { cin >> p[j]; oc[p[j]].push_back(j); myMap[p[j]].insert(i); } for (auto& p1: oc) { if (p1.second.size() != 2) { fine = false; continue; } for (auto& p2: oc) { int l1 = p1.second[0]; int r1 = p1.second[1]; int l2 = p2.second[0]; int r2 = p2.second[1]; if (p2.first == p1.first) { continue; } if (l1 > l2 && r1 < r2) { adj1[p1.first].insert(p2.first); } else if (l1 < l2 && r1 > r2) { } else if (l2 > l1 && l2 < r1) { fine = false; } if (l1 <= r1 && r1 <= l2 && l2 <= r2) { adj2[p1.first].insert(p2.first); } } } } vector> rng (2 * N + 1); for (int i = 0; i < 2 * N + 1; i++) { if (!contiguous(myMap[i])) { cout << "NO\n"; return; } rng[i] = range(myMap[i]); } if (!fine) { cout << "NO\n"; return; } vector> new_adj1(2 * N + 1), new_adj2(2 * N + 1); for (int i = 0; i < adj1.size(); i++) { for (int j: adj1[i]) { new_adj1[i].push_back(j); if (rng[i].first < rng[j].first) { cout << "NO\n"; return; } } for (int j: adj2[i]) { if (adj1[i].count(j) || adj1[j].count(i)) { cout << "NO\n"; return; } new_adj2[i].push_back(j); } } Checker c; c.n = adj1.size(); c.adj = new_adj1; if (!c.find_cycle()) { cout << "NO\n"; return; } c.adj = new_adj2; if (!c.find_cycle()) { cout << "NO\n"; return; } cout << "YES\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; while (T--) { solve(); } } 
 » 5 months ago, # |   +8 Hint for Gold Prob2 please?And also what is the solution for the second subtask of the same problem? (I really hope it's not something randomized, please!)
•  » » 5 months ago, # ^ | ← Rev. 3 →   +3 I don't remember the subtasks, and the problems aren't visible right now. Here are some hints, I hope they are helpful! :) Hint 1We can make a binary tree of the permutation. The queries made will correspond to the path from root to $x$ in this binary tree.UPD: actually, the queries will correspond to the path from root to $x$ or $x + 1$, whichever is present at a greater depth. Hint 2Since querying the binary tree for for each query can be $N.Q$ in the worst case, instead we could lazily propagate some information while building our binary tree, which allows us to answer each query in $O(1)$ by accessing the vertex which corresponds to $x$. Hint 3Whenever we go from a parent vertex to its left child, it represents "HI", and when we go to its right child it represents "LO". While building the binary tree we can just keep track of the number of "HILO" encountered on the route from root to each vertex.
•  » » » 5 months ago, # ^ |   +8 The second subtask had one constrain that the permutation is randomly generated.
•  » » » » 5 months ago, # ^ |   +3 Ah. I think that just means that there are no malicious testcases (no testcases which intentionally lead to $O(N.Q)$ time if you build and query the binary tree naively.Now that you say it, I do remember that my first $O(N.Q)$ submission passed those randomly generated testcases.
•  » » » » » 5 months ago, # ^ |   +8 Oh, I see now.And also this idea of binary tree is fabulous, do you remember any other problem using similar ideas like this?
•  » » » » » » 5 months ago, # ^ |   +3 Can't say I do, sorry :(Glad I could help :)
•  » » » 5 months ago, # ^ |   0 Hello, I'm sorry but I don't quite understand what a "binary tree" is referring to. Do you mean that we should make a binary heap over the array, or a binary search tree, or is it something else?
•  » » » » 5 months ago, # ^ |   0 Draw the binary search tree and note that on the path from a node to the root, if you mark left edges as L and right edges as H, then the problem reduces to finding number of HLs on path to the root.
•  » » 5 months ago, # ^ |   +42 Here was my solution (around 30 lines of working code): Hint 1The answer differs by at most 1 between i - 1 and i (i being a value of x, i in the range [1, n - 1]). Hint 2The only point that changes as you step once from i - 1 to i is the guess at i (which moves from the right side of x + 0.5 to the left side). Hint 3Therefore, if a HILO pattern starts at i, then you will have to decrement the answer when moving from x = i - 1 to x = i.Similarly, if a HILO pattern ends at i, you will have to increment the answer. Hint 4However, if we find answers in order from x = 0, 1, 2, ... n in order, there isn't any way to quickly find whether a HILO pattern starts or ends at x (at least I haven't found one yet). Hint 5So, instead, find the change between x = i - 1 and x = i out of order. Then, at the end, put your calculated changes in order and output them.This solution eliminates the need for extra data structures like a BIT (which I think many others used), and is really short to implement. FULL SOLUTION#include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; vector map(n + 1); for (int i = 0; i < n; ++i) map[arr[i]] = i; set> existing; vector changes(n + 1, 0); for (int i = 0; i < n; ++i) { int num = arr[i]; pair t = {num, i}; auto it = existing.upper_bound(t); if (it != existing.end()) { pair u = *it; if (it == existing.begin()) ++changes[arr[i]]; else { --it; pair b = *it; if (u.second > b.second) ++changes[arr[i]]; } } if (arr[i] > 1) if (map[arr[i] - 1] > map[arr[i]]) --changes[arr[i]]; existing.insert(t); } int sum = 0; for (int i = 0; i <= n; ++i) { sum += changes[i]; cout << sum << endl; } return 0; } 
•  » » » 5 months ago, # ^ |   0 Woah, you made it seem very simple.I wonder, was the second problem an easy one for other people? Because, for me, it was a pain to think about it, while on the contrary, the first and the last were somehow trivial.
•  » » » » 5 months ago, # ^ |   0 My code was 350 lines and included a lot of casework + segment tree with lazy propagation (it turns out seg tree isn't needed, but I understood that 50 hours after contest ended). It is different than the binary tree idea and much messier, but I'll share anyways.The main idea is that if you look at the matrix formed with all the "H"s and "L"s, then all columns have some "?"s followed by some "H"s followed by some "L"s followed by some "L"s. We can identify the transition points, where things change, and since there are at most $3N$ updates, if we can point update and query number of "HL"s in $O(1)$ or $O(\log N)$ we're good. Also, we should stop querying after we know our number.To point update just look at 2 characters to left and 2 to the right and figure out if things change and if so, by how much.
•  » » » » 5 months ago, # ^ |   +16 I wonder, was the second problem an easy one for other people? Well, the final idea and code are simple, but in reality this idea wasn't extremely easy for me to think of. In fact, it took the longest time out of all three problems (around 1 hour and 30 minutes) of thinking for me to come up with this solution XD
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Keep the set of pairs (value, position). When you add a new pair $(v, p)$ check the existing element to the left $(v_l, p_l)$ and to the right $(v_r, p_r)$. If $p_r > p_l$ you need to add 1 to answer on $[p, p_r)$, which you can do in linear time. If you put proper initial values into the set there are no corner cases. It is about 15 lines of code.
•  » » » » » 5 months ago, # ^ |   +26 Yep, if I'm not misunderstanding this is what I did (my code isn't the most concise).Small correction: shouldn't it should be O(n log n) time not linear, since you use a set?
•  » » » » » » 5 months ago, # ^ |   0 Yeah, you are right actually it is the same, my bad. I was slightly thrown off by your hints 2 and 3 and haven't read the code close enough until now, just skimmed through.For linear I meant just the part with adding to the answer.
•  » » » » » » » 5 months ago, # ^ |   0 Ah, I see!
 » 5 months ago, # |   +8 I would like to mention a thing about Silver S1. It was a wonderful problem but I submitted a very random code and it managed to pass 8 tests (obviously it's totally wrong) so doing S2, S3 and a random code on S1 could have allowed one to pass silver.
•  » » 5 months ago, # ^ |   0 But maybe S1 is the easiest problem among the three problems.
•  » » » 5 months ago, # ^ |   0 I didn't find it to be that way for me it was as such S1 > S3 > S2 but it could be just me since I am inherently bad at problems involving greedy.
 » 5 months ago, # |   +15 I just upsolved HILO from USACO Gold. I don't see my solution in the editorial. But I think it's a simple O(n) solution: I simulated the process backwards. I maintain intervals of numbers $x+0.5$ that are not distinguishable. At the end, all numbers are distinguishable, so all $n+1$ intervals are of length 1. As you simulate backwards, the intervals above and under the current p[i] get merged, because those weren't distinguishable before. I only maintain the boundaries between the intervals in an "array linked list" and for each interval, what the number p[i] was that merged it last. (last[a] = the last p[i] that merged the interval underneath a). Merging is then just removing from the linked list and updating one number. Which numbers could get a "HILO" in their string at this moment in time? If we have the interval $(a,b)$ that gets split into $(a,p[i])$ and $(p[i],b)$, it can be verified that all numbers $x+0.5 \in (last[a],i)$ get an extra "HILO". Since we need to support range adds and only query at the end, we can maintain the difference array and do prefix sums at the end. Code#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) typedef vector vi; int main() { int n; cin >> n; vi p(n); for(auto& i : p) cin >> i; vi dif(n+2), last(n+1,-1), l(n+2),r(n+2); iota(all(l), -1), iota(all(r),1); auto join = [&](int i) { int a = l[i], b = r[i]; if(last[a]!=-1) dif[last[a]]++, dif[i]--; r[a]=b, l[b]=a; last[a] = i; }; for(int i=n-1;i>=0;--i) { join(p[i]); } int res=0; for(int i=0;i<=n;++i) { res+=dif[i]; cout << res << '\n'; } } 
•  » » 5 months ago, # ^ |   0 Sorry, I don't think I understand what "not distinguishable" is referring to. Is it referring to when a number is skipped for consideration since another number before it already revealed enough info (Like skipping 4 because we already know 3 is too high?)
•  » » » 4 months ago, # ^ |   0 Yeah, I think that's what it means. I'm pretty sure what this solution is doing is that it finds the answers in reverse order (which is why there's for(int i=n-1;i>=0;--i)) then stores them and prints out reversed
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 You can think of Elsie's procedure for guessing the number as follows: Elsie keeps the search range [l,r] (at the beginning [0.5, n+0.5]), which is the interval where the number could still be. Her search interval becomes smaller when she does a query, and she gets the answer HI or LO, just like binary search. If the number she's was going to guess is outside the search range, she doesn't ask it at all.The intervals stored in the array linked list, are exactly the intervals which Elsie could have at this point in time as her search range. So in this way, you can simulate all possible ways for her search to go at once in O(n). If you look in the forwards direction in time, if she guesses a number, it splits the interval that this number lies in in two: The portion where she would answer HI, and the portion where she would answer LO. If you go backwards in time, this corresponds to merging of the intervals above and below the number guessed.
 » 4 months ago, # |   0 December Silver is very hard for me... I hope next contest silver will not be like this :(
•  » » 4 months ago, # ^ |   +11 Don't worry. It will be just harder.