Блог пользователя humbertoyusta

Автор humbertoyusta, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • +347
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +117 Проголосовать: не нравится

As a tester, I tested… GL&HF

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 года назад, # ^ |
        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.

      • »
        »
        »
        »
        2 года назад, # ^ |
        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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится
    Meme!
»
2 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

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

:')
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Congratulations guys, nice job!

»
2 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Why no IGM/LGM testers?

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Quite excited to participate in this round!

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 4   Проголосовать: нравится -24 Проголосовать: не нравится

.

»
2 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

2021: Send Monogon's contribution to the moon.

2022: Send tourist's rating to the moon.

»
2 года назад, # |
  Проголосовать: нравится -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...); }

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +122 Проголосовать: не нравится
    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.
»
2 года назад, # |
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.

»
2 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what the important topics at this Div ??

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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 .

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Good luck for everybody!!!

»
2 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
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.

»
2 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Me tested, me want contribution :eyes:

»
2 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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?

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I guess I am just having a bad day :(

»
2 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +59 Проголосовать: не нравится

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

»
2 года назад, # |
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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +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}$$$ =)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      i can understand the pain

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Yes problem C ruined my day :(.

  • »
    »
    2 года назад, # ^ |
    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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    The one that has tricky cases

»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
    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.

  • »
    »
    2 года назад, # ^ |
    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

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 3
»
2 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Love the problems

»
2 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +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)

  • »
    »
    2 года назад, # ^ |
    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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<n-1$$$ so another one is needed (it's also simple. The case analysis seems unavoidable).

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

R.I.P. the 4k dream.

»
2 года назад, # |
  Проголосовать: нравится +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)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Submitted the solution 12 secs before, still no judgment?

»
2 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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

»
2 года назад, # |
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.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

RESOLVED.

  • »
    »
    2 года назад, # ^ |
    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится 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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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;)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Hint
    Solution
»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain to me the solution to Problem D?

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
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!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    will you please share the approach of problem D?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same after two WA :)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

»
2 года назад, # |
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?

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

tourist forgot to send solution to F. F

»
2 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
2 года назад, # |
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
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

It is cheating.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

D was really cool problem!!

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    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 ^^

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D div1. Pls give me some ideas

»
2 года назад, # |
  Проголосовать: нравится -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
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +88 Проголосовать: не нравится

When can we start system testing?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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?

»
2 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

I just want to submit my code...

»
2 года назад, # |
  Проголосовать: нравится +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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Update: System testing started.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
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 !

»
2 года назад, # |
  Проголосовать: нравится 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;"

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

what about dark mode in codeforces?

»
2 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
D1D spoiler

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