Hello codeforces!

BrayanD, dmga44 and I are glad to invite you to Codeforces Round #768 (Div. 1) and Codeforces Round #768 (Div. 2) which will be held on Jan/27/2022 17:35 (Moscow time).

Each division will have **6** problems, and you will have **2** hours to solve them. The round will be rated for both divisions.

We would like to thank:

Aleks5d for his excellent round coordination.

albertolg101 and jmrh_1 for helping in the early stages of the contest.

I_Remember_Olya_ashmelev, nweeks, 16204, windazz, Ali.Kh, vaaven, marcOS, low_, Riladavin, TeaTime, MDario, aniervs, Dragonado, Saborit, 4qqqq and saarang for testing and providing useful feedback.

MikeMirzayanov for the great platforms Codeforces and Polygon.

Score Distribution:

Div. 2: $$$500 - 1000 - 1500 - 2250 - 2250 - 3000$$$.

Div. 1: $$$500 - 1250 - 1250 - 2000 - 2500 - 3000$$$.

Good luck to all participants! Hope you enjoy the contest.

UPD1: Editorial

UPD2: Congratulations to the winners.

Div. 1:

Congratulations to all of them for solving all problems!

Div. 2:

As a tester, I tested… GL&HF

Xi Ximpingpong playing tennis with peng shuai in XINJIANG.

## whereispengshuai

Don't forget that Adonis is a gentleman, he reads, meditates and works out daily, doesn't waste precious time in gaming or social media, doesn't fap, stays on his diet, works hard for his goals, respects women and his parents, and doesn't settle for weakness. Be like Adonis my friends, be the best version of yourself you can be.

You're asking coders to work out and meditate lol...

Being skinny or fat doesn't help you in any way. A healthy mind resides in a healthy body. For a healthy body we should exercise and for a healthy mind we should meditate. Having a healthy body and mind will help us live a longer life without miseries.

Of course you should keep coding but at the same time take care of yourself. Your future self will not regret it.

Meme!One of the first Cuban rounds!!!!!!!!!!! humbertoyusta, BrayanD, dmga44, albertolg101, jmrh_1, marcOS, MDario, aniervs, Saborit OTZ

Actually, it's the second or third already.

Oh I see, fixed.

Don't forget Codeforces Round #659 (Div. 1)

unforgettable

I am still drowning inorder to help koa in div2 of this contest

This contest is hell tough for beginners like me

Probably the round where we see our first 4000+. GL tourist

:')Don't wanna jinx it

Another division should be created for this single person

He'll reach infinity rating pretty quickly then

And what about that?

jejeje (aniervs flashbacks)

I read about him on the wikipedia, he used to spent no more than 4 hours on his computer, Unbelievable...

Um_nik wins.

not happening now. You did jinxed it.

jinxed...

Congratulations guys, nice job!

During testing I really enjoyed solving problems of the round and I hope participants will enjoy as much as I did.

Why no IGM/LGM testers?

they have to participate to help tourist cross 4000 rating

Quite excited to participate in this round!

I'm happy to see a cuban round again ! I remember that I really enjoyed the first cuban round I did :D

Can anyone explain what does "cuban round" mean ? ,Thanks in advance .

It means that the authors are from Cuba.

I am sorry for previous comment.

It is a normal codeforces round, hope you enjoy the contest.

Thanks ^_^

Why did you downvote my comments ?

You have asked stupid and googleable question

He isn't stupid but your mother is stupid

Please don't say like this, you must be respectful

I said thanks and they downvote it bro

People thought you were trolling because not knowing Cuba the country is quite rare, but maybe you're just young.

Don't worry too much about the downvotes, it just means what you asked was not relevant to most people which is understandable.

Thank you very much for explaination.

That was a legitimate question. There is no such word as "cuban" (uncapitalized).

Meme:Actually, they were going to give shorts to the winners instead of T-shirts, but now you spoiled it.

Could you please give pants instead? So rare nowadays… (∩︵∩)

But then again, can we really tell if they are pants or not? Rather like the gender of your profile pic.

it means the authors are from Kuban

Not from Kuban, from Cuba.

that's the joke

Jokes used to be funny.

Apparently, his jokes are not and he got banned for it

That's not me lol

Found it finally

it proves nothing

Xi Ximpingpong playing #tennis with

## peng_shuai in #XINJIANG

.

.

Don't spam! A very similar comment has already been posted

After this contest, MikeMirzayanov should add new rating called tourist rating for people with 4000+ ratings

## China_communist_party_Zhang_gaoli_raped_peng_shuai

2021: Send

Monogon's contribution to the moon.2022: Send

tourist's rating to the moon.not Monogon, it's YouKn0wWho

ratio

## include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

## ifdef LOCAL

## define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

## else

## define dbg(...)

## endif

## define fast_io ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

## define ar array

## define ll long long

## define ld long double

## define sza(x) ((int)x.size())

## define all(a) (a).begin(), (a).end()

## define fr(i,a,b) for(int i=a;i<b;i++)

## define vi vector

## define vii vector

## define vll vector

## define vpii vector<pair<int,int>>

## define nline endl

void printArr(int arr[],int n){fr(i,0,n)cout<<arr[i]<<" ";} void printVec(vector &v , int n){fr(i,0,n)cout<<v[i]<<" ";}

const int MAX_N = 1e5 + 5; const ll MOD = 1e9 + 7; const ll INF = 1e9; const ld EPS = 1e-9;

vector primes, spf, mobius, phi; vector is_prime;

void sieve(int n) { primes.clear(); is_prime.assign(n + 1, 1); spf.assign(n + 1, 0); mobius.assign(n + 1, 0); phi.assign(n + 1, 0); is_prime[0] = is_prime[1] = 0; mobius[1] = phi[1] = 1; for (ll i = 2; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); spf[i] = i; mobius[i] = -1; phi[i] = i — 1; } for (auto p : primes) { if (i * p > n || p > spf[i]) break; is_prime[i * p] = 0; spf[i * p] = p; mobius[i * p] = (spf[i] == p) ? 0 : -mobius[i]; phi[i * p] = (spf[i] == p) ? phi[i] * p : phi[i] * phi[p]; } } } void solve(){ int n,m; cin>>n>>m; vector a(n); vector<vector> s(n,vector (m)); fr(i,0,n){ fr(j,0,m){ cin>>s[i][j]; } } fr(i,0,m){ cin>>a[i]; } ll ans = 0; fr(j,0,m){ vector v(27,0); fr(i,0,n){ v[s[i][j]-65]++; } int mx = v[0]; // cout<<mx<<endl; fr(i,1,27){ mx=max(v[i],mx); } ans =ans + mx*a[j]; } cout<<ans<<nline; } int main() { fast_io; int tc = 1; for (int t = 1; t <= tc; t++) { solve(); } return 0; }

//What wrong in this why i got runtime error testcase 24 question link https://codeforces.com/problemset/problem/1201/A

"Probably, the solution is executed with error 'out of bounds' on the line 74".thanks for instruction and i am sorry i will not do it agains :)

Don't forget that Adonis is a gentleman, he reads, meditates and works out daily, doesn't waste precious time in gaming or social media, doesn't fap, stays on his diet, works hard for his goals, respects women and his parents, and doesn't settle for weakness. Be like Adonis my friends, be the best version of yourself you can be.

Who is Adonis?

Adonis is inside all of us. We just have to work hard enough to reveal him within

jesus christ . what the fuck man

Come on man, stop promoting your youtube channel here.

I am so excited to see someone who's rating is more than 4000.

No...

By looking at the score distribution it seems like it will gonna be a very balanced round.

what the important topics at this Div ??

When you participate in Codeforces rounds you must prepare yourself for anything because there are a lot of creative minds of who will set the problems in the contest on this round and another rounds, good luck .

Good luck for everybody!!!

If I solve two problems, I will get 1000 point?

No. The score assigned to each problem is the score that you will gain if you solved this problem during contest, not the delta that you will gain after the contest.

ok,thank you

I hope everyone will get positive

delta.For the comments, I would recommend being nice, tolerant, and thinking carefully before downvoting any comments. In particular, "already having many downvotes" shouldn't be the reason to downvote a comment.

Me tested, me want contribution :eyes:

I just started codeforces and currently I am in division 3(newbie). Should I participate in division 2 contests. Thanks in advance for suggesting.

Yes, Participate in as many contests as possible.

Since you are New I have 2 suggestions:

1) Initially participate for learning not for rating cause ultimately you have nothing to lose.

2) Enjoy the contest.

That's what was going through my mind but just wanted to know others suggestion. Thanks

I want to see the 4000 rating but don't know why I have a feeling that we have to wait more..

Good luck for all contestant

my new yr resolution to be less on shit codeforces an more on pornhub going strong

Is it rated for me who has a rating of ~1550? Division shows I am in div3.

Yes

How is rating change calculated for each contest? Is it like total sum of rating changes is zero? If it is, then what would happen when everyone performs well?

How would you explain a scenario where everyone performs well.

Yeah its a hypothetical situation ! Since performance is relative

How would you explain this scenario even in a hypothetical situation?

Thats what my point is !

Okay let's assume everyone is rank 1 than Grandmaster is performing same as a Newbie which contradict with rank itself!!

I guess I am just having a bad day :(

Contest went bad to me with 2 WA on A making my Brain Dead.

but Nice contest and I must say the contest till now went very smooth with No lag appreciatable.

Hello guys i have a task for you. if someone can hack umnik's any solution .. i will personally give him 500$ :)

I bet <0.001% can even understand um-nik's solution

Send button doesnt work in "ask a question" tab ? Anyone else have same problem ?

Does anyone else suspect there might be something wrong with pretests 2+ for Problem C Div.2? Can't wait to see full test output.

i thought the same for a while and then realized my foolishness. in my case, i was considering, k == n — 1 as a -1 condition which is completely inaccurate.

Yes, right. That was exactly my mistake as well.

I hoped tourist would have 4000 after this contest...

Yea Me too but still i have the hope:)

He got concerned if there's a Y2K-like issue with CF rating database.

All of a sudden a storm starts going over Div2 D. Look at the colors of majorities and their submission time.

The one with almost same memory and time are suspicious

I cannot stress upon how much I hated problem C. It really made me wonder what's the point of all the practice when all of it boils down to staring at binary numbers and figuring out an edge case.

UPD: I was too salty during the contest to try D. Now I upsolved it, and was a super nice problem for me.

Honestly, I thought it was a really cool problem till I got WA on test 2. The edge case for n>4 & k= n-1 is freaking disgusting (maybe an example testcase would solve this..). I was sure about the correctness of my solution (at least for the rest of it...) and for the whole contest, I was trying to figure out what was wrong. I am really disappointed that the overall contest performance gets blown by such crap.

I was saved by my bruteforce solution =) For some reason I decided to look at all permutations of $$${0, 1, .., 7}$$$ and look what kind of sums we can get and found out that we can get all of $$${0, 1, .., 7}$$$ =)

I was reading the problem over and over again thinking that i must have overlooked something in the problem statement.

i can understand the pain

I bruteforce it and found the case when k == n-1, Maybe you havent bruteforce the solution . I wrote dfs which gave the correct answer for the case k = n-1.

Yes problem C ruined my day :(.

I figured out that edge case quickly, yet i was too late because i spent half an hour trying to fix a tiny bug in B.It would be sad if that was the only reason of my WA in C..

edit: my code got WA because of that case and I also had a typo in the code anyway :D

I hate every constructive problem.

Thanks to problem C, at least I know what type of problem I hate the most :

The one that has tricky cases

Any hints for D? I think I can greedily check if I can get an answer with a given interval, but no idea how to find a good interval.

If every subarray needs to have strictly more in range than out of range, then the entire array needs to have at least k more in range than out of range. Finding the range requires constructing a copy of the array and then sorting, and then minimizing arr[i+dist]-arr[i]. Constructing is then a linear scan waiting for the moment in range > out of range, except for the last one being the rest of the array.

My thoughts were: for a fixed interval $$$[x, y]$$$ denote all the numbers that are in this interval by $$$1$$$ and all the others by $$$-1$$$. Then you should be able to find partition where all the segments have their sum > 0. If you compute array of prefix sums then you should check if its longest increasing subsequence starting with $$$0-$$$th number and ending in $$$n$$$-th number is at least $$$k + 1$$$. You can binsearch on $$$y - x$$$ and iterate over $$$x$$$ somehow manipulating on longest increasing subsequence but I didn't figured out how.

Edit: saw solution above, my is overkill

Hint 1If you need $$$k$$$ subarrays, what is the minimum number of good elements you need?

AnswerAt least 1 more good element than bad per subarray, so we want the min $$$x$$$ such that $$$x \geq (n - x) + k$$$, or simplifying, $$$x = \lceil\frac{n + k}{2}\rceil$$$

Hint 2How can we find the minimum $$$y$$$ for a given $$$x$$$ such that there are at least $$$\lceil\frac{n + k}{2}\rceil$$$ good elements in $$$[x, y]$$$?

AnswerStore a count of how many times each $$$a_i$$$ appears, now just two pointer / binary search on this array to find the smallest range.

Hint 3How can we guarantee we can always generate ranges for this?

AnswerWe initially have $$$k$$$ more good elements than bad elements.

Greedily remove the range $$$[1, i]$$$ for the smallest $$$i$$$ that has strictly more elements in the range. Notice that good_elements = bad_elements + 1 in this case. So we have $$$k - 1$$$ more good elements than bad elements after this.

Since we have only used $$$1$$$ of the extra good elements to make $$$1$$$ subarray, we can just repeat this process for the remaining $$$k - 1$$$ subarrays.

Aren't we supposed to take continuous elements from a. Your solution assumes that we can take any element from any position and create subarrays. example your solution allows keeping index 1 element in a right before index 5 element in one of the subarray. Was this allowed ? I thought we had to take continuous elements of a as subarrays. Was I wrong ?

Love the problems

To be honest, it was a really bad contest :(

And why do you think so?

Oops...

So what, difficulty gradient seems fine. At least for A,B,C,D

For you

About problem E: I don't think that's the right way to fix it, what if the numerator and denominator are both divisible by P?

I would fix it by saying that you can assume that the number of permutations is not a multiple of P.

Fixed, we are very sorry for all the issues with that

Okay, am I missing something in A? Because I think that BCDE took me less thinking time in total than A alone, I'm not kidding (not talking about implementing time)

I think you overkilled it, you can pair i and (n — 1) xor i, to create anything less than n — 1, you can create pairs (k, n — 1), (0, k xor (n — 1)), for n — 1 it's same but create 1 and n — 2.

Thank you!

Number of people envying Len for seizing the chance to advise an LGM: 7949999998 and counting...

`x & ~x = 0`

so you can pair $$$n-1$$$ with $$$k$$$, $$$0$$$ with $$$\sim k$$$, and $$$x$$$ with $$$\sim x$$$ for other $$$x$$$s. The only tricky part is that despite what the example suggests the answer always exists when $$$n>4$$$ and the above construction only works when $$$k<n-1$$$ so another one is needed (it's also simple. The case analysis seems unavoidable).At first I tried to find the way how to get sum == 0. And it is clear to see that we can match every number to it's inverted partner (a goes with b, where a == ), so in every pair (a^b) = (n-1) is true.

Then I tried to find a way to get value k with only 1 swap. If we match some value with 0, we always get 0. If we match x with n-1, we always get x. So let's take a pair (k, ) and match k with n-1, and with 0. Every other pair is still valid, and the answer is k.

We cannot do that when k == n-1, so for n == 4 the answer is -1.

But when n is 8 or more, there is always a way to make sum equal to k. I thought that we should divide "adding k" into 2 parts. I decided to add k-1, and 1 seperately. So I had to add pairs. {1, 3} — adds 1 {n-1, n-2} — adds n-2 {0, n-3} — adds 0 {2, n-4} — adds 0 so we used first 4 and last 4 values, and every pair can be matched in a usual way.

any hint for div1 B, I have no idea even after spending 1 hr.

Hint: you don't need to check if a certain interval $$$[x, y]$$$ is valid for subarrays individually, but you can check for the entire array directly.

Hint : If you have ceil((n+k)/2) elements in the range, you can create such k partitions satisfying the condition. After this idea, it's just binary search for finding the range and then partitioning into subarrays.

R.I.P. the 4k dream.

I was looking forward to it! So sad now :(

Eco-Friendly memeHow to solve div2D.

I don't have any idea how to solve it (Other than trivial cases of k=1 and k=n)

Submitted the solution 12 secs before, still no judgment?

This distribution was quite weird. My times:

D (2000) — 8 mins

B (1250) — 10 mins

C (1250) — 16 mins

A (500) — 16 mins

I think D is easier than A. The trick in D is too obvious (at least for me).

can anyone tell me what is my mistake in div2 ques b https://codeforces.com/contest/1631/submission/144241818

Kinda speedforces but E was nice.

Also B, I like that possible number of splits can be easily proved to be independent on order, which gets rid of a whole lot of ugliness.

RESOLVED.

I don't know much C++, but the most common mistake that I know of is forgetting that after you perform the operation, elements right after the ones you just changed might already be equal to the target. Checking this condition requires a while loop.

I got it now , it fails for cases like : 6 1 2 6 6 6 6

My code would output 0, whereas the answer should be 1. Thank you for looking in to.

What is pretest 2 for div. 2 "C"? I already tested all I could and can't figure out what is my error.

It was "n 0".

EDIT: I guess it was "n 0" "n n-1".

your code fails for

1

8 7

as there is a possible answer

7 6

1 5

0 2

3 4

How to solve Div 1D? I have a feeling I am missing some important observation.

If we can invert a range $$$a$$$ and a range $$$b$$$, then we can invert any range $$$a-b$$$ (works thanks to $$$a,b \le n/2$$$). That gives Euclid's modulo algorithm. We can invert any range $$$g = gcd(B)$$$.

It's easy to see that we can then invert any two elements whose distance is multiple of $$$g$$$. We get $$$g$$$ groups, in each group we can change the number of negative elements by $$$2$$$ so it can be forced to be $$$0$$$ or $$$1$$$.

The above uses an even number of operations so two cases arise depending on the parity of number of operations applied. The rest is simple implementation.

good job and a good round as well keep it going

For

`Div2`

`Problem C`

, can someone help me understand how to find the pairs, when`k==n-1`

?(I was able to find pairs for all other values of

`k`

)The example for n=65536, k=65535 would be (65535, 65534), (0, 1), (2, 65532), (3, 65533). The rest are just paired so that their sum is 65535.

if (k==n-1 and n!=4), the two pairs which will sum up to k will be (n,k-1) and (k-2,1) and for the rest of the pairs you have to make their & 0.

when n>4 and k==n-1 you can find it by simply (n-1)&(n-2) , 1&3 , 0&(n-1-3) and rest as i&(n-1-i). But if n==4 and k==n-1 it is impossible. Hope you get it;)

Hintn is always a power of 2.... then kin binaryis like (111,11111) -All bits are ON.-think how u can turn ON all these bits.SolutionI can take (n-1 & n-2) to turn all bits except the first one

to turn the first one I can take (1&3).

then I just want to make all other AND pairs = 0.

from 2 to n/2 take (i&(n-i-1)) except (0&(n-4))

codeIn problem E, with 30612 ones, 12124 twos, 2 threes, p is not zero but q is not (answer is p/q modulo 998244353) and I believe there's also possibility p and q are both zero modulo 998244353 but p/q is legal. Does the statement mean we don't need to consider these cases? I suppose it's better to state that in a more exact way.

Yes, statement says we can assume that such a case doesn't happen. There's nothing we can do if it does, after all — the expected number wouldn't be well-defined. It's always possible to switch to sum over all distinct permutations (or to floats), though.

let's check that if the validator consider this case...

Validator should reject it as an invalid input.

I liked 'any number of times' in each problem.

C Div2 was just to find the combination for k=n-1, rest was obvious.

I figured out the edge case for k=n-1 , but still get WA on pretest 2. I even checked myself for various cases like 16,0 16,15 and so on and was getting the right answer. If anyone can help figure out the problem I'd be grateful. My solution if(4,3) then -1, if(n,n-1) then pair (n-1,n-2)(all but 1 is missing now) 1,3(to add the 1) then 0,n-1^3 and rest i,i^n-1. But I'm still getting wa on pretest 2. Please help

code... ` ~~~~~ int main(){

} ~~~~~

`

you should assign 1 to n-3 rather than assigning it to 3 in case of k==n-1

Probably there is a way to combine these 3 cases as one, but I still think of them separately in my head.

k == 0k <= n - 2k == n - 1Can anyone explain to me the solution to Problem D?

Why does Div.2 Problem C stress that "All test cases in each individual input will be pairwise different"? The word "different" is even in boldface.

How to solve B?

My opinion: Div2 B problem statement could be more clear. Div2 C: looks like I was solving CodeChef question, not cf.

Am I the only one who initially thought for Div2 C, the answer is -1 for k=n-1, then after 2 WA's realized it is only for n=4?

PS. Div2 D was a nice question!

will you please share the approach of problem D?

Same after two WA :)

The procedure was to find x,y and then partition the array in k parts. 1. If x,y satisfies the constraints of the problem, then x,y+1 too, and if x,y don't satisfy the constraints, then x,y-1 also won't. This gives an idea to binary search on y. 2. So we iterate over x, binary search on y, and then we get our optimal x and y.

Notice that once we get our optimal x and y (call them ansx and ansy), the following relation will hold — no of elements outside [ansx, ansy] + k <= no of elements inside [ansx, ansy]

So to partition the array, following greedy strategy works — First partition array in k-1 parts so that count of excluded == count of included-1, then assign the remaining array as last partition. The last parition will also satisify the constraints of [ansx, ansy] because of the relation mentioned above.

Can div1F be solved like this:

-First thing to note is that it is enough to remove elements such that there isn't any cycle of odd length

-Now you can make DAG, if you have three indices x, y, z (a[x] > a[y] > a[z]) and a[x] % a[y] == 0, and a[y] % a[z] == 0 then it ofc a[x] % a[y] == 0, so you can just add edge from x -> y and y -> z

-Next thing you can see is that if you have depth >= 2 than there is odd length cycle in that directed tree (I called it DAG, because we will add one node as "root" so we can do dp)

-So you can do dp[node][do you remove it 0/1][depth in he's subtree]

-And if you add one new node to be root than you answer is min(dp[root][0][0], dp[root][0][1]) — 1 (-1 because that root is added in dp).

Is this ok?

tourist forgot to send solution to F.

FAbout the problems:

I didn't like D, E (even disregarding the issue about denominator). They feel like just a combination of some standard problems.

However, I thought F is really cool, maybe it will be a best problem of 2022. C was also interesting.

Sed, Tourist missed the best problem of 2022.

Or is it the best cause he didn't solve?

F is cool, but I mean, it is just a slight variation to the very well known problem of determining the biggest antichain in a poset. It is fine for a Codeforces round, but I personally would definitely not consider it among the best problems

I agree with the fact about F, it's one of the best problems I've seen so far.

I'm not sure how your solution exactly works, so it'd be great if you could explain the reduction to bipartite matching. (I noticed that you used bipartite matching since yours was one of the fastest solutions in contest).

My (out of contest) solution consists of noting that if the edges were directed, then you need to avoid paths of length 2 (it is necessary and sufficient to avoid an odd cycle). To do this, we can construct a network with 6 layers (first and last layers being the source and the sink), with $$$n$$$ vertices each in the remaining layers, and the edges between layers {1, 2}, {3, 4} and {5, 6} corresponding to vertices in the original graph, and edges between layers {2, 3} and {4, 5} corresponding to directed edges. Then using the vertex version of Menger's theorem we can see that the max flow in this network is the number of vertices we need to remove (since each path from source to sink passes through all the layers).

Hints for the third problem anyone? (Div 2C)

Data for $$$n = 8$$$

1216Idea generated by staring at this table: comment with idea

Implementation based on idea: 144175474

for k == 7 i constructed 4+3 i could not figured out how to make 6 + 1. :_:

my contribution is dead any help would greatly be appreciated and good job on this round

I figured out the edge case for k=n-1 , but still get WA on pretest 2. I even checked myself for various cases like 16,0 16,15 and so on and was getting the right answer. If anyone can help figure out the problem I'd be grateful. My solution if(4,3) then -1, if(n,n-1) then pair (n-1,n-2)(all but 1 is missing now) 1,3(to add the 1) then 0,n-1^3 and rest i,i^n-1. But I'm still getting wa on pretest 2. Please help

code... ` ~~~~~ int main(){

} ~~~~~

`

I think it should be cout<<-1<<endl; not cout<<-1;

Oh my god I want to die

Bruh I think the luck was not with you today . Imagine knowing the logic and still getting Wa

Knew the concept of C, could not figure out the edge case :( sol

what is the edge case

look down

It is cheating.

I looked carefully at the submissions. These are literally the same implementation if you remove all of the unnecessary variables being defined. There are hundreds of (fake) users with that same implementation.

The whole time I was thinking that k can be any positive integer in div2 C TwT

D was really cool problem!!

can you please give some hints for D

HintBinary Search on j-i

Can anyone share the solution for problem C ( Div 2) along with the observation? Thanks!

For K = 0, just pair each value with its complement.

For any other K other that is not N — 1, we can just pick N — 1 and K as pairs, and eliminate any other number by pairing it with its complement (every J will be paired with N — 1 — J). Since we don't need to eliminate N — 1, we pair the "unused" zero to the complement of K to eliminate it as well.

For K = N — 1, we could pair N — 1 with N — 2 to obtain N — 2. Now we just need to add 1. Knowing that N — 1 is odd, N — 3 is odd as well, which means its least significant bit is turned on. Therefore, we can pair 1 with N — 3 to obtain 1. What's left is to eliminate any other number with its complement (or by making usage of the "free" zero).

Possibly there is a more generalized approach, but this was my thought process. Hope it helps ^^

1st observation is x&(n-1) is always x. 2nd is if u want k to be 0 , you can pair all x,y such that x is the complement of y. if k is non zero & != n-1 then pair all elements with their compliments except k. k can be paired with n-1(k&(n-1) = k) and k compliment can be paired with 0.

if k is n-1 then make n-2 with above algorithm and we need 1 more, so pair 1 with any odd number and pair the compliment of the odd number with 0. the answer is -1 only when n = 4 , k = 3

How to solve D div1. Pls give me some ideas

Since the system testing is not completed and I am not able to submit my solution, can someone tell me whether this is the correct solution for E?

SpoilerI am astonishing now about a large amount of NEW accounts were suspected for cheating today in div2.Really Sad to see that.

I just got C, Wow the way to generate an extra 1 by using the previous bit is amazing,

`n = 32 and k = 31 then n/2 = 16`

Generate 1 using

`4 bits or 16 so 15 1, 0 16, 30 31`

15 and 1 generates 1 and 16 0 generates 0 and finally 31 30 generates 30 totaling to 31"Just Wow

Their are other ways too . I generated all pairs And zero except one. But your solution is clever tbh

First 5 problems: 4 ad-hoc and one pure combinatorics counting problem, 0 algorithmic problems, 0 data structure problems. Rounds like this with only math problems make me want to quit competitive programming.

When can we start system testing?

There are no hacks so we'd like to know what is the excuse for not starting system test 1 hour after the contest ends. Is putting up an announcement in such scenario too much to ask for?

I just want to submit my code...

When will system testing start? It's been almost an hour after the contest had ended. Or is there a discussion going on about the denominator-mod-998244353 issue in Div. 1 E?

Update: System testing started.

There was an issue with a non deterministic generator in D1D (do not worry, the bad case was not present in pretests and it will not be present in system tests. Sorry for the delay.

I wasted 27 minutes on a "Wrong answer" of Div.2 Problem C, just because I didn't realize that 11...1100 is actually (2^b-4) not (2^b-3). Such small errors can ruin one's rank in a contest.

Anyone else who waste a lot of time in Div2C (Div 1A) trying to find out the case k>=n ?

I waste almost an hour on it, and feel very strange why so many people get accepted, am I too dumb? Then I see the constraint, damn it !

I did same. Except I saw the constraint after contest ended.

But managed to solve anyway. https://codeforces.com/contest/1631/submission/144245114

Yeah but i figured it out soon.

So many cheaters whose name like this amboss[0-9]; They just replace the variants with some hashcode or wrap the code by "if(1==1) code;"

These will never stop cheating . They ruining our fun of problem solving

https://codeforces.com/contest/1631/submission/144245114

This happen when you don't read constraint carefully.

I wish I read 0<=k<=n-1 . It would have saved lot of time for me.

Points not updated yet?

or is this unranked?

what about dark mode in codeforces?

Can someone please tell what i did wrong here in Div2 B? This is my code :-

CodeYou're only assuming that the last sub-array could be the same, but some times there will be a number in the middle that can help you:

For example the test case :

1 1 1 2 1 2 2 2 1 2In this example your first cnt will happen after it spots the 1, but then you only reach the fourth-from-last 2 and don't use the 5th one, leading to your answer being 3 instead of 2.

fix this by checking for last index of arr where arr[curr] == arr[n], and make your starting i = curr — 1.

add this at the start of your while loop and it should work:

Thanks man! I got AC.

On a particular note, I copied your code and added the lines to make sure it worked before I helped you with the solution. I'm not familiar with the rules here so is that okay or could it cause trouble?

I had already solved it in the competition though.

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

Have the ratings been updated? :D

which test case in DIV2 Problem B causing wrong answer on test case 3 for many submission? can someone figure out that test case!.

You're only assuming that the last sub-array could be the same, but some times there will be a number in the middle that can help you:

For example the test case :

1 1 1 2 1 2 2 2 1 2

In this example your first cnt will happen after it spots the 1, but then you only reach the fourth-from-last 2 and don't use the 5th one, leading to your answer being 3 instead of 2.

https://codeforces.com/blog/entry/99299?#comment-881544

Check this comment

i got fst in div1C... I forgot to reset the left bound

https://codeforces.ml/contest/1631/submission/144275630 I don't know how to correct this code.(Div2 B)

Hey, It's just a silly mistake, although LL should be "long long" rather than "unsigned long long." Otherwise, the "mi" variable won't consider negative values. You should have debugged your code carefully. Although, you have written a perfect algorithm. Don't be regretful. Instead, strive to better yourself. All the best.

Oh!Thanks a lot.I have been confused about it for a long time.I did't notice the "unsigned long long".How stupid I am.All the best for you too.

Thank you, everyone, for arranging a great contest.

Anyone knows why did that user get better rating than me? yqjqygg

Probably because that is one of their first 6 contests

You are right, thanks

can somebody help me with the solution of problem A. Min Max swap. i got a runtime error on pretest #2. my code was:

I'm Not familiar with python. But store max_value into long long data type. long max_value = (long)(max(a))*long(max(b));

If you haven't found the problem yet you're reading the input as string, together with spaces. Use "list(map(int, input().split()))".

no it didn't work. the input of the pretest#2 is:

in my opinion which is not in line with the question as it has to provide us with 2 list of same length, and in this test only 1 list is provided. any thoughts?

It's a very long test case, codeforces don't show all.

Here is my solution with same approach: link

Thank you, that helps.

D1D spoilerI really loved this problem! I think the observation that $$$B$$$ can be reduced to a single element is quite trivial, but the parity in the remaining part was super satisfying to think of

I did pretty badly in the round as usual, but I enjoyed the problems (A-D) nonetheless :D

First of all, I would like to thank codeforces for arranging the contest. The codeforces site got block from my side due to some issues in the server. I got a little panic and used the idedone website to run my code and check weather it is working or not. I was in such a hurry that I forgot to change the setting from public to private. I'm so sorry for this. But I've not cheated. Please consider my points and believe me. Thank you