Auto comment: topic has been updated by windva (previous revision, new revision, compare).

As a tester,problems are awesome.Hope you enjoy it :)

As a tester, I did not know that the contest would be scheduled this early. Well, that was quite early, I guess.

Anyways, the problemset was enjoyable. Everyone, good luck on positive $$$\Delta$$$, and I hope you enjoy the contest as well (regardless of the $$$\Delta$$$).

As a tester, the last problem is the best problem I've seen recently. Good Luck and Have Fun!

As a tester, windva is handsome, so please participate.

As a tester, I personally did like problem D and E. Hope you do not give up early and have a good result

As a participant, windva is god. :blobaww:

As a tester, I really enjoyed testing this contest.

The problems are creative, and solving these problems require a variety of approaches. Each problem has its unique style, and will broaden your perspective to the next level. Plus, they are fun to solve!

I saw windva putting a tremendous amount of effort and time to run this round. Moreover, windva is really cute, so please do consider participating actively.

Big thanks to windva, for creating this beautiful set, allowing me to test it, and for being cute.

This should be hackable, but I'm too lazy to write a testcase against it.
224983900

Wish me luck I hope this contest is another step into turning gren

We are ready

Good luck everyone! Hope you get your color-up!

I hope this will be an unrated contest for me :)

As a participant, windva is 大. very good at 三行詩. :blobaww:

2 out of 3!

Hope to solve at least one problem :)

Can anyone please explain why when I read input this way it is not accepted : 225037625

but when I read it this way it is accepted : 225042785

I thought both of them the same and I even runned debug with the first test case for the first submission and it just works like how I expected

I'm kinda new here, is this round rated?

Hope that I can solve problem D :)

rated for the participants with rating lower than？

how do I become a tester for some codeforces round?

Guys I won't be able to participate if I just didn't will that effect anything after I registered?

I hope everyone reaches their goal <3

I couldn't solve C, should I commit suicide?

Why dfs in D is so slow. I got TL int $$$O(30 \cdot n)$$$, changed $$$30$$$ to $$$21$$$ and it's still $$$2.7$$$ seconds...

I am going to break my 1666 rating :))

Any hints for C ?

Why the skill difference between D and E so high everytime. btw how to approach E anyone?

This second question that came, well in the third test case why was the output 6 and not 7? You could include 1 too in the set.

What is the logic for B? Thanks.

How do you solve D? (Hints)

A ok

B Unimaginably bad

C Unimaginably bad

D Unimaginably bad

E1 Unimaginably bad

E2 out of my skill no comments

total: 6.9/100 (fail)

abort_dodger_3000

Quite similar problem to problem D : 1187E - Tree Painting

It's basically the same idea

B's pretest were pretty weak, probably gonna fst a lot

Why TLE? It is $$$O(n)$$$

Submission: 225143030

A: We can solve by greedy: Let b[i] be the minimum it can be, which means, if a[i]==b[i-1]+1 then b[i]=b[i-1]+2, otherwise b[i]=b[i-1]+1.

B: For each $$$t \in \bigcup_{i=1}^{n} S_i$$$, assume $$$t \notin S$$$, we can let $$$S = \bigcup_{t \notin S_i}^{} S_i$$$, and take it as a candidate of answer.

C: Observe that if we removed the i-th card, then for j>i we can get max(0, a[j]) score by appropriate order of operations. Assume the most top card we removed is i0-th card, then the answer will be a[i0]*[i0%2==1] + sum(j>i0)(max(0, a[j])).

D: When u is the root, it's useless to do operation on u, and for each other node v, we need to cost (a[parent[v]]^a[v])*size[v] to make a[parent[v]]==a[v]. Therefore, if we let 1 be the initial root of the tree, and u is the parent of v when root is 1, then node v will contribute (a[u]^a[v])*(n-size[v]) to the answer of nodes in subtree of v, and contribute (a[u]^a[v])*size[v] to the answer of other nodes.

E1: We can use 3 operations to swap two numbers in the permutation: [I]*s*[II]t[III] --> [II]*t*[III]s[I] --> [III]*s*[I]t[II] --> [I]t[II]s[III], and do 2 opartions on 1, n will cause no change. Therefore, we can build operation sequences for p[i] and q[i] separately, and if the parity of lengths of them is the same, we can fill (1, n) to operation sequence of p[i] if it's shorter, or fill (1, m) to operation sequence of q[i]. Otherwise, if n is odd, we can add n operations on 1 for p[i], similar for m is odd. If both n and m are even, the answer doesn't exist.

Tried DFS and Rerooting for each bit in D, got TLE, shouldn't 20 * n pass?

The contest is maybe very good But it DID NOT FIT ME. :( problem D is DP. I am not good at DP at all:( especially on tree :(:( E1 WA#10, mistake, didn't pass pretest until contest over. :(

problem C is fun. feel good over A B C.

For Problem C, DP was way straight forward than the greedy method for me. DP Solution

it was a very good contest and I do learn a new thing from D problem thank you Windva for writing these Masterpiece

Why multitest in D???

The system tests for E1 are weak. A test with two decreasing permutations of length 2500 causes my solution to TLE. I'm not sure why some tests were included for E2 but excluded for E1, since I'm pretty sure test 87 from E2 would have caused the same TLE on E1 (the code that causes the TLE is unchanged between my submissions). This also seems like the most intuitively "hard" case, so I'm surprised it wasn't included early on among the pretests for both versions of the problem.

D is too similar with Leetcode 834. It is possible to "transform" 834's solution to D's solution by just adding weight of the egdes by a[u]^a[v]

Leetcode 834 solution (in Chinese version) :https://leetcode.cn/problems/sum-of-distances-in-tree/solutions/

My solution: https://mirror.codeforces.com/contest/1882/submission/225158821

C was too much ad hoc for me, fuc*** my whole contest :(, D was straight kinda straight forward, submitted just after the contest was over :(

Problem B Is too much for div2B

Video Editorial For Problem A,B,C,D

My DP solution for C is not working. Can anyone plzz check?

Super Fast Delta Delivery!

In problem C i got AC but i don't know if my idea is good or just lucky

practically i maintain a multiset where i keep the values that i took

a priority queue where i keep the value i didnt take but are on odd positions

a cnt where i mantain the values i didnt take on even positions

i have a value tura that means if i have to look on even or odd positions , because i deleted a even number or odd number of numbers before

so practically when i am on a odd position i see if its > 0

if it is i take it and tura becomes 1 -tura

if i am on a even position i see if i took a position before if i did and this one is bigger than 0 i take this position as odd also

if i didnt i will see if i have cnt > 0 if yes it means i can take it if its bigger than 0

then if i cant do that either i see if v [ poz ] > min ( multiset.begin() , priority_queue.top())

if yes i take it and i give up a element to the left

Can someone pls explain this solution by Jiangly for problem B? https://mirror.codeforces.com/contest/1882/submission/225097723

Since October 2022, I have participated in 3 CF Rounds, all in May, this year. After that time this one was the first. This year I participated in the IMO and IOI. Hence, during the last few months, I was training for both IMO and IOI. I started training for the IOI after the IMO. During that period I have not participated in any CF Round. I was virtually participating in different 5-hour IOI-style contests, mostly IOI. To understand the problem statements clearly, I read them slowly. And now I think I am not in my best form of CF-style contests. Fortunately, I managed to solve A, B, C, D and to write the code of E. After I finished coding, then finding and fixing bugs, around a minute was remaining for the contest to end, so I quickly tested my code on the test cases available in the statement and sent the code. But… I got WA on TEST 1. What?… and after a few seconds of checking my code, I found the following:

for (i = 0; i < sz(va); i++) cout << va[i] << ' ';
cout << "\n";
 
for (i = 0; i < sz(vb); i++) cout << vb[i] << ' ';
cout << "\n";

I wrote this to locally debug my code to find bugs, and forgot to change it into a comment… I quickly fixed that, but it was already late for a minute… The contest was over… During the system testing I hoped that my idea of the problem was wrong, or that there was another bug in the code (so that the lateness of 1 minute wouldn't change anything), but, fortunately or unfortunately, after the end of the system testing, I sent the fixed code and got AC… WOW… I thought I would be more relaxed should I get WA.

P. S. By the way, the Honourable Mention from the IMO and Bronze medal from the IOI, which I earned, made me feel happy that a story like this happened during the regular round but not the official contest.

Editorial please!

In problem D, how to prove that in the optimal cost solution, all values in the subtree of a node v should become equal to the original value of the node v itself after certain operations?

I'm getting WA on test 5 E1, it says:

Checker Log

wrong answer incorrect A

what does that mean?

Thank you to the author and helpers for the contest! I liked all the problems except D, which I felt was standard and boring, and E2, which I can't solve. C and E1 in particular I like a lot. Thanks again :)

Thnx

DP Solution for C, considering

dp[i][0][0] => not removing the ith index as an even index from the start,

dp[i][0][1] => not removing the ith index as an odd index from the start,

dp[i][1][0] => removing the ith index as an even index from the start,

dp[i][1][1] => removing the ith index as an odd index from the start,

dp[0][0][1] = max(0ll,a[0]);dp[0][1][1] = a[0];

for(i=1;i<n;i++){
        ll x,y ;
        x = dp[i-1][0][0]+max(0ll,a[i]);
        y = dp[i-1][1][1]+max(0ll,a[i]);
        dp[i][0][1] = max(x,y);
        x = dp[i-1][0][1];
        y = dp[i-1][1][0];
        dp[i][0][0] = max(x,y);
        x = dp[i-1][1][1]+a[i];
        y = dp[i-1][0][0]+a[i];
        dp[i][1][1] = max(x,y);
        x = dp[i-1][1][0];
        y = dp[i-1][0][1];
        dp[i][1][0] = max(x,y);
}

submission — 225203776

can anyone explain B to me??

I understood that we need to opt out the set with least no of unique elements wrt other sets,but how to implement this.

Hi, can someone tell me why the following code gives me a runtime error (I ran it in an IDE outside of Codeforces and no RTE was picked up). Thanks.

int main(){
	ll t;
	cin >> t;
	while(t--) {
	    ll n;
	    cin >> n;
	    vector<vector<ll>> s(n);
	    vector<ll> freq(50),k(n);
	    ll maxi=0,m=0;
	    for (ll i=1;i<=50;i++) {
	        freq[i]=0;
	    }
	    for (ll i=0;i<n;i++) {
	        cin >> k[i];
	        vector<ll> a(50);
	        for (ll i=1;i<=50;i++) {
	            a[i]=0;
	        }
	        for (ll j=0;j<k[i];j++) {
	            ll b;
	            cin >> b;
	            a[b]=1,freq[b]+=1;
	            if (freq[b]==1) {
	                m+=1;            }
	        }
	        s[i]=a;
	    }
	    for (ll i=1;i<=50;i++) {
	        vector<ll> freqnew=freq;
	        for (ll j=0;j<n;j++) {
	            vector<ll> c=s[j];
	            if (c[i]==1) {
	                for (ll l=1;l<=50;l++) {
	                    freqnew[l]-=c[l];
	                }
	            }
	        }
	        ll num=0;
	        for (ll i=1;i<=50;i++) {
	            if (freqnew[i]>0) {
	                num+=1;
	            }
	        }
	        if (num<m) {
	            maxi=max(num,maxi);
	        }
	    }
	    cout << maxi << endl;
	}
	return 0;
}

Really fun round ngl

I and wxy_is_a_dog/2255153050 had studyed the Replacing DP，and we studyed https://www.cnblogs.com/wlzhouzhuan/p/12643056.html this blog.So our solutions have something in same by accident.

I got a message stating that my solution to the problem 1882C - Карточная игра coincides with qilby's submission (both submissions: 225107761, 225130187). The submissions are very similar (and what's even funnier, our nicks are also pretty similar), but the coincidence happened only due to how short the solution to that problem was (all variable names used there are pretty standard like $$$s$$$ for sum and $$$ans$$$ for answer or $$$ll$$$ for long long type). Moreover, I've submitted the solution $$$\approx$$$ 30 mins after De_Coder so it would make no sense to take that long if I had been cheating. The solution didn't use any data structures/advanced algorithms hence I didn't use any code written before the contest.

MikeMirzayanov

For Question B, Set and Union. Test Case 3.

s2 U s3 U s5 = {1,3,5,6,8,9,10} but the test case missed 1. i.e s2 U s3 U s5 = {3,5,6,8,9,10}. Why is 1 missing for test case 3?

The answer for test case 3 should be 7 right?