Great problems, but too hard for me :,(

Solutions and Implementations aren't visible. Kindly fix it. Thanks.

One of the finest rounds on codeforces. kudos to the problem-setters!

Great Problems.

Tooooooooooooooooooo.. Hard. Yet, very interesting.

.

In problem B, won't only the winners(getting best standings) of the 5 marathons be the only potential candidates for the gold medal? Please, someone, help

In Problem D, I wrote down some examples and observed 3 ways to get a YES answer (First of all I converted all the negatives elements to positive because since we have been given differences, the sign doesn't matter) :- 1) If there exists a 0 in the array. 2) If there are repetitions in the array. 3) If there exists more than one subset sum in the array. :)

I have an $$$O(2^n\cdot n)$$$ solution for D. I don't know why does it work:

void solve() {
    int n;
    cin >> n;
    vec<int> a(n);
    cin >> a;
    set<int> s;
    s.insert(0);
    for(int i = 0; i < (1 << n); i++) {
        int sum = 0;
        for(int j = 0; j < n; j++)
            if(i & (1 << j))
                sum += a[j];
        
        s.insert(sum);
    }

    cout << (len(s) != (1 << n) ? "YES" : "NO") << "\n";
}

I also did problem B in O(nlogn) but i used sorting

Did the setters anticipate non-bitmask solutions to G? It seems that even with some careful book-keeping to avoid performing any $$$O(n)$$$ calculations at the critical deepest level of recursion, the time limit is still pretty strict for these solutions.

My contest solution (123766099) keeps the non-recursive part of every loop at $$$O((k+1-i) \cdot (1 + |S_i \setminus T_{i-1}|))$$$ by following the set and un-set bits to their destinations in advance and attains something close to $$$O((\frac{n+k}{k})^k)$$$ performance. (It's technically a bit worse for large $$$k$$$, but that's not very relevant to this problem.)

I did problem B using a comparator function 123741857

Typo: The latex in hint 3 for H is currently broken

Is it only me or the "Hint 3" in problem H is bugged?

Don't ever upsolve. If a problem appears at one contest, what is the chance it will appear at another? - Gennady Korotkevich

I have another way to do in problem D. First, if there is some zero in the given set, the answer is YES. Otherwise, consider the absolute values |a1|, |a2|, ..., |an| and check whether there are two distinct subsets of the new set s.t their sum are equal. This can be done in O(n.2^n).

How is it supposed to solve D in $$$O(3^n)$$$? Is it a typo, while the actual complexity is $$$O(3^n\cdot n)$$$?

Hello authors,

Thanks for the great contest, all the problems I read were interesting and entertaining to solve and think about.

However, one decision I am confused about is the omission of a max pretest for D. There was no pretest that had 20 test cases of n = 10, and this lead to people FSTing. My solution ran in less than 200 ms on pretests, and so even though I was suspicious of my complexity, I figured that my solution for D was okay, yet it still FSTed.

Next time, please include max tests in the pretests so contestants can be rather certain their solution will pass under the time limit.

Sadly, I got FSTed for D. Interesting problems btw. Kudos!

Edit: Can anyone explain why I got TLE for D while the time complexity seems to be n * O(2 ^ n)? 123771731

1552C - Maximize the Intersections I still completly do not get why we can ignore the initial chords configuration. The editorials seems to not explain it further. Is that something so obvious?

"Problems A and B are meant to be easy!" Really?

I had a different approach for problem F:

First of all, compress all coordinates so each of them is not greater than $$$2n$$$. The solution below uses 1-indexation for compressed coordinates. The original coordinates are kept in array c.

Then do some kind of right-to-left dp, let's call it over. over[i] means the number of times the ant goes from point i - 1 to point i. Then the answer is clearly $$$\left(\sum_{i = 1}^{2n}over[i] \cdot (c[i] - c[i - 1])\right) + 1$$$.

The point is how to calculate the over dp. There are two cases:

• i-th coordinate is y for some portal p. Then over[i] = over[i + 1] - cnt where cnt is the number of telepantings through the portal p. It can be easily found as over[p.x] - over[p.x + 1].
• i-th coordinate is x for some portal p.One can notice that in the half of the cases the ant is moving forward, so over[i] = 2 * over[i + 1] +- 1 (+-1 depends on the initial activity of the portal).

You can read the code here (123756889) or

struct portal {
    int x, y;
    bool active;
 
    friend istream &operator>>(istream &is, portal &p) {
        int a;
        is >> p.x >> p.y >> a;
        p.active = a;
        return is;
    }
};

void solve() {
    autoint n;
    vector<portal> p(n);
    cin >> p;
    vector<int> c{0};
    for (auto[x, y, _] : p) {
        c.push_back(x);
        c.push_back(y);
    }
    sort(c.begin(), c.end());
    vector<int> what(2 * n + 1);
    int index = 0;
    for (auto &[x, y, _] : p) {
        x = lower_bound(c.begin(), c.end(), x) - c.begin();
        y = lower_bound(c.begin(), c.end(), y) - c.begin();
        what[x] = what[y] = index++;
    }
    mod_int ans = 1;
    vector<mod_int> over(2 * n + 2);
    over[2 * n + 1] = 1;
    for (int i = 2 * n; i > 0; --i) {
        int j = what[i];
        if (p[j].y == i) {
            over[i] = over[i + 1] + over[p[j].x + 1] - over[p[j].x];
        } else {
            over[i] = over[i + 1] * 2 - !p[j].active;
        }
        ans += over[i] * (c[i] - c[i - 1]);
    }
    cout << ans << '\n';
}

I think I have done problem B in more simple way. All I did is 2-d vector sorting using my own compare function.
Compare function code:

// size of vector athleteA is 5, result of matches
bool myCompareFunction(vector<int> athleteA, vector<int> athleteB){
    int A_won = 0;
    for(int i=0 ; i<athleteA.size(); i++) {
        if(athleteA[i] < athleteB[i]) A_won++;
        else A_won--;
    }
    return A_won > 0;
}

Only first athlete in sorted vector will be contestant to be superior. Just have to check that.

D can be solved in O(2^n). It's sufficient to check if two subsets have the same sum.

2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/

Alternative solution to 1552F - Telepanting

Let $$$z_i$$$ be the index of the teleporter reached immediately after using the teleporter $$$i$$$ (it can be calculated by binary search).
Let $$$dp_{i,0}$$$ be the number of times $$$x_i$$$ is reached. Let $$$dp_{i,1}$$$ be the number of times the teleporter $$$i$$$ is used. Then, the answer is easy to calculate (you spend $$$x_{z_i}-y_i$$$ time for each teleporter, and if the teleporter is inactive you spend $$$x_{i-1}-x_i$$$ time).
You can calculate $$$dp_i$$$ in decreasing order of $$$i$$$ by obtaining it from the recurrences
$$$\displaystyle dp_{i+1,0} = \sum_{z_j=i+1}{dp_{j,1}} + \lfloor \frac{dp_{i,0} + (s_i \oplus 1)}{2} \rfloor$$$
$$$\displaystyle dp_{i,1} = \lfloor \frac{dp_{i,0}}{2} \rfloor$$$

As there could be multiple possible values of $$$dp_{i,0}$$$, you have to choose the one with the same parity as $$$s_i \oplus 1$$$ (because all the teleporters are active at the end). This can be done by using mod $$$1996488706 = 2 \cdot 998244353$$$.

Submission: 123775629

One of the best tutorial sections of all time! Though I got demoted to pupil :(, still a nice contest! @cip999

Magnificent editorial! I wish all editorials would be at least as detailed as this!

I really liked the contest, since it had a lot of interesting and fun problems.

For me personally it was a bit sad, that my "solutions" A, B, C & D all passed the pretest without any problems, but later my solution for D failed with a TLE although it only took me ~300 ms to pass the pretests.

Since I am new to codeforces, I would like to ask if this is the standard (you are responsible for your own code, so you have to calculate the complexity) or if you normally should be rather safe with a ~300 ms.

Great contest! Looking forward to more :)

Thank you for the contest!

bad pretest for B:,(

Finally I became an International Master after this Round.Thanks to cip999 and dario2994 :)

I can come up with a solution to problem B, which is referred to as 3rd Solution.

I define a comparison between athlete $$$i$$$ and athlete $$$j$$$, athlete $$$j$$$ is called "greater" than athlete $$$i$$$ if and only if athlete $$$i$$$ is superior to athlete $$$j$$$. After sorting the athletes by this compare, each of them, except the first one, will have at least one athlete that come up before and superior to them.

Finally, we check whether the first athlete is superior to everyone else or not.

Implement: https://mirror.codeforces.com/contest/1552/submission/123730552

I solved the D problem with a approach different from the editorial . Have a look at it. I find it interesting. 123742321

The problem C is very very difficult.

Can someone who solved E during Contest explain what went through their mind while solving it? Did you prove the solution u coded ? And what's the first thing came to your mind when u looked at weird ceil(n/(k-1)) constraint?

If there is more than such one athlete, print any of them. Can Someone told me important of this line in Problem B.

Anyone else try doing B with bitmasks?

Can anyone please tell me why I am getting a TLE in my solution of problem B?? 123801888

Federico in B made me think about Federico Chiesa. LOL :)). Anybody have the same imagination?

I think I have an interesting and easy-to-understand solution for B.

Here's the idea:

• Keep a knockout style tournament

• Each player will play 2 other players ( n-1, and n+1)

• Only those players who have won both their matches will advance to the next round

• Eventually, only one person will remain. (Possible winner)

• To check if he's the actual winner, see if he's superior to all other players.

Example:

• First round -> 1, 2, 3, 4, 5, 6, 7
• Second round -> 2, 4, 6 (2 won against 1,3; 4 won against 3,5; 7 won against 6,1)
• Third round -> 6 (Only 6 won against 4,2)
• Now, apart from 6, all other players have lost at least once, so they can't get the gold medal.
• The only thing remaining is to check if 6 is superior to all 6 other players.

Code: https://mirror.codeforces.com/contest/1552/submission/123742601
Complexity: O(n*logn)

What are your thoughts?

tourist is Lionel Messi of cp. GOAT.

Can anybody share the O(nlogn) algorithm mentioned in problem C solution?(=-=)

nu cuoi da tat vi mim qua dak

Best Editorial I have seen ever, thanks

I've seen some solutions for E that do not seem to explicitly check for the ceil(n/(k-1)) constraint and greedily make "n" passes over the array and on each pass tries to pick disjoint intervals whenever it can. (Here's a sample submission that does this).

Does anyone have a proof that this won't violate the ceil(n/(k-1)) constraint ?

O(N log N) solution for problem C:

I used indexed set but could also be done using segment tree.

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>indexed_set;

#define forn(i,m,n) for(ll i=m;i<n;i++)
#define vv vector
#define vi vv<int>
#define ii pair<int,int>
#define vii vv<ii>
#define mp make_pair
#define pb push_back
#define PI 3.141592653589
#define ll long long
#define pll pair<ll,ll>
#define vl vv<ll>
#define ff first
#define ss second
#define MOD 1000000007

ll max(ll a,ll b){ return a>b?a:b; }
ll min(ll a,ll b){ return a<b?a:b; }``

void solve(){
    int n;cin>>n;
    indexed_set st,st1;     //for maintaining unused points
    for(int i=1;i<=2*n;i++){
        st.insert(i);
        st1.insert(i);
    }
    int k;cin>>k;
    vector<pair<int,int>> v;    //for chords
    priority_queue<pair<int,pair<int,int>>> pq;     //(distance points between end points,(points))
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        v.pb({a,b});
        pq.push({-min(abs(a-b),2*n-abs(a-b)),{a,b}});
        //negative sign to maintain shortest chord on top of pq
        st.erase(a);
        st.erase(b);
    }
    for(int i=0;i<n-k;i++){
        auto a=st.find_by_order(i);
        auto b=st.find_by_order(n-k+i);
        v.pb({*a,*b});
        pq.push({-min(abs(*a-*b),(2*n)-abs((*a)-(*b))),{*a,*b}});
    }
    int rem_pts=2*n-2;
    int ans=0;

    //removing the shorter chords first
    while(!pq.empty()){
        pair<int,int> x=pq.top().second;
        pq.pop();
        int a=st1.order_of_key(x.first);
        int b=st1.order_of_key(x.second);
        int intersects=min(abs(a-b)-1,rem_pts-(abs(a-b))+1);
        ans+=intersects;
        rem_pts-=2;
        st1.erase(x.first);
        st1.erase(x.second);
    }
    cout<<ans<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        #ifndef ONLINE_JUDGE
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        #endif

    int te;cin>>te;while(te--)
        solve();
}

Seems like sansen is hacking everyone's G and most of them are failing with TLE, does that mean the system tests were weak? Sorry if I'm getting this wrong

reference:
https://mirror.codeforces.com/contest/1552/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=G
https://i.ibb.co/YPDkbV9/hacks-1.png

problem E,why can construct it? I don't understand.who can help me?

In problem E [n / (k-1)] can be 0, if k — 1 > n. In this case there is no answer, but "One can show that such a family of intervals always exists under the given constraints." Help me, please.

Interesting observation in Problem E I haven't seen mentioned yet. One can look at the special case $$$n=k-1$$$. Then we have the case, that each number belongs to at most $$$1$$$ interval. We can solve this and use the solution to solve the general case.

In the general case we have $$$n$$$ and $$$k$$$ and at most $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ intervals. Then we can split up the $$$n$$$ numbers arbitrary into $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ separate groups with each containing no more than $$$k-1$$$ numbers, and solve each group separately. (I guess, this is the meaning behind hint 1.2)

This isn't the best way to implement the solution, but this train of thought really helped me to come up with a solution.

Can someone explain this part of greedy solution for problem E:

We can say more: the rightmost endpoints of these intervals must belong to $$$[x_{i,j}, x_{i,j+1}]$$$; indeed, if it weren't the case for at least one interval $$$[a, b]$$$, the interval $$$[x_{i,j}, x_{i,j+1}]$$$ would come before $$$[a, b]$$$ in the ordering, so it would actually have been selected.

I agree that interval $$$[x_{i,j}, x_{i,j+1}]$$$ would come before $$$[a, b]$$$ in this case. But we might not select it based on requirement #2. Am I missing something?

in problem B, any two pairs, one must be superior to the other, right?

however you choose 3 chords that connect 3 disjoint pairs of points, no point strictly inside the circle belongs to all 3 chords. what does this means?

Especially problem D was great.

Can someone tell me the $$$O(3^{n/2})$$$ meet-in-middle solution for D?

You have nice problem ideas. You have good English skills. You are devoted to the thing you do. Although I just do the virtual contest (and solved only A), I can say: "Nice problemset!" Thank you very much, sir!

What does the anti-random case look like on problem G?

Why is the Task I a recurrence of 243E - Matrix? What a shame.

The solution to I contains a bug.

Observe that the set $$$I$$$ is nonempty. Let us consider various cases:

This doesn't necessarily hold. For example, if $$$(Z_1, \ldots, Z_3) = (\{1\}, \{2\}, \{3\})$$$ and $$$S = \{1, 3\}$$$, we have $$$I = \emptyset$$$.

This is not a critical one though. One can easily extend the solution's idea to the case of $$$I = \emptyset$$$ (and it's done in my submission: https://mirror.codeforces.com/contest/1552/submission/124438016)

My solution for H isn't based on any proof, only on the expectation that a lot of queried sets will give different answers for different shapes. I don't believe there's a single test where this doesn't hold.

Naturally, I start with finding $$$ab$$$, where $$$a$$$ and $$$b$$$ are the number of rows and number of columns of points belonging to the rectangle (why bother with writing $$$+1$$$). I find all candidate pairs $$$(a,b)$$$; quick testing shows there's at most $$$26$$$ of them, so we only need each query to select up to 1/3 of current candidates to succeed.

Let's pick a set where possible answers for each $$$(a,b)$$$ are simple to find. I go for some integers $$$d_a$$$ and $$$d_b$$$ and points $$$(x,y)$$$ where $$$d_a | x-1$$$ or $$$d_b | y-1$$$: rows with spacing $$$d_a$$$ and columns with spacing $$$d_b$$$. A rectangle with $$$(a,b)$$$ will cover $$$\left\lfloor \frac{a}{d_a} \right\rfloor \le k \le \left\lceil \frac{a}{d_a} \right\rceil$$$ of the selected rows and $$$\left\lfloor \frac{b}{d_b} \right\rfloor \le l \le \left\lceil \frac{b}{d_b} \right\rceil$$$ of the selected columns. That's up to $$$4$$$ answers, each is $$$bk+al-kl$$$.

For each query, I try all possible $$$d_a$$$ and $$$d_b$$$, since there are just $$$40,000$$$ of them. For each of them, I find all possible answers for each remaining candidate $$$(a,b)$$$, then find the answer that corresponds to the largest number of candidates. I pick $$$(d_a,d_b)$$$ which minimises this maximum, ensuring that the number of candidates remaining after the query is small even in the worst case. I ask the query and filter candidates that can give the answer returned by the judge. It works!

Very nice problems!

Another way to think of it is to find two disjoint subsets with the same sum, which has complexity $$$ O(n*2^{2n}) $$$ or $$$ O(n*4^n) $$$ and passes in the time.

Can anyone explain what this method is and why it is working on traversing all 3^n states?

int three2n = 1;
    for (int i = 1; i <= n; i++)
        three2n *= 3;
 
    for (int k = 1; k < three2n; k++) {
        int k_cp = k;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int s = k_cp % 3;
            k_cp /= 3;
            if (s == 2) s = -1;
            sum += s * a[i];
        }
        if (sum == 0) {
            cout << "YES" << endl;
            return;
        }
    }
 
    cout << "NO" << endl;

Best editorial i had ever seen on codeforces. All soutions are explained very clearly and efficiently. UPVOTED.... I wish every editorial on cf would be like this.

Can someone explain the solution to my problem E? I just greedily choose the interval with the leftmost right endpoint (an interval refers to two adjacent points with the same color), and then choose it n/(k-1) times. Once a color is chosen, it is not chosen again. It's weird that I passed the problem.211917556

Graph solution to D is over complicated.

How to solve the bonus for C?