Zco practice contest #3

Competitive Programming
1

What are the solutions to the problems ???
What were the topics , subtopics requires to solve them kindly also provide the approach i.e the Logic
How many marks did you guys obtain.

2

@Balajiganapathi sir please update the editorial fast!

3

What score did you all get ??
Is 51 ok ??

4

Here is a quick user-editorial to the ZCO Mock 3:

Problem 1: Number Grid
Topic: Combinatorics;

Notice that the problem asks for updating any two adjacent squares (which share a side) of the grid by any integer.
Now, the key step is to colour the grid black and white (like a chess-board). We keep the sum of numbers of black squares and white squares.
Notice that, when we perform an operation, we add the same number to two adjacent squares and any two adjacent squares are of always different colours. Thus, we notice that:

  • When we perform the operation, the difference between the sum of black and white squares remains constant (or invariant).

Now, the difference of the sum of white squares and black squares initially and finally should be constant and same. Thus, we calculate it difference of the sum of the white and black squares of
the initial grid (which is given in the input) and the final grid (which has all the cells with the integer C) and check if it is same. If it is, then we are done.

Note that we don’t really care about the total no. of operations which we take (as it is given granted in the problem itself).

Code:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define fi first
#define si second

const ll MOD = 1e9+7;
const ll INF = 1e17;

int main() {
    speedup
    int n, m, c;
    cin >> n >> m >> c;
    vector<vector<int>> a(n, vector<int>(m));
    ll sum1 = 0, sum2 = 0;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
            if ((i+j)%2 == 1){
                sum1 += a[i][j];
                cnt1++;
            }else{
                sum2 += a[i][j];
                cnt2++;
            }
        }
    }
    if (sum1 - sum2 == (cnt1-cnt2)*c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Problem 2: Swaps
Topics: Bitwise Operations, Summation;

Now, we are going to exploit the condition that N \le 18. Notice that, in binary representation of the indices, each of the index has at most 18 bits.
First, let’s solve the problem without any queries.

Now, in each operation involving 2^k (where we divide the whole segment into blocks, each size 2^k), we are just toggling the k-1 th bit (bits are counted from right, 0-indexed) and swapping it to the toggled number. For example, for k = 2, we will be swapping 4 = (100)_2 with 6 = (110)_2 and notice that toggling the k-1=1 st bit of 4 (from right and 0-indexed), we get 6.

Thus, we are motivated to count the sum, interms of the bits of the indices.

Like:

\sum_{k = 0}^{2^n-1} k A[k] = \sum_{b = 0}^{n-1} S_b 2^b

where S_b denotes the sum of A[j]'s , where the number j has its b th set to 1.

Now, we will compute the sum by computing S_b cleverly.

Consider the initial array A[] without any swapping. For each bit b, we have only two possible choices for the S_b. It is:

  • Sum of the A[k]'s where k has its b th bit set to 1.
    We can achieve this sum, naively from the definition of S_b.
  • Sum of the A[k]'s where k has its b th bit set to 0.
    Now, after performing a 2^{b+1}-block swapping, we can achieve this sum as all such k from the above sum, will have their b th bit set to 1.

Now, note that S_b is dependent only on the 2^{b+1}-block operation.

Note that in the implementation, we will be having two sums stored (say S_{b0}, S_{b1}), for each S_b calculation.
Thus, we are done.

Now, for solving the queries, first we subtract A[X] from where-ever we added it (S_{b0} or S_{b1} for each bit 0 \le b \le n-1).
Then, we add the value of Y from where-ever we subtracted A[X] and proceed (by storing it with A[X]) to compute the answer of the query in a straight O(N) loop, which is fast enough.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <functional>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define LSB(x) ((x) & -(x))


int main(){
    speedup
    int n; cin >> n;
    vector<int> a(1<<n);
    for (int i = 0; i < (1<<n); i++){
        cin >> a[i];
    }
    vector<vector<ll>> dp(n, vector<ll>(2));
    for (int mask = 0; mask < (1<<n); mask++){
        for (int i = 0; i < n; i++){
            if (mask&(1<<i)){
                dp[i][1] += a[mask];
            }else{
                dp[i][0] += a[mask];
            }
        }
    }
    int q; cin >> q;
    while (q--){
        int x, y; cin >> x >> y;
        for (int i = 0; i < n; i++){
            if ((1<<i)&x){
                dp[i][1] -= a[x]; dp[i][1] += y;
            }else{
                dp[i][0] += y; dp[i][0] -= a[x];
            }
        }
        a[x] = y;
        ll ans = 0;
        for (int i = 0; i < n; i++){
            ans += min(dp[i][0], dp[i][1])*(1<<i);
        }
        cout << ans << '\n';
    }
    return 0;
}

Thanks for the reading… :grinning:

2 Likes
5

Thank you bro but one question, bitwise operations are not listed in the syllabus. How come could they be asked in a question. I know that there is a not bitwise solution also, do you have that also? The code of that will do.