humbertoyusta's blog

By humbertoyusta, history, 4 months ago,

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:

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:

• +347

 » 4 months ago, # |   +117 As a tester, I tested… GL&HF
• »
»
4 months ago, # ^ |
-35

Xi Ximpingpong playing tennis with peng shuai in XINJIANG.

whereispengshuai

•  » » 4 months ago, # ^ |   -60 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.
•  » » » 4 months ago, # ^ |   0 You're asking coders to work out and meditate lol...
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +25 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.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 Of course you should keep coding but at the same time take care of yourself. Your future self will not regret it.
•  » » 4 months ago, # ^ |   +41 Meme!
 » 4 months ago, # | ← Rev. 2 →   +16 One of the first Cuban rounds!!!!!!!!!!! humbertoyusta, BrayanD, dmga44, albertolg101, jmrh_1, marcOS, MDario, aniervs, Saborit OTZ
•  » » 4 months ago, # ^ | ← Rev. 2 →   +46 Actually, it's the second or third already.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -36 Oh I see, fixed.
•  » » 4 months ago, # ^ |   +83 Don't forget Codeforces Round #659 (Div. 1)
•  » » » 4 months ago, # ^ |   +44 unforgettable
•  » » » 4 months ago, # ^ |   0 I am still drowning inorder to help koa in div2 of this contest
•  » » » 4 months ago, # ^ |   0 This contest is hell tough for beginners like me
 » 4 months ago, # |   +72 Probably the round where we see our first 4000+. GL tourist :')Don't wanna jinx it
•  » » 4 months ago, # ^ |   +22 Another division should be created for this single person
•  » » » 4 months ago, # ^ |   -17 He'll reach infinity rating pretty quickly then
•  » » 4 months ago, # ^ |   +10 And what about that?
•  » » » 4 months ago, # ^ |   +7 jejeje (aniervs flashbacks)
•  » » 4 months ago, # ^ |   -7 I read about him on the wikipedia, he used to spent no more than 4 hours on his computer, Unbelievable...
•  » » 4 months ago, # ^ |   +2 Um_nik wins.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +5 not happening now. You did jinxed it.
•  » » 4 months ago, # ^ |   +2 jinxed...
 » 4 months ago, # |   +6 Congratulations guys, nice job!
 » 4 months ago, # |   +25 During testing I really enjoyed solving problems of the round and I hope participants will enjoy as much as I did.
 » 4 months ago, # |   +42 Why no IGM/LGM testers?
•  » » 4 months ago, # ^ |   +320 they have to participate to help tourist cross 4000 rating
 » 4 months ago, # |   +12 Quite excited to participate in this round!
 » 4 months ago, # |   +10 I'm happy to see a cuban round again ! I remember that I really enjoyed the first cuban round I did :D
 » 4 months ago, # | ← Rev. 2 →   -21 Can anyone explain what does "cuban round" mean ? ,Thanks in advance .
•  » » 4 months ago, # ^ |   +56 It means that the authors are from Cuba.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 I am sorry for previous comment.
•  » » » » 4 months ago, # ^ |   +15 It is a normal codeforces round, hope you enjoy the contest.
•  » » » » » 4 months ago, # ^ |   +23 Thanks ^_^
•  » » » » » » 4 months ago, # ^ |   +33 Why did you downvote my comments ?
•  » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +1 You have asked stupid and googleable question
•  » » » » » » » » 4 months ago, # ^ |   -38 He isn't stupid but your mother is stupid
•  » » » » » » » » » 4 months ago, # ^ |   +65 Please don't say like this, you must be respectful
•  » » » » » » » » 4 months ago, # ^ |   +19 I said thanks and they downvote it bro
•  » » » » » » » » » 4 months ago, # ^ |   +101 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.
•  » » » » » » » » » 4 months ago, # ^ |   +13 Thank you very much for explaination.
•  » » » » » » » » » 4 months ago, # ^ | ← Rev. 4 →   -18 That was a legitimate question. There is no such word as "cuban" (uncapitalized).
•  » » » » » » » 4 months ago, # ^ |   +82 Meme:
•  » » » » 4 months ago, # ^ |   +60 Actually, they were going to give shorts to the winners instead of T-shirts, but now you spoiled it.
•  » » » » » 4 months ago, # ^ |   +31 Could you please give pants instead? So rare nowadays… (∩︵∩)
•  » » » » » » 4 months ago, # ^ |   0 But then again, can we really tell if they are pants or not? Rather like the gender of your profile pic.
•  » » 4 months ago, # ^ |   -27 it means the authors are from Kuban
•  » » » 4 months ago, # ^ |   +17 Not from Kuban, from Cuba.
•  » » » » 4 months ago, # ^ |   -26 that's the joke
•  » » » » » 4 months ago, # ^ |   +93 Jokes used to be funny.
•  » » » » » » 4 months ago, # ^ |   0 Apparently, his jokes are not and he got banned for it
•  » » » » » » » 4 months ago, # ^ |   -22 That's not me lol
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0
•  » » » » » » » » » 4 months ago, # ^ |   -30 it proves nothing
»
4 months ago, # |
-30

Xi Ximpingpong playing #tennis with

peng_shuai in #XINJIANG

 » 4 months ago, # | ← Rev. 4 →   -24 .
•  » » 4 months ago, # ^ | ← Rev. 2 →   -8 .
•  » » » 4 months ago, # ^ |   +9 Don't spam! A very similar comment has already been posted
 » 4 months ago, # |   +39 After this contest, MikeMirzayanov should add new rating called tourist rating for people with 4000+ ratings
»
4 months ago, # |
-45

China_communist_party_Zhang_gaoli_raped_peng_shuai

 » 4 months ago, # |   +26 2021: Send Monogon's contribution to the moon. 2022: Send tourist's rating to the moon.
•  » » 4 months ago, # ^ |   -39 not Monogon, it's YouKn0wWho
•  » » » 4 months ago, # ^ |   0 ratio
»
4 months ago, # |
-230

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

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

•  » » 4 months ago, # ^ |   +122 Don't copy paste code directly into comments. No one has the patience to try and understand unformatted code. It's also a nuisance to all those reading other comments on the blog since it takes up so much space. Use a code block and if it takes up more than a few lines, use a spoiler tag (there are options for them when you comment). If it is an entire submission, just provide the link (143943751). This is the announcement blog for an upcoming round, so this is not the place to be posting this. At least make an effort to solve your problem yourself. If you look at your sumbmission, the verdict says RTE on test 24. The first line even says "Probably, the solution is executed with error 'out of bounds' on the line 74". If you're asking for a favour, maybe it would be better to give readers some context (ask your question) prior to dumping a huge block of code in their face. And here you go: 143948025.
•  » » » 4 months ago, # ^ |   +49 thanks for instruction and i am sorry i will not do it agains :)
 » 4 months ago, # | ← Rev. 4 →   -115 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.
•  » » 4 months ago, # ^ |   +17 Who is Adonis?
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -24 Adonis is inside all of us. We just have to work hard enough to reveal him within
•  » » » » 4 months ago, # ^ |   0 jesus christ . what the fuck man
•  » » » » 4 months ago, # ^ |   0 Come on man, stop promoting your youtube channel here.
 » 4 months ago, # |   +28 I am so excited to see someone who's rating is more than 4000.
•  » » 4 months ago, # ^ |   0 No...
 » 4 months ago, # |   -37 By looking at the score distribution it seems like it will gonna be a very balanced round.
 » 4 months ago, # |   0 what the important topics at this Div ??
•  » » 4 months ago, # ^ |   0 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 .
 » 4 months ago, # |   +8 Good luck for everybody!!!
 » 4 months ago, # |   -15 If I solve two problems, I will get 1000 point?
•  » » 4 months ago, # ^ |   +2 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.
•  » » » 4 months ago, # ^ |   +1 ok,thank you
 » 4 months ago, # |   -17 I hope everyone will get positive delta.
 » 4 months ago, # | ← Rev. 2 →   +1 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.
 » 4 months ago, # |   +34 Me tested, me want contribution :eyes:
 » 4 months ago, # |   0 I just started codeforces and currently I am in division 3(newbie). Should I participate in division 2 contests. Thanks in advance for suggesting.
•  » » 4 months ago, # ^ |   +1 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.
•  » » » 4 months ago, # ^ |   +1 That's what was going through my mind but just wanted to know others suggestion. Thanks
 » 4 months ago, # |   -6 I want to see the 4000 rating but don't know why I have a feeling that we have to wait more..
 » 4 months ago, # |   0 Good luck for all contestant
 » 4 months ago, # |   0 my new yr resolution to be less on shit codeforces an more on pornhub going strong
 » 4 months ago, # |   0 Is it rated for me who has a rating of ~1550? Division shows I am in div3.
•  » » 4 months ago, # ^ |   0 Yes
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   0 How would you explain a scenario where everyone performs well.
•  » » » 4 months ago, # ^ |   0 Yeah its a hypothetical situation ! Since performance is relative
•  » » » » 4 months ago, # ^ |   +6 How would you explain this scenario even in a hypothetical situation?
•  » » » » » 4 months ago, # ^ |   0 Thats what my point is !
•  » » » » 4 months ago, # ^ |   +5 Okay let's assume everyone is rank 1 than Grandmaster is performing same as a Newbie which contradict with rank itself!!
 » 4 months ago, # |   +6 I guess I am just having a bad day :(
 » 4 months ago, # |   +1 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.
 » 4 months ago, # |   +5 Hello guys i have a task for you. if someone can hack umnik's any solution .. i will personally give him 500$:) •  » » 4 months ago, # ^ | -8 I bet <0.001% can even understand um-nik's solution  » 4 months ago, # | +1 Send button doesnt work in "ask a question" tab ? Anyone else have same problem ?  » 4 months ago, # | 0 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. •  » » 4 months ago, # ^ | 0 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. •  » » » 4 months ago, # ^ | 0 Yes, right. That was exactly my mistake as well.  » 4 months ago, # | +7 I hoped tourist would have 4000 after this contest... •  » » 4 months ago, # ^ | 0 Yea Me too but still i have the hope:) •  » » 4 months ago, # ^ | 0 He got concerned if there's a Y2K-like issue with CF rating database.  » 4 months ago, # | ← Rev. 4 → +59 All of a sudden a storm starts going over Div2 D. Look at the colors of majorities and their submission time. •  » » 4 months ago, # ^ | +3 The one with almost same memory and time are suspicious  » 4 months ago, # | ← Rev. 2 → +42 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. •  » » 4 months ago, # ^ | +13 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. •  » » » 4 months ago, # ^ | +6 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}$ =) •  » » » 4 months ago, # ^ | +2 I was reading the problem over and over again thinking that i must have overlooked something in the problem statement. •  » » » 4 months ago, # ^ | +1 i can understand the pain •  » » » 4 months ago, # ^ | 0 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. •  » » 4 months ago, # ^ | +14 Yes problem C ruined my day :(. •  » » 4 months ago, # ^ | ← Rev. 2 → +1 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 •  » » 4 months ago, # ^ | 0 I hate every constructive problem. •  » » 4 months ago, # ^ | 0 Thanks to problem C, at least I know what type of problem I hate the most :The one that has tricky cases  » 4 months ago, # | +5 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. •  » » 4 months ago, # ^ | ← Rev. 2 → +4 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. •  » » 4 months ago, # ^ | ← Rev. 2 → +5 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 •  » » 4 months ago, # ^ | ← Rev. 3 → +29 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. •  » » » 4 months ago, # ^ | 0 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 ?  » 4 months ago, # | -14 Love the problems  » 4 months ago, # | -36 To be honest, it was a really bad contest :( •  » » 4 months ago, # ^ | 0 And why do you think so? •  » » » 4 months ago, # ^ | -42 Oops... •  » » » » 4 months ago, # ^ | 0 So what, difficulty gradient seems fine. At least for A,B,C,D •  » » 4 months ago, # ^ | 0 For you  » 4 months ago, # | +107 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. •  » » 4 months ago, # ^ | ← Rev. 2 → 0 Fixed, we are very sorry for all the issues with that  » 4 months ago, # | +42 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) •  » » 4 months ago, # ^ | ← Rev. 2 → +6 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. •  » » » 4 months ago, # ^ | +6 Thank you! •  » » » 4 months ago, # ^ | +32 Number of people envying Len for seizing the chance to advise an LGM: 7949999998 and counting... •  » » 4 months ago, # ^ | 0 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 •  » » 4 months ago, # ^ | +2 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.  » 4 months ago, # | +16 any hint for div1 B, I have no idea even after spending 1 hr. •  » » 4 months ago, # ^ | 0 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. •  » » 4 months ago, # ^ | +11 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.  » 4 months ago, # | +46 R.I.P. the 4k dream. •  » » 4 months ago, # ^ | +12 I was looking forward to it! So sad now :( •  » » 4 months ago, # ^ | +5 Eco-Friendly meme  » 4 months ago, # | +3 How to solve div2D.I don't have any idea how to solve it (Other than trivial cases of k=1 and k=n)  » 4 months ago, # | 0 Submitted the solution 12 secs before, still no judgment?  » 4 months ago, # | +73 This distribution was quite weird. My times: D (2000) — 8 mins B (1250) — 10 mins C (1250) — 16 mins A (500) — 16 mins •  » » 4 months ago, # ^ | -18 I think D is easier than A. The trick in D is too obvious (at least for me).  » 4 months ago, # | 0 can anyone tell me what is my mistake in div2 ques b https://codeforces.com/contest/1631/submission/144241818  » 4 months ago, # | ← Rev. 3 → -8 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.  » 4 months ago, # | ← Rev. 2 → -15 RESOLVED. •  » » 4 months ago, # ^ | ← Rev. 2 → 0 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. •  » » » 4 months ago, # ^ | 0 I got it now , it fails for cases like : 6 1 2 6 6 6 6My code would output 0, whereas the answer should be 1. Thank you for looking in to.  » 4 months ago, # | 0 What is pretest 2 for div. 2 "C"? I already tested all I could and can't figure out what is my error. •  » » 4 months ago, # ^ | ← Rev. 2 → 0 It was "n 0".EDIT: I guess it was "n 0" "n n-1". •  » » 4 months ago, # ^ | +3 your code fails for 18 7as there is a possible answer 7 61 50 23 4  » 4 months ago, # | +6 How to solve Div 1D? I have a feeling I am missing some important observation. •  » » 4 months ago, # ^ | +8 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.  » 4 months ago, # | 0 good job and a good round as well keep it going  » 4 months ago, # | 0 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) •  » » 4 months ago, # ^ | 0 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. •  » » 4 months ago, # ^ | 0 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. •  » » 4 months ago, # ^ | 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;) •  » » 4 months ago, # ^ | +1 Hintn is always a power of 2 .... then k in binary is 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)) code if (n == 4) { cout << -1 << '\n'; }else { cout << n - 2 << " " << n - 1 << "\n"; cout << "1 3\n" << n - 4 << "0\n"; for (int i = 2; i < n / 2; i++) if (i != 3) cout << i << " " << (n - i - 1) << "\n"; }   » 4 months ago, # | +116 In 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. •  » » 4 months ago, # ^ | -10 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. •  » » » 4 months ago, # ^ | +18 let's check that if the validator consider this case... •  » » » » 4 months ago, # ^ | +3 Validator should reject it as an invalid input.  » 4 months ago, # | 0 I liked 'any number of times' in each problem.  » 4 months ago, # | 0 C Div2 was just to find the combination for k=n-1, rest was obvious. •  » » 4 months ago, # ^ | 0 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(){ int q; cin>>q; while(q--){ inte n; cin>>n; inte k; cin>>k; n--; if(n+1==2){ if(k==0) { cout<<0<<" "<<1< •  » » » 4 months ago, # ^ | ← Rev. 2 → 0 you should assign 1 to n-3 rather than assigning it to 3 in case of k==n-1 •  » » » 4 months ago, # ^ | +10 Probably there is a way to combine these 3 cases as one, but I still think of them separately in my head. k == 0for (int l = 0, r = n - 1; l < r; l++, r--) cout << l << ' ' << r << '\n';  k <= n - 2cout << 0 << ' ' << n - k - 1 << '\n'; cout << k << ' ' << n - 1 << '\n'; for (int l = 1, r = n - 2; l < r; l++, r--) { if (l == k || l == n - k - 1) continue; cout << l << ' ' << r << '\n'; }  k == n - 1cout << 0 << ' ' << 2 << '\n'; // 0 cout << 1 << ' ' << n - 3 << '\n'; // 1 cout << n - 2 << ' ' << n - 1 << '\n'; // n - 2 for (int l = 3, r = n - 4; l < r; l++, r--) cout << l << ' ' << r << '\n';   » 4 months ago, # | 0 Can anyone explain to me the solution to Problem D?  » 4 months ago, # | 0 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.  » 4 months ago, # | 0 How to solve B?  » 4 months ago, # | -7 My opinion: Div2 B problem statement could be more clear. Div2 C: looks like I was solving CodeChef question, not cf.  » 4 months ago, # | ← Rev. 3 → +12 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! •  » » 4 months ago, # ^ | 0 will you please share the approach of problem D? •  » » 4 months ago, # ^ | 0 Same after two WA :) •  » » 4 months ago, # ^ | 0 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.  » 4 months ago, # | ← Rev. 4 → +3 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?  » 4 months ago, # | +18 tourist forgot to send solution to F. F  » 4 months ago, # | +47 About 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. •  » » 4 months ago, # ^ | 0 Sed, Tourist missed the best problem of 2022.Or is it the best cause he didn't solve? •  » » 4 months ago, # ^ | +1 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 •  » » 4 months ago, # ^ | +16 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).  » 4 months ago, # | 0 Hints for the third problem anyone? (Div 2C) • » » 4 months ago, # ^ | Rev. 5 +3 Data for$n = 8$k = 0 k = 1 k = 2 ... k = 7$000_2$&$111_2 = 0000_2$&$110_2 = 0000_2$&$101_2 = 0$...$000_2$&$010_2 = 0001_2$&$110_2 = 0001_2$&$111_2 =$1$010_2$&$111_2 =$2 ...$001_2$&$101_2 =$1$010_2$&$101_2 = 0010_2$&$101_2 = 0001_2$&$110_2 = 0$...$110_2$&$111_2 =$6$011_2$&$100_2 = 0011_2$&$100_2 = 0011_2$&$100_2 = 0$...$011_2$&$100_2 = 0$Idea generated by staring at this table: comment with idea Implementation based on idea: 144175474 •  » » » 4 months ago, # ^ | 0 for k == 7 i constructed 4+3 i could not figured out how to make 6 + 1. :_:  » 4 months ago, # | -26 my contribution is dead any help would greatly be appreciated and good job on this round  » 4 months ago, # | ← Rev. 4 → 0 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(){ int q; cin>>q; while(q--){ inte n; cin>>n; inte k; cin>>k; n--; if(n+1==2){ if(k==0) { cout<<0<<" "<<1< •  » » 4 months ago, # ^ | +9 I think it should be cout<<-1< •  » » » 4 months ago, # ^ | 0 Oh my god I want to die •  » » » » 4 months ago, # ^ | 0 Bruh I think the luck was not with you today . Imagine knowing the logic and still getting Wa  » 4 months ago, # | 0 Knew the concept of C, could not figure out the edge case :( sol •  » » 4 months ago, # ^ | 0 what is the edge case •  » » » 4 months ago, # ^ | 0 look down  » 4 months ago, # | +56 It is cheating. •  » » 4 months ago, # ^ | +9 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.  » 4 months ago, # | +12 The whole time I was thinking that k can be any positive integer in div2 C TwT  » 4 months ago, # | +4 D was really cool problem!! •  » » 4 months ago, # ^ | 0 can you please give some hints for D •  » » » 4 months ago, # ^ | +3 HintBinary Search on j-i  » 4 months ago, # | +2 Can anyone share the solution for problem C ( Div 2) along with the observation? Thanks! •  » » 4 months ago, # ^ | ← Rev. 2 → +3 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 ^^ •  » » 4 months ago, # ^ | +2 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  » 4 months ago, # | 0 How to solve D div1. Pls give me some ideas  » 4 months ago, # | -10 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? Spoiler ll n; cin >> n; vector v(n),lin(n,-1); for(ll i=0;i> v[i]; v[i]--; lin[v[i]] = i; } ll ans = 0,cur = 0; while(cur=prev;j--){ if(lin[v[j]]>mx){ from = j; mx = lin[v[j]]; } } if(mx>cur){ if(from == prev){ exceptions++; } links++; prev = cur; cur = mx; } else{ break; } } ans += (cur-start) - (2*links-1 - exceptions); ans += links-1; } else{ cur++; } } cout << ans << endl; }   » 4 months ago, # | +6 I am astonishing now about a large amount of NEW accounts were suspected for cheating today in div2.Really Sad to see that.  » 4 months ago, # | 0 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 = 16Generate 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 •  » » 4 months ago, # ^ | 0 Their are other ways too . I generated all pairs And zero except one. But your solution is clever tbh  » 4 months ago, # | +167 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.  » 4 months ago, # | +88 When can we start system testing? •  » » 4 months ago, # ^ | +37 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?  » 4 months ago, # | +24 I just want to submit my code...  » 4 months ago, # | +114 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? •  » » 4 months ago, # ^ | +3 Update: System testing started. •  » » 4 months ago, # ^ | +68 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.  » 4 months ago, # | 0 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.  » 4 months ago, # | ← Rev. 2 → 0 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 ! •  » » 4 months ago, # ^ | 0 I did same. Except I saw the constraint after contest ended.But managed to solve anyway. https://codeforces.com/contest/1631/submission/144245114 •  » » 4 months ago, # ^ | 0 Yeah but i figured it out soon.  » 4 months ago, # | 0 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;" •  » » 4 months ago, # ^ | 0 These will never stop cheating . They ruining our fun of problem solving  » 4 months ago, # | 0 https://codeforces.com/contest/1631/submission/144245114This 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.  » 4 months ago, # | ← Rev. 3 → -14 Points not updated yet?or is this unranked?  » 4 months ago, # | -10 what about dark mode in codeforces?  » 4 months ago, # | 0 Can someone please tell what i did wrong here in Div2 B? This is my code :- Code#include using namespace std; #define ll long long int #define ul unsigned long long int #define mk make_pair #define all(a) (a).begin(), (a).end() #define inp(a,n) for(int i=0; i>a[i]; const ll mod = 1000000007; void solve() { ll n; cin>>n; vector arr(n+1); for(int i=1; i<=n; i++) cin>>arr[i]; ll i = n-1, cnt = 0; while(i>=1) { ll avs = n-i, j = i-avs+1; bool isSame = true; while(i>=1 && i>=j) isSame = isSame && (arr[i] == arr[n]), i--; if(!isSame) cnt++; } cout<> tc; for (int t = 1; t <= tc; t++) { solve(); } }  •  » » 4 months ago, # ^ | 0 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 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:  if(arr[i] == arr[n]){ i--; continue; }  •  » » » 4 months ago, # ^ | 0 Thanks man! I got AC. •  » » » » 4 months ago, # ^ | 0 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.  » 4 months ago, # | +66 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon! •  » » 4 months ago, # ^ | 0 Have the ratings been updated? :D  » 4 months ago, # | 0 which test case in DIV2 Problem B causing wrong answer on test case 3 for many submission? can someone figure out that test case!. •  » » 4 months ago, # ^ | ← Rev. 2 → 0 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 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.https://codeforces.com/blog/entry/99299?#comment-881544Check this comment  » 4 months ago, # | +7 i got fst in div1C... I forgot to reset the left bound  » 4 months ago, # | 0 https://codeforces.ml/contest/1631/submission/144275630 I don't know how to correct this code.(Div2 B) •  » » 4 months ago, # ^ | 0 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. •  » » » 4 months ago, # ^ | 0 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.  » 4 months ago, # | 0 Thank you, everyone, for arranging a great contest.  » 4 months ago, # | 0 Anyone knows why did that user get better rating than me? yqjqygg •  » » 4 months ago, # ^ | +1 Probably because that is one of their first 6 contests •  » » » 4 months ago, # ^ | 0 You are right, thanks  » 4 months ago, # | ← Rev. 2 → 0 can somebody help me with the solution of problem A. Min Max swap. i got a runtime error on pretest #2. my code was: t= int(input()) c = [] while t!=0: n= int(input()) a=list(input()) b= list(input()) for i in range(len(b)): if a[i]>b[i]: a[i],b[i] = b[i],a[i] max_value = int(max(a))* int(max(b)) print(max_value) t = t -1  •  » » 4 months ago, # ^ | ← Rev. 3 → -20 I'm Not familiar with python. But store max_value into long long data type. long max_value = (long)(max(a))*long(max(b)); •  » » 4 months ago, # ^ | 0 If you haven't found the problem yet you're reading the input as string, together with spaces. Use "list(map(int, input().split()))". •  » » » 4 months ago, # ^ | ← Rev. 2 → 0 no it didn't work. the input of the pretest#2 is: 100 100 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 100... 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? •  » » » » 4 months ago, # ^ | 0 It's a very long test case, codeforces don't show all.Here is my solution with same approach: link •  » » » » » 4 months ago, # ^ | 0 Thank you, that helps.  » 4 months ago, # | +8 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 ofI did pretty badly in the round as usual, but I enjoyed the problems (A-D) nonetheless :D
 » 3 months ago, # |   0 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