Well... :p

• CodeCraft-22
• CodeCraft-21
• CodeCraft-20
• CodeCraft-19
• CodeCraft-18
• CodeCraft-17

good

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

fangahawk akcube orz!

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!

What if you become master?

what if you become IM ?

He is an algorithm book and resource by himself.

I can speedrun minecraft, does that mean that I will AK the contest?

me first

Lessgooo!

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.

it's annual hackathon by IITH codecraft-24 will by 2025 ig

what meant by score distribution

Only if you knew math, 2021 would have come by now

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.

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.

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

Thought the same. Someone enlighten me.

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.

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

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

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?

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

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.

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

solve dp I think

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

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

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

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.

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.

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

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

Same here

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

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

Found my mistake

It's more observation i would say, if you can think of the final equation the dp is strightforward to use to calculate 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.

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.

no , contest was trash(2.25 hours wasted)

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?

Same with me, i investigated a bit and it seems that it's a internal error of the system not of the code. Hope they fix the error soon.

I rejudged your submission.