fangahawk's blog

By fangahawk, 7 months ago, In English

Hello Codeforces!

We're glad to invite everyone to participate in Codeforces Round 940 (Div. 2) and CodeCraft-23, which will start on Apr/21/2024 17:35 (Moscow time). The contest will be rated for all the Div. 2 participants (Rating < 2100).

The Programming Club at IIIT-H organizes this event as a part of our techno-cultural fest Felicity @ IIIT Hyderabad.

Programming Club at IIIT-H

You will have 6 problems to solve in the duration of 2 hours 2 hours and 15 minutes. One of the problems is divided into 2 subtasks. Do ensure you read all of the problems!

There have been a bunch of people that have helped us in making this contest a (hopefully) great one!

Score Distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - (2250 + 1250)$$$

Hope you enjoy the problems!

UPD: The editorial can be found here.

UPD: The Winners

Official

  1. Alphaqwq_
  2. misfits
  3. Monkey1ng
  4. Nanani_fan
  5. lmq3z

Unofficial

  1. BurnedChicken
  2. maspy
  3. kotatsugame
  4. zdc123456
  5. zjy2008
  • Vote: I like it
  • +373
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +135 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmmm cool

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I hope I will not reach specialist in this round

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a participant,hoping for clear and short statements

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Damn, never hoped that after Indian ICPC, IIITH Programming club would go international! Really looking forward to attend it!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to the positive delta after this round

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

bet

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Will the score distribution of the problems be published? Or will the contest be held on ICPC rules?

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

    It will have a score distribution. We will publish it soon.

»
7 months ago, # |
  Vote: I like it +33 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Hope so there is no moss for this :)

»
7 months ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

As a tester I really liked the problemset and encourage everyone to participate in the round!

akcube fangahawk orz

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great to hear you enjoyed the problem set! Your encouragement really makes me want to dive in and give it a go. Thanks for the motivation!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post the score distribution as well?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for pupil

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I will upvote if I become CM

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wishing everyone a good codeforces round after a week.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

akcube round, orzzz!!!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what algorithms book and resources gennady korotkevich (tourist) read?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the score distribution of the problems be published? Or will the contest be held on ICPC rules?

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Best of luck so that you can get good response for your questions, from IIIT Hyderabad.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

clear and short description we like it

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Minecraft !!

»
7 months ago, # |
  Vote: I like it +83 Vote: I do not like it

IIITH Programming Club orz

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a participant, I would like to get upvotes as minus looks ugly in my profile!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1K stalkers and I will write this one.

»
7 months ago, # |
  Vote: I like it +93 Vote: I do not like it

As a monkey tester, I was offered $$$6+9+6 \times 9$$$ bananas to write this comment.

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

I too wanted to join IIIT bcoz of the coding culture there, my clg sucks

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

    Yeah I hear a lot about IIIT too....but then everything can't be helped I guess....at this point you should be contributing to building the culture there.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping to reach pupi.

»
7 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Why codecraft-23 in 2024, isn't it codecraft-24?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best wishes for everyone's A, B, C, D

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the score distribution be announced?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what meant by score distribution

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

      Usually contest happen in either icpc style, i.e. every question has equal weightage, i.e. whoever does any question first gets higher rank. Whereas normal contests on codeforces (non educational rounds) have ratings attached to them so that they are indicable that it is 50% chance that it can be done by someone having rating about equal to what's shown, and the if you do a higher rated question its more rank than doing first few questions.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Score distribution $$$\neq$$$ problem rating, those are two separate things.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But scores are proportional to the earned points ig

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

            Usually, yes, but his explanation was still wrong, he mixed up the two systems. The score distribution does not tell you how much a problem is rated, only its value in the contest.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah agreed problem ratings depends on the problems itself there is no way one can just guess without opening the problem and not even the order justifies that I have C labelled 800 rated problem

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

            To clarify, scoring distribution is different from the ratings attached to the problems post-contest. Ratings are given to problems after the contest is over based on number of solves, etc. and are indicative of the rating required to solve the problem in contest. Scoring distribution is just the points you as a contestant would gain if you solved it at the 0th minute. It's more or less only meant to be indicative of what the setters + testers approximate the relative difficulty of the problems to be.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Got it — "Ratings are given to problems after the contest is over based on number of solves"

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Will try to solve 3 questions !! Wish me luck :)

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

ee sala cup namde

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I taught this was a programming contest,looks like a math test to me

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

so much math i loved it, knew solutions within minutes of every question, but while implementation so many mistakes :(

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone pls enlighten me on how to solve D

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

    it is clear from the question that we need for each y

    ax ^ ax+1 ^ ax+2 ... ^ ... ^ az-1 ^ az > ax ^ ax+1 ^ ax+2 ... ay ^ ... ^ az-1 ^ az.

    note in lhs, ay is missing so basically what we need is all those ranges(x, y) in which sum of MSB of ay is even.

    we need x, y, z. traverse through y, now for each y calculate no. good x and z pairs.

    suffix and prefix dps can be maintained for each bit for odd and even counts.

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

      Is MSB = max set bit? That makes sense but I'm kinda confused about how you would implement the prefix and suffix dp. If you don't mind, can you please give me the gist? Appreciate it.

      Edit: oh wait nvm I see how to do it. Thanks broski

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

        okay, both will have 3 states -> suffix/prefix, bit, odd/even. i will tell for prefix, suffix is similar. pref[n+1][30][2] (n+1, for simple implementation, 30 bits and 2 odd and evens)

        dp state pref[i][j][0] represents count of bit j till ith elements such that parity/zor of that bit is 0(even)

        basically

        a1, a2, a3, a4, a5, a6, a7 a8 ....

        if we are at a8, and we are taking a look at 4th bit (i.e., bit at this position -> (1<<4)) then if we take all suffixes ending at a8 and xor each suffix, the state represents no. of such suffixes that have THE 4th bit off.

        think for transitions it's not that difficult/look at my code., if you don't understand then ill write it. (if anything is unclear don't hesitate to ask or even dm me.)

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why msb ?

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

        because in a range for a particular bit there can either odd or even no of that bits. now, we are taking a range (x, z) and we have to remove any element from that range new range -> (x, y-1) ^ (y+1, z), if in new range there are odd bits, then old range will have even bits of MSB.

        basically i am structuring my solution such that it is dependent upon MSB.

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

          ok,i know what you mean, just because remove aj will happen some change, and MSB will be make this change simple. thx

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you explain this part please, I get the pO*aE + pE*aO part but why did you add aO+ pO, can you please explain

          Spoiler
»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I was way too close to solving problem C! Great problemset :D

»
7 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Thanks for the math contest authors. Always appreciate a -100 delta.

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

C was way too hard for me... After an hour of intense math i found a formula, which gives much bigger answer for the second sample, but i just can't find any single thing wrong with it... If we won't place any rook on main diagonal there are $$$30$$$ possible positions for the first rook, after that there will be $$$12$$$ possible positions for the second rook and $$$2$$$ positions for the last one. In total it is $$$30 * 12 * 2 = 720$$$, which is already bigger, than $$$331$$$... What's wrong?

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

    I was able to find a recurrence for C but was not able to submit in time because of runtime errors.

    F(n) = F(n-1) + (2*n-2)*F(n-2)

    where n is the total number of row and column numbers which were not used. Not sure if it is correct.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      I also came up with same relation but I got WA 257630731

      I forgot to add dp[0]=1; Oh god.

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

      Can you provide the intuition for this?

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

        Let us assume some n pairs (r,c) where the rooks have already been kept. Now we cannot keep the rook in any of those (r,c) or (c,r). So, that leaves us (n — r -c) rows and (n — r -c) columns.

        Now, let us list down these x = (n-r-c) viable rows and columns as a1, a2, a3 .. ax.

        So, we can keep the rook at a1,a1 and a1 will be removed from the above list and we will have x-1 elements in the list. (so, f(x-1) part)

        If we take any other ai, we will have x-2 elements left, and we can arrange a1 and ai in 2 ways multiplied by numbers of ways to arrange those x-2 elements. And there are x-1 ways to chose some ai. Hence 2*(x-1)*f(x-2).

        So, the recurrence becomes : f(x) = f(x-1) + 2*(x-1)*f(x-2).

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

        I'm not great at explaining, so forgive me if this isn't clear.

        Initially, I noticed that placing a rook at coordinates (ri, ci), where ri ≠ ci, eliminates 2 rows and 2 columns, reducing the chessboard from n*n to (n-2)*(n-2). Similarly, if ri = ci, it removes 1 row and 1 column, making it (n-1)*(n-1). Let's say after K moves, we've removed some rows and columns, leaving a chessboard of size m (m ≤ n). Now, this smaller board becomes a blank canvas for determining how many boards we can build by arranging the rooks. The challenge lies in determining the number of possible boards we can build. Initially, I considered a brute force approach where I place a rook on a cell, compute the resulting reduced matrix after the computer's move, and repeat.

        $$$\displaystyle f(n)= \sum_{i=1}^n \sum_{j=1}^n

        \begin{cases} f(n-1),& \text{if } i=j\\ f(n-2), & \text{otherwise} \end{cases}

        \text{ where cell } i,j

        \text{ has a white rook}$$$
        $$$ f(1)=1,f(2)=3; base cases $$$

        However, this solution is inefficient with a time complexity of O(N^2) and suffers from overlapping solutions.

        For instance, consider a 3*3 matrix where a white rook is fixed at (1,1) you will get 3 possible boards.

        W _ _	W _ _    W _ _
        _ W _	_ _ W    _ _ W
        _ _ W	_ B _    _ W _
        

        Also when you fix rook at (2,2) you will get 3 boards.

        W _ _	_ _ W    _ _ B
        _ W _	_ W _    _ W _
        _ _ W	B _ _    W _ _
        

        As you can see we have one overlapping solution.

        By examples I observed that we can calculate all possible boards by fixing the rooks in just one row. So we take a row and see all the variations of that row and calculate the number of boards for each variation and this would give us the unq count.

        W _ _	_ W _    _ _ W
        _ _ _	_ _ _    _ _ _
        _ _ _	_ _ _    _ _ _
        
        _ B _    _ _ B
        _ _ _    _ _ _
        _ _ _    _ _ _
        

        Below is the formula of our revised approach ( the base condition remains same)

        $$$\displaystyle f(n)= \sum_{j=1}^n

        \begin{cases} f(n-1),& \text{if } j=1\\ f(n-2), & \text{otherwise} \end{cases}

        \text{ cell } 1,j

        \text{ has a white rook} + \sum_{j=2}^n f(n-2)

        \text{ cell } 1,j

        \text{ has a black rook} $$$

        If you simplify this you will get

        $$$ f(n)= 2*(n-1)f(n-2)+f(n-1)$$$
    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      .

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

    I think the problem is that operation order doesn't matter, so it should be divided by $$$(n/2)!$$$

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

      Maan, I am so bad at combinatorics)

      Thank you)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thought the same. Someone enlighten me.

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

    The 720 possibilities are overcounted. Eg. These two configs are same;

    - W(1,3), B(3,1), W(2,4), B(4,2)
    - W(2,4), B(4,2), W(1,3), B(3,1)
    

    The final rook positions are same in above 2 cases.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah, thought the same, i could figure out only that 1 is the way we put all in diagonal, so i need to come up with 330, maybe 720/2 gives 330 lol

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I just solved it once the contest was over:(((((((((((( Unfortunately I couldn't submit my solution which I am sure that it is correct :((

    #include <bits/stdc++.h>
    using namespace std;
    
    #define ull unsigned long long
    #define ll long long
    #define ld long double
    #define int ll
    
    #define endl '\n'
    #define EPS .0000001
    #define MOD 1000000007
    
    void calculate();
    
    int dp[300010];
    signed main() {
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= 300000; i++) {
            dp[i] = dp[i-2]*(i-1)*2+dp[i-1];
            dp[i] %= MOD;
        }
        int t = 1;
        cin >> t;
        for(int i = 1; i <= t; i++) {
            calculate();
        }
    }
    
    void calculate() {
        int n, k;
        cin >> n >> k;
        int x, y;
        set<int> st;
        while(k--) {
            cin >> x >> y;
            st.insert(x);
            st.insert(y);
        }
        n -= st.size();
        cout << dp[n] << endl;
    }
    
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I dunno what got into me, but i have found a recurrent formula, similar to yours, but for some reason I was trying to make it linear...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My way of thinking was similar. There are $$$10$$$ ways for the second rook, because $$$30-(4*8-4*3)=10$$$. And because by filling up the remaining diagonals, all these could be considered as final positions. So after placeing 2 rooks, there are $$$30*10=300$$$ possible positions, which again could be considered as final ones. And then $$$1+30+300$$$ gives $$$331$$$ (the $$$1$$$ is needed because the initial position can also be considered as a final one). But what I don't get is that we overcount the positions after 2 rooks, so it should be $$$150+30+1=181$$$. Can anyone please explain it to me?

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

    Btw, my A got WA on system testing, wow... $$$a_i \le 100$$$ got me there... Definitely, not a good day for me...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this solution would have been correct if two rooks position swapped yields a different setting. but according to problem, they are same. and if you notice carefully, its 6! = 720 and there is a reason for that.

    you can look at my solution i did not do recurrence i used combinatorics only.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    did the same!

    what you need to do is to divide this big number i.e. 720 with 3!.

    It is because there are repeated groups in counting. and the number of repetitions for each group is 3!.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have any advice for improving on problems like C in today's contest?

»
7 months ago, # |
  Vote: I like it +26 Vote: I do not like it

OMG, I SUBMITTED D 8 SECONDS BEFORE THE END

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think D is more intuitive than C.

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

Problem B in a Nutshell, huge skill issue

Spoiler
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    basically you can just check whats the biggest number for Math.pow(2,x)-1 <= k because Math.pow(2,x)-1 is only 1's, the rest of the number doesnt really matter and you can sum it up with the difference and the rest 0's

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it
    a ^ b < a implies that msb of b should be present in a 
    which means for given A[i] ans = no. of pairs l, r such that msb of 
    A[i] should be present in that xor(l...r).
    i couldn't implement in time but i'm sure it's correct 
    

    UPD :- i was correct 257663607

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain b? I am getting wa.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about how any number that looks like this $$$2^{n}-1$$$ has all ones in it's binary representation. Also if $$$n=1$$$ just print the value of $$$k$$$. In all other cases where $$$n\geq1$$$ you only really need to print two numbers that sum up to $$$k$$$.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let $$$b$$$ be highest bit in k. Then you can get $$$b-1$$$ bitcount by just printing $$$s = 2^{b} - 1$$$. Then print out $$$k - s$$$ and fill the rest with zeros.
    Why does this work?
    Either $$$k - s$$$ will be greater equal than $$$2^b$$$, then you've got all bits in answer and you can't make it bigger (note that it means k has no 0s in its binary representation,
    or $$$k - s$$$ will be smaller, but that means that you "spent" 1 from b-th position to cover up all 0s in lowest bits.

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hello, I want to report a cheater "Sputnik123". No need to long text lol, he just cheated.

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I Solved C during the contest but once I fixed some minor bugs in my code I found that the contest is over :(

Here is my (should be) Accepted code for problem C:

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define int ll

#define endl '\n'
#define EPS .0000001
#define MOD 1000000007

void calculate();

int dp[300010];
signed main() {
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= 300000; i++) {
        dp[i] = dp[i-2]*(i-1)*2+dp[i-1];
        dp[i] %= MOD;
    }
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        calculate();
    }
}

void calculate() {
    int n, k;
    cin >> n >> k;
    int x, y;
    set<int> st;
    while(k--) {
        cin >> x >> y;
        st.insert(x);
        st.insert(y);
    }
    n -= st.size();
    cout << dp[n] << endl;
}
»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I didnt had dream last night for maths formula of c. so i was not able to solve it( btw one of worse c i have seen). (If author love maths then give olympiads)

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Found my bug in C five seconds after contest ended. That sucks.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: Brute force a solution for cases in which n = 2. Generate random testcases keeping n = 2 and see where your code gets a different answer from the brute force solution.

»
7 months ago, # |
  Vote: I like it +88 Vote: I do not like it
Solved D but at what cost.. nice D tho 🙂
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

road to pupil :pray: thank you

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone explain why this fails? 257627963

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try cases with low value of $$$n$$$.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your submission fails for cases like n=2 and k=100. One answer is [63,37], with 7 1s, however your code returns [1,99] which has only 4 1s. The optimal way is to find such m, that 2^m-1 <= k

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for problem F? I thought of doing merge sort segment tree with heavy-light decomposition, then binary search to find the lowest value that the count is not equal, but I realized there some edge cases.

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

My B problem got Judgement failed veredict, what that means?

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

Mathforces

»
7 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

problem C last minute submission got very much raised after 2:05 due to this solution being leaked online in a telegram group please MikeMirzayanov look into this behaviour of participants : screenshot of the solution , i will later reveal those solutions which are being cheated from here!(https://ibb.co/TTQGHV3) Vladosiya othmaine also look into this once please

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one submission which was a random person in my friend list: link

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

    found three cheaters they tried very much to keep their submission for not being detected 257640596 useless variables and deleting those we will get exact same as the solution even the line space etc is also exact same (spacing is same) ! 257641772 exact same , 257640016 exact same again . Please look mostlikely they may be undetected due to some minor changes but the format and spacing is exact same . MikeMirzayanov Vladosiya

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also checked out the previous contests which those three gave, Infact there too they cheated from a telegram group . Infact now the first user upsolved the B ,C problems which he/she already did in contest time . That also leads us to why he/she cheated the same code exactly which i shared earlier just because of some useless variable declarations like int p1=INT_MIN; he/she will not get caught at all.

»
7 months ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

Could anyone please tell me why the answer for n=6 in E is 24? I am getting 23 by hand and code, I was able to simplify the formula for C(i,j) mod j as follows:

1) if j is prime then ((i/j) mod j)*(j-1)

2) if j is not prime then we only need to do this for j=4 because (j-1)! mod j is 0 for all other composite numbers

»
7 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I guess D can be solved using dp

Screenshot-2024-04-21-223826

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    It's more observation i would say, if you can think of the final equation the dp is strightforward to use to calculate it

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not combinatorics which has exponential time complexity in brute force. It's just a very classical "change your perspective to group quantities together" type of problem.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Exponential? You mean cubic?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please read carefully of what I wrote before commenting. That's basic respect.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh sorry, I thought the combinatorics had something to do with the problem

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Could anyone please explain how to do problem C? I always seem to struggle in these types of problems related to combinatorics :(

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is possible to solve using combinatorics but the solution would be way harder. (You need some techniques to reduce time complexity).

    I guess the official solution would be DP: DP[n] = DP[n-1] + DP[n-2] * (n-1) * 2.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would you kindly explain how you figured it out? Like explain why this works? I haven't solved many dp problems too.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Assume there is an N X N chessboard, and you know how many different configurations are there for 1 ~ N-1. Think N X N chessboard as an extension of an N-1 X N-1 chessboard.

        1. It is possible for you to put a rook at (N, N). The number of cases equals to DP[n-1].
        2. If not, a rook should be added somewhere between (N, 1) ~ (N, N-1). The number of cases equals to DP[n-2] * (n-1) * 2.
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mathForces

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can't believe I'm this bad. Can't even solve 3 problems

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was quite to my liking and I was able to sprint to rank 50 after solving C, although temporarily(^_^)

But D was too difficult and I fell to rank 900+ for not solving any problem after C._(:3]<)_So how to solve it? I was confused by my prefix and suffix array, so tried brute force, but it got WA rather than TLE.

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

    For any number, $$$a_i$$$ you can find that it satisfies the condition only when the xor of subarray in which $$$a_i$$$ is present has the MSB of $$$a_i$$$ set to zero, now you just need to find these subarrays for each element which can be done using dp for each bit j.

    To find the first observation, try to think of an answer for $$$n^2 logn$$$ where you iterate on each subarray and find the number of possible y's in that subarray. What will be the condition for y?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why only MSB? If any bit is set in ai, but not set in xor of the whole subarray, then it would lead to a valid answer, right? It doesn't necessarily have to be MSB.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes,i mean same of you, but i think twice MSB just make this question be simple. MSB just a "point"

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        because if the msb is set in the subarray then taking xor will make it zero and then for any bit< msb even if u set it you can't satisfy the conditon since $$$sum_{i=1}^{n-1} 2^i < 2^n$$$.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain to me what this test result means? Also it's not even shown like -1 in results, just empty square, as if I havn't submitted this problem

https://codeforces.me/contest/1957/submission/257589755

»
7 months ago, # |
  Vote: I like it -34 Vote: I do not like it

combinatorics is the most no skill thing you can ask a programer to do

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for q1 has been given the verdict as judgement failed, what does it mean?

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

everyone solved C using dp but I only did some n choose r math thingy 257639189

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E, F?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It says judgement failed for problem B https://codeforces.me/contest/1957/submission/257590765

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

E problem was just observations i think.. i didnt prove anything concrete, just saw first few values and came to conclusion that n = 4 and n = prime are kind of special cases to handle.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I am getting judgement failed verdict on this submission.

https://codeforces.me/contest/1957/submission/257590736

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone know what the verdict "Judgement failed" means. Muhammad-Saram got it and I feel bad for him. His logic was on point. Here's his submission

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

my solution for B is still not judged https://codeforces.me/contest/1957/submission/257594447 even when system testing is finished :/

»
7 months ago, # |
  Vote: I like it +25 Vote: I do not like it

 3 pages of judgement failed, strange.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And all of them were made almost at the same time

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is judgement failed??? Is it wrong answer?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/1957/submission/257616209 I faced judgement failed in this submission?

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

https://codeforces.me/contest/1957/submission/257627565 https://codeforces.me/contest/1957/submission/257651698 submitted the exact code again and it passed now but gave runtime error during system testing. What's going on? Codeforces high or wat?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem B, can someone please explain why my submission 257616558 is incorrect? I agree I overkilled it a little bit, but I cannot see how the Jury's answer is better.

»
7 months ago, # |
  Vote: I like it +49 Vote: I do not like it

I would like to report a suspicious contestant: F9O1OvO

I think he cheated because his template has changed massively:

  • His main function looks completely different
  • He switched from typedef to define
  • He suddenly uses "namespace wshb"

His submission for problem A in today's contest: 257575498

His submission for problem A in his previous contest: 255636465

His performance is also very unusual — I find it very weird that a specialist who has participated in more than 50 contests suddenly gets 5th in a div.2 round.

I believe he might have given his user to another person.

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

    And they said: "If you solve ABCD, cheaters won't affect you", lol

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +12 Vote: I do not like it

      Yeah lmao. When I previously reported some cheater, some user told sth similar also,

      Debunked
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yeah a sudden Rk 5 and his template changing is definitely an indicator it wasn't him doing the contest.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me whats wrong in my code. I thought if sum of array is k and number of 1 bit is maximum it work. but it is not why? sub :https://codeforces.me/contest/1957/submission/257631018

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here

    t = int(input())

    for _ in range(t): n, k = map(int, input().split()) q = k ans = [0]*n l =0 while k>=2 and n>0: for i in range(0,k+1): if pow(2, i) >k: ans[l]= 2**(i-1)-1 l+=1 n-=1 k=k-(2**(i-1)-1) break

    if sum(ans)<q:
        ans[-1]+=q-sum(ans)
    print(*ans)
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there is this set of data: n = 14, k = 720729. The number of 1s actually equals to 19, and you give 17. I think your solution is inaccurate for the case where s is not equal to k.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice round, but why problem E doesn't have a bolded notification that sum of n over subtests is unbounded? It messed me a bit up.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i submitted my E in the last 4 minutes just to realise that

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

✋✋✋**help wanted** ✋✋✋✋✋✋ i know i am dumb but can anyone tell me where the hell am i wrong here! it works like magic bitcount are correct+ sum of the nums are correct then what?

t = int(input())

for _ in range(t): n, k = map(int, input().split()) q = k ans = [0]*n l =0 while k>=2 and n>0: for i in range(0,k+1): if pow(2, i) >k: ans[l]= 2**(i-1)-1 l+=1 n-=1 k=k-(2**(i-1)-1) break

if sum(ans)<q:
    ans[-1]+=q-sum(ans)
print(*ans)
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    atleast format the code before asking for help.

    cout << "Please!!" << endl;
    
»
7 months ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

what an impeccable contest and i hope that there will be more contests like that

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

Mathforces (More like combiforces tbh).

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

This is one of the best rounds I have had in recent times, with clever ideas in every question! Hope to see more rounds like this~

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the time complexity of question E?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool

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

In the next codecraft we'll have "How does the Knight move??"

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

    I'm glad someone got that reference :D

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Round !

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what's wrong with my Solution

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to reach 1200 points after this compete

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I'm not in the winners list??? I'm 2nd!!!

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i wish you all reach what u want :)