humbertoyusta's blog

By humbertoyusta, 3 years ago, In English

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:

  1. Um_nik

  2. kiwihadron

  3. heno239

  4. ksun48

  5. Radewoosh

  6. maroonrk

  7. 244mhq

  8. Vercingetorix

Congratulations to all of them for solving all problems!

Div. 2:

  1. YuulBA

  2. wcdr

  3. Dalia12

  4. hrgd

  5. Pure__Vessel

  • Vote: I like it
  • +347
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +117 Vote: I do not like it

As a tester, I tested… GL&HF

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -60 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +25 Vote: I do not like it

        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.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it
    Meme!
»
3 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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

:')
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Congratulations guys, nice job!

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Why no IGM/LGM testers?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +320 Vote: I do not like it

    they have to participate to help tourist cross 4000 rating

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Quite excited to participate in this round!

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

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

»
3 years ago, # |
Rev. 4   Vote: I like it -24 Vote: I do not like it

.

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

2021: Send Monogon's contribution to the moon.

2022: Send tourist's rating to the moon.

»
3 years ago, # |
  Vote: I like it -230 Vote: I do not like it

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://mirror.codeforces.com/problemset/problem/1201/A

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +122 Vote: I do not like it
    1. 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).
    2. This is the announcement blog for an upcoming round, so this is not the place to be posting this.
    3. 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".
    4. 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.
    5. And here you go: 143948025.
»
3 years ago, # |
Rev. 4   Vote: I like it -115 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what the important topics at this Div ??

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck for everybody!!!

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Me tested, me want contribution :eyes:

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you explain a scenario where everyone performs well.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah its a hypothetical situation ! Since performance is relative

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I guess I am just having a bad day :(

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea Me too but still i have the hope:)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 4   Vote: I like it +59 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The one with almost same memory and time are suspicious

»
3 years ago, # |
Rev. 2   Vote: I like it +42 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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}$$$ =)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      i can understand the pain

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Yes problem C ruined my day :(.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    The one that has tricky cases

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +29 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Love the problems

»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +107 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it

R.I.P. the 4k dream.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Submitted the solution 12 secs before, still no judgment?

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

This distribution was quite weird. My times:
D (2000) — 8 mins
B (1250) — 10 mins
C (1250) — 16 mins
A (500) — 16 mins

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

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

»
3 years ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

RESOLVED.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It was "n 0".

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    your code fails for

    1

    8 7

    as there is a possible answer

    7 6

    1 5

    0 2

    3 4

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Hint
    Solution
»
3 years ago, # |
  Vote: I like it +116 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Validator should reject it as an invalid input.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      k == 0
      k <= n - 2
      k == n - 1
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me the solution to Problem D?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    will you please share the approach of problem D?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same after two WA :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

tourist forgot to send solution to F. F

»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    Data for $$$n = 8$$$

    k = 0 k = 1 k = 2 ... k = 7
    $$$000_2$$$ & $$$111_2 = 0$$$ $$$000_2$$$ & $$$110_2 = 0$$$ $$$000_2$$$ & $$$101_2 = 0$$$ ... $$$000_2$$$ & $$$010_2 = 0$$$
    $$$001_2$$$ & $$$110_2 = 0$$$ $$$001_2$$$ & $$$111_2 =$$$ 1 $$$010_2$$$ & $$$111_2 =$$$ 2 ... $$$001_2$$$ & $$$101_2 =$$$ 1
    $$$010_2$$$ & $$$101_2 = 0$$$ $$$010_2$$$ & $$$101_2 = 0$$$ $$$001_2$$$ & $$$110_2 = 0$$$ ... $$$110_2$$$ & $$$111_2 =$$$ 6
    $$$011_2$$$ & $$$100_2 = 0$$$ $$$011_2$$$ & $$$100_2 = 0$$$ $$$011_2$$$ & $$$100_2 = 0$$$ ... $$$011_2$$$ & $$$100_2 = 0$$$

    Idea generated by staring at this table: comment with idea

    Implementation based on idea: 144175474

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

It is cheating.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

D was really cool problem!!

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    • 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 ^^

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D div1. Pls give me some ideas

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +167 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +88 Vote: I do not like it

When can we start system testing?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    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?

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I just want to submit my code...

»
3 years ago, # |
  Vote: I like it +114 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Update: System testing started.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 !

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;"

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.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.

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

what about dark mode in codeforces?

»
3 years ago, # |
  Vote: I like it +66 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Probably because that is one of their first 6 contests

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it
D1D spoiler

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