Dominater069's blog

Invitation to CodeChef Starters 177(Rated upto 5 stars) — 12th March
By Dominater069, 15 hours ago, In English

We invite you to participate in CodeChef’s Starters 177, this Wednesday, 12th March, rated upto 5 stars (i.e. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

UPD : The number of problems in each division is as follows:

  • Division $$$1$$$ : $$$6$$$ problems
  • Division $$$2$$$ : $$$7$$$ problems
  • Division $$$3$$$ & $$$4$$$ : $$$8$$$ problems

UPD 2 : Congratulations to the winners:

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

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

Dominater round after so long

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

korbo lorbo jeetbo re

→ Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest starts in ~30min.

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to have some fun with the problems .

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

is the problem blocktree , perfect subset sum ?

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

    $$$k = 0$$$ or $$$n$$$ : You can achieve $$$score = 1$$$

    $$$score = 2$$$ : Achievable iff there exists subtree of size either $$$k$$$ or $$$n - k$$$

    $$$score = 3$$$ : Always achieveable, colour any connected set of $$$K$$$ nodes as $$$1$$$. It can be shown that a path will be $$$0..01...10...0$$$ in the worst case.

    → Reply
»
5 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

i am sorry for the weak samples on Matching Arrays.

I expected the problem to be much easier than it ended up being. The correct decision was indeed a stronger sample.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Off-topic, but who are the 6 and 7 star north korean users?
    Many of them are never mentioned in the list of top 5 winners. I assume this is due to their cheating being pretty transparent. I distinctly remember one of them beating the lgm nachia in one of the contests. Was AI really able to solve all those problems? Their coding styles also seem legit.
    So, how are they cheating?

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i believe they are team accounts, still the individual members would have to be strong...

      → Reply
  • »
    »
    98 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would say samples are used to help understand the problem statement. Weak samples are ok as long as this is in a full feedback contest.

    I also got it wrong 2 times, but Wrong Answer forced me to re-think if my solution is wrong.

    → Reply
»
3 hours ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

In the problem SUMBYOR , the test cases are weak as the number of distinct possible numbers are close to 32000. But i have seen accepted codes with time complexity as big as O(32000^2). The code given below is accepted.

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

#define int long long

const int MAX_N = 200000;

int getBitMask(int num) {
    int mask = 0;
    for (int i = 0; i<30; i++) {
        if (num & (1LL << i)) {
            mask |= (1 << i);
        }
    }
    return mask;
}

void solve() {
    int n; cin >> n;
    map<int, int> freq;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int mask = getBitMask(a[i]);
        freq[mask]++;
    }
    vector<pair<int, int>> masks(freq.begin(), freq.end());

    int sum=0, pref=0, ct=0;
    for (int i = 0; i < masks.size(); i++) {
        int mski = masks[i].first;
        int cti = masks[i].second;
        sum += (cti*(cti-1)/2)*2;
        for(int j = i + 1; j < masks.size(); j++) {
            int maskj = masks[j].first;
            int ctj = masks[j].second;
            if ((mski & maskj) == 0) {
                sum += cti * ctj * 1;
            } else {
                sum += cti * ctj * 2;
            }
        }
    }
    cout<<sum<<endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
→ Reply