USACO 2021-2022 First Contest

3 years ago, # |

+25

What are one's chances at plat with 1780 rating (peak 1930)? I've solved virtually all past gold problems since 2015.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+60

I think they're quite high, if this year's contests are like last year's. You got this :D

I hope to plat as well xD

EDIT: omg I did it!!!

→ Reply

Platanito_Frito

3 years ago, # ^ |

← Rev. 5 →

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.

→ Reply

Radin_Zahedi

3 years ago, # |

Thank you for your contests. Would you please also clarify the exact time of each contest?

→ Reply

3 years ago, # ^ |

+14

It's not xiawuc's contest, as far as I know. It's run by Brian Dean.

→ Reply

orendon

3 years 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

→ Reply

RaadSharar

3 years ago, # |

+11

Can a specialist with rating 1413 (peak 1553) reach gold in 2 contest?

→ Reply

3 years ago, # ^ |

I guess we will find out soon :p all the best.

→ Reply

3 years ago, # ^ |

ok I failed, ended silver with 433 pts. 666 was doable. Silver 1 : sad noises :

→ Reply

3 years ago, # ^ |

← Rev. 2 →

I made Gold when I was ~1400 and had peak 1512 iirc. I got a 400 in December and a 1000 in January.

→ Reply

oursaco

3 years ago, # ^ |

I made gold then struggled in pupil for a year lol.

→ Reply

codebuster_10

3 years ago, # |

-8

can one give the contest unofficially ?

→ Reply

parth_kabra

3 years ago, # |

Where can i register for the contest ?

→ Reply

ak2006

3 years ago, # ^ |

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.

→ Reply

ak2006

3 years 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.

→ Reply

PQ2876

3 years ago, # ^ |

Hope I can reach Gold as well.

→ Reply

rituI_kr_singh

3 years ago, # ^ |

→ Reply

Stranger321

3 years ago, # |

what's the duration for a contest in USACO? Does it vary in leagues(bronze, silver, gold, platinum)?

→ Reply

Ritwin

3 years ago, # ^ |

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)

→ Reply

Venti_chai

3 years ago, # ^ |

I could not find any info on this but could you get promoted twice, if you full score two times?

→ Reply

Ritwin

3 years ago, # ^ |

Yep, technically it's possible to promote to platinum in your first contest by acing everything.

→ Reply

tdpencil

3 years ago, # |

Anyone ready to increase rank after practicing over summer?

→ Reply

3 years ago, # ^ |

+42

No.

→ Reply

chuka231

3 years ago, # |

What is the exact start & end time? I can't find it anywhere.

→ Reply

ETK.

3 years ago, # |

+40

I'm excited to get destroyed by plat problems!

→ Reply

eclipse17

3 years ago, # |

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?

→ Reply

hydroshiba

3 years ago, # ^ |

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!

→ Reply

3 years 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?

→ Reply

xiaowuc1

3 years 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.

→ Reply

ParsaS

3 years ago, # |

← Rev. 3 →

+12

If I promote from x to y

Can I participate the next day and whenever? for y

→ Reply

adminreyiz

3 years ago, # ^ |

Yes you can if you promote in-contest and it's before the deadline, your timer also resets.

→ Reply

mickeyandkaka1

3 years 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 ?

→ Reply

Cereal2

3 years 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.

→ Reply

kevbamboo

3 years ago, # |

← Rev. 2 →

-105

sry

→ Reply

kevbamboo

3 years ago, # ^ |

← Rev. 3 →

-66

sry

→ Reply

notlikeduck

3 years 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)

→ Reply

kevbamboo

3 years ago, # ^ |

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'

→ Reply

kozliklekarsky

3 years ago, # ^ |

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!!!!

→ Reply

infinite-inverse

3 years ago, # |

+11

If we get AC on most of testcases of a problem will we get some points from that problem or not?

→ Reply

Dan4Life

3 years ago, # ^ |

You can get partial score i.e getting 5/10 testcases in 1 problem will give around 333/2 points

→ Reply

infinite-inverse

3 years ago, # ^ |

How can we see score?

→ Reply

3 years ago, # ^ |

You have to calculate your score manually, I think.

→ Reply

dimachine

3 years ago, # ^ |

+16

Does samples count towards scores?

→ Reply

Grassypotato

3 years ago, # ^ |

Yes, they’re basically free points.

→ Reply

valeriu

3 years ago, # ^ |

← Rev. 2 →

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

→ Reply

dimachine

3 years 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.)

→ Reply

Qingyu

3 years 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?

→ Reply

p3i

3 years ago, # ^ |

nah corner cases r fine

Programs 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.

→ Reply

RaadSharar

3 years ago, # |

← Rev. 222 →

-106

→ Reply

Cereal2

3 years ago, # ^ |

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.

→ Reply

b4nanacream

3 years ago, # ^ |

+22

now i know a reason to improve in jitterclicking

→ Reply

Itsmdshahin

3 years ago, # |

Can I participant in this contest?

→ Reply

Cereal2

3 years 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!

→ Reply

infinite-inverse

3 years ago, # |

when will the editorial be published?

→ Reply

Qingyu

3 years ago, # ^ |

+47

The contest is still running. It should be available after the contest.

→ Reply

coderdhanraj

3 years ago, # |

→ Reply

hiddenanonymous

3 years ago, # |

The contest is over now? How do you all perform?

→ Reply

LoboLobo

3 years ago, # |

Any idea for silver's problem 1? (The contest has already end acording to the usaco site)

→ Reply

rivalq

3 years ago, # ^ |

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).

→ Reply

LoboLobo

3 years ago, # ^ |

Thanks

→ Reply

xiaolaogou

3 years 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.

→ Reply

hackerbhaiya

3 years ago, # ^ |

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.

→ Reply

sjc061031

3 years 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)$$$

→ Reply

Dan4Life

3 years ago, # |

How to solve silver problem 3?

→ Reply

3 years ago, # ^ |

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.

→ Reply

xiaolaogou

3 years 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)$$$.

→ Reply

timreizin

3 years ago, # ^ |

-8

Isn't O(N^2) too slow?

→ Reply

xiaolaogou

3 years ago, # ^ |

It is $$$O(M^2)$$$, sorry for the typo, since $$$a_i$$$ and $$$b_i$$$ are bounded by $$$M$$$.

→ Reply

hackerbhaiya

3 years ago, # ^ |

← Rev. 2 →

Observe that M was quite less. So store the count of all possibilities of a_i + a_j and b_i + b_j. 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,m²))

→ Reply

mickeyandkaka1

3 years ago, # |

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 choose

1 = choosed and will make pair with later one

2 = choosed and paired with previous one

i 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?

→ Reply

hackerbhaiya

3 years ago, # ^ |

← Rev. 4 →

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.

Code

ll cal(vector<array<ll,2> > &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;
}

→ Reply

3 years ago, # ^ |

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 <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <chrono>
#include <random>
#include <queue>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <map>
#include <list>
#include <stack>
#include <algorithm>

typedef long long ll;
using namespace std;
const ll MAXN = 1e5;
ll dp[MAXN][2][2][2][2];
vector<pair<ll, ll>> 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<bool> 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?

→ Reply

SleepyShashwat

3 years 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.

→ Reply

TechnobladeNeverDies

3 years ago, # ^ |

+52

Why?

→ Reply

SleepyShashwat

3 years 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.

→ Reply

Benq

3 years 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 ...

→ Reply

ko_osaga

3 years ago, # ^ |

+56

Totally agree, I think people who are not xiaowuc1 should stop setting Platinum problems

→ Reply

xiaowuc1

3 years 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.

→ Reply

Gary2005

3 years ago, # |

+49

How to solve Pt 2 ?

→ Reply

lucaperju

3 years 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.

→ Reply

StArChAn

3 years 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.

→ Reply

dimachine

3 years ago, # |

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.)

→ Reply

3 years 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?

→ Reply

kshitij_sodani

3 years 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

→ Reply

3 years 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.

→ Reply

TheScrasse

3 years ago, # ^ |

+19

Fun fact: this kind of segment tree is given as the definition of segment tree on Wikipedia.

→ Reply

3 years ago, # ^ |

+11

→ Reply

askd

3 years 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$$$.

→ Reply

arkob

3 years ago, # |

← Rev. 2 →

+10

Is there a way to solve Platinum problem 1 in less than $$$O(N+K\log^2 K)$$$ time?

→ Reply

Tutis

3 years 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.

→ Reply

arkob

3 years 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.

→ Reply

jiangbowen_

3 years ago, # ^ |

-19

Fibonacci Heap? $$$O(NlogN+KlogN)$$$

→ Reply

ko_osaga

3 years ago, # ^ |

+18

My solution works in $$$O((N + K) \log (N + K))$$$ time.

→ Reply

gyh20

3 years 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.

→ Reply

coderdhanraj

3 years ago, # |

← Rev. 2 →

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.

→ Reply

Carmel_Ab1

3 years ago, # ^ |

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.

→ Reply

3 years ago, # |

Gold P1

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;
struct segmentTreePoint {
    vector<int> v;
    vector<int> vec;
    vector<int> 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<int> 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<int,int> oc;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        oc[p[i]] = i;
    }
    oc[0] = -1;
    set<int> s;
    map<int,vector<pair<char,int>>> myMap;
    for (int i = 0; i < n; i++) {
        auto it = s.upper_bound(p[i]);
        pair<int,int> p1;
        if (it != s.begin()) {
            it--;
            p1 = {0, *it - 1};
        } else {
            p1 = {-1, -1};
        }
        pair<int,int> p2 = {max(p1.second, p1.first) + 1, p[i] - 1};
        pair<int,int> 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<int,int> 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 <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <chrono>
#include <random>
#include <queue>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <map>
#include <list>
#include <stack>
#include <algorithm>

#define ll long long
using namespace std;
struct Checker {
    int n;
    vector<vector<int>> adj;
    vector<char> color;
    vector<int> 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<int> 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<int> s) {
    if (s.empty()) return true;
    vector<int> v;
    for (int i: s) {
        v.push_back(i);
    }
    return (v.size() == v.back() - v[0] + 1);
}
pair<int,int> range (set<int> s) {
    if (s.empty()) {
        return {0, 0};
    }
    vector<int> 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<set<int>> adj1(2 * N + 1);
    vector<set<int>> adj2(2 * N + 1);
    map<int,set<int>> myMap;
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;
        int p[n];
        map<int,vector<int>> 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<pair<int,int>> 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<vector<int>> 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();
    }
}

→ Reply

3 years ago, # |

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!)

→ Reply

3 years ago, # ^ |

← Rev. 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 1

Hint 2

Hint 3

→ Reply

3 years ago, # ^ |

The second subtask had one constrain that the permutation is randomly generated.

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

Oh, I see now.

And also this idea of binary tree is fabulous, do you remember any other problem using similar ideas like this?

→ Reply

3 years ago, # ^ |

Can't say I do, sorry :(

Glad I could help :)

→ Reply

Anthony_Smith

3 years ago, # ^ |

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?

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

+42

Here was my solution (around 30 lines of working code):

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

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 <iostream>
#include <vector>
#include <set>
#include <utility>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int n; cin >> n;
  vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
  vector<int> map(n + 1);
  for (int i = 0; i < n; ++i) map[arr[i]] = i;
  set<pair<int, int>> existing;
  vector<int> changes(n + 1, 0);
  for (int i = 0; i < n; ++i) {
    int num = arr[i];
    pair<int, int> t = {num, i};
    auto it = existing.upper_bound(t);
    if (it != existing.end()) {
      pair<int, int> u = *it;
      if (it == existing.begin()) ++changes[arr[i]];
      else {
        --it;
        pair<int, int> 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;
}

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years 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

→ Reply

3 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

3 years 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?

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

Ah, I see!

→ Reply

3 years ago, # |

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.

→ Reply

Zeardoe

3 years ago, # ^ |

But maybe S1 is the easiest problem among the three problems.

→ Reply