Hello Codeforcers!

As a tester I really enjoyed the round and I highly recommend everyone to participate in it!

As a tester, this round will happen at a really funny time!

As a tester I really liked the problems, I recommend you to participate!

What can 1 TON buy me ?

Doge council decided that problems are great and you should participate

As a tester, I'm sad I couldn't participate.

OMG! rainboy is tester!

As a tester, I can say that this round is GOATed!

As a monkey tester, the cows are friendly :)

As a tester, smax orz

as a tester with photo of Stewie Griffin i say .........................................................................Brian Griffin

smax orz

As a tester, I enjoyed helping Farmer John with his never-ending problems.

As a tester, I can confirm the epicness of this contest.

As a tester, I have to say, excellent round, I hope everyone enjoys it thoroughly.

Having such intelligent individuals commenting on the problems is very encouraging, yet depressing at the same time.

Have a nice contest!

orz myvaluska the pupil tester

As a non-tester, I want to say that I hope the round will be cool

Is the score distribution right (1250-750) or it should be (1250-1750).

1800 plz!

Heh, just realized it would be ~4.5 years since my last rated contest, and I'm now kinda willing to take part in a rated one for old time's sake.

Hope that I would not get a -ve delta T.T

UPD: I screwed myself up badly T.T Still the problems were great anyway!

I wish codeforces had the same high quality UI design like ton.org does.

Good luck to everyone!

First time participating in a CodeTON, what is the difficulty of the problems in USACO terms?

Thank you in advance)

value of TON tripled since the last CodeTON round, it's $5/TON now

so the first place winner will receive a prize of $5,000. wow

I believe that listening to the best video game official soundtrack may help your performance during this round.

Thank you all for this wonderful round. I am very excited!

I'm glad that the prize isn't NOT coin :D

mike was too lazy fixing the problem ratings so he thought why not remove rainboy completely from the contest

WOW! Benq Geothermal and rainboy! This test will be wonderful!

What does (1250+750) represents in terms of points, like do we need to solve both the problems to get the points, if not why the D problem is of 750 pints ?

Another 1024 TON to tourist.

Can newbies or beginners register??? And solve problem will there degradation in rating if my problem goes wrong???

i hope i can get 2 ton!

As a tester, I almost forgot to make "as a tester" comment.

Anyway, the problems are great! Huge orz to the setters and I recommend everyone to participate in this round.

left after seeing polygons...

INTERESTING_FORCES unfortunately got so many penalties in C2

Very good and interesting problemset.

this contes could be better

Problem D: Learning to Paint is a straight-forward application of the famous interview problem.

I have added hints and thought process for this problem on CF Step.

254174144

Problem D. Can someone explain, why random gives TL?

#include <bits/stdc++.h>
 
using namespace std;
 
const int N=1010;
int a[N][N];
multiset <int> dp[N];
int perm[N];
 
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<=n;i++) dp[i].clear();
 
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        dp[i].insert(-a[1][i]);
        dp[i].insert(-a[2][i]);
        while(dp[i].size()>k) dp[i].erase(--dp[i].end());
 
        if(i<3) continue;
 
        for(int j=0;j<=i-3;j++) perm[j]=j+3;
        random_shuffle(perm,perm+i-3);
        for(int l=0;l<=i-3;l++){
            int j=perm[l];
            for(int x : dp[j-2]){
                if(dp[i].size()==k && x-a[j][i]>=*(--dp[i].end())) break;
                dp[i].insert(x-a[j][i]);
                if(dp[i].size()>k) dp[i].erase(--dp[i].end());                
            }
        }
    }
    for(int i : dp[n]) cout<<-i<<' ';
    cout<<endl;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie();
 
    int tt;
    cin>>tt;
    while(tt--){
        solve();
    }
 
    return 0;
}

is C2 constructive, casework problem?

calculate the distance, first select power of 2 to get extra, second select even until 2, then add rest? idk

need hints for c1 :/

A question about task E: "It may be the case that the game will continue indefinitely" as far as I'm concerned, that's not true, right? I couldn't find any example configuration where the game continued indefinitely

As a music gamer, I got defeated by the tiebreaker (looking forward to the solution). Anyway thanks for the cool round!

why did I notice E so late? T_T, idk how to solve D without segtree or efficiently with segtree

Can anyone tell why my code is giving wrong answer for question c2? https://mirror.codeforces.com/contest/1942/submission/254186598

UPD: Nvm, system tests are over

Problem C has definitely ruined all this competition.

i did bad, very bad. c1 defeated me. i don't know why i did not notice that the inner polygon is also created for 2 hours.

In D problem1
1- if i do dp to get maximum sum(mx_sum) and hm ways i can get this sum (freq)
2- k-=freq
3- then dose 1 again but i wanna second max so i use the mx_sum from last dp.

is this solution will pass?

A frustrating contest indeed !!

Are some of my observations for E incorrect?

• The only thing which actually matters is the min gap between some $$$a_i$$$ and $$$b_i$$$, i.e, $$$min(b_i - a_i)$$$.

• Any move always preserves the parity of this, meaning P1 will always win for an odd value and lose for an even value.

• The gap between $$$b_{i - 1}$$$ and $$$a_i$$$ doesn't matter since A's movement left / B's movement right is bounded while the other's is unbounded (subject to the loss by parity above).

• So for each odd gap upto $$$L$$$, we can count the number of ways of the min gap between an $$$a_i$$$ and $$$b_i$$$ being exactly that, the answer should be the sum of those values.

• We can get the ways of assigning gaps so min gap between $$$a_i$$$ and $$$b_i$$$ is $$$\geq x$$$ and rest are $$$\geq 0$$$ using bars and stars, so we take (ways of $$$min\ gap \geq x$$$) — (ways of $$$min\ gap \geq x + 1$$$).

This doesn't work for the large sample, any guesses on what I might be missing? (or is it just an implementation skill issue?)

Any reason for such tight constraints in D, isn't brute force O(n^2klogk)

Not gonna give any div1+div2 round onwards. Only div2 seems to be the way.

Great contest. Loved the problems! 💯
Fixed my bug on problem D only to see the "contest over" message flash right before I could submit. 🤧
Well, that's also a fun experience once in a while. The mistakes stick harder! 😂
Expert, here I come! 🤓

not able to solve prob D since last 3 rounds. Disappointment as always

Could you please pose H in a data structure training contest... (or at least have a subtask?) From $$$O(NQ)$$$ to $$$\widetilde{O}(N+Q)$$$ is apparent (if you have prepared) and boring.

.

Is there any $$$O(nk)$$$ solution for D?