SIX SEVEN

print("Hello World")

WoW ！

SIXTY SEVENNNN

Why are there people with more than 2100 rating that have registered as an official participants?

i love edu rounds but the fact is it always decreases my ratings!!!

No testers???

Thanks for the round! Interesting to see the Blackbox Cup format—good luck to everyone participating!

When can I become purple

Guys, what are the differences between educational round and normal round?

I wish I can solve C and become 1500 rating or above. I wish there is at least one problem in difficulty 1400 — 1600 for me to study.

cp just ruined my life, i hate cp im never coming back here

What is the point of these rounds?

• They're not "educational" as the name implies (in fact, the average div-2 accomplishes the original goal of these rounds (to expose more users to general algorithmic techniques) to a far greater extent)
• They're not fun. I think they can be summarized as "div-3s but less fun, less balanced, and way more tedious". Having no testers doesn't help either.
• They waste slots. Why not have regular div-2s instead of these rounds? Considering how the proposal queue is always full, there's certainly no shortage of problems for regular rounds.
• ICPC scoring sucks, I have no idea why it's present in this format.

Even contests like Good Bye 2023 are infinitely superior to whatever today's round was.

why is it so hard man:(

Nice round! Though I feel like C > D

Hey guys, During this contest and in the last 10 minutes, I headed towards B, I thought this would be a simple greedy algorithm, but I never really had learned any algorithm, I now have wrote this code

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

int main() {
  int m= 0;
  int t;
  cin >> t;
  while (t--) {
    string x;
    cin >> x;
    int l= x.length();
    if (l == 1) {
      m++;
    }
  }
  return 0;
}

Its not even complete, If anyone knows what should I do next, please help me.

Solution of F: First put numbers from 1 to n on a binary tree, where the root is floor((1+n)/2), and the left and right child of each node represent the left and right range of the next step of binary search. For example n=12:

             6
          //   \\
       3          9
    /    \      /   \
   1     4    7      11
    \     \    \    /  \
     2     5    8  10  12

Then we can observe that for any two nodes u < v (proof omited):

(1) If u is ancestor of v, or the v is ancestor of u: beauty(u,v) = n-(v-u).

(2) Otherwise, beauty(u,v) = n- (2 + (size of subtree of right child of u) + (size of subtree of left child of v)).

We denote the formula above as n- (2 + RSZ(u) + LSZ(v)).

To calculate the answer, first we pretend that there's no situation (1). Then we iterate v from 1 to n, use a map to maintain for each possible size k, there are how many u < v such that RSZ(u) = k. By the structure of the binary tree, there are at most O(log(n)) different possible sizes of subtrees, so the complexity is O(n*log(n)).

Second, we need to deal with situation (1). Note that the height of the binary tree is at most O(log(n)), there are at most O(n*log(n)) pairs of nodes with ancestor relation, so we can brute force for every single pair.

Therefore, we solved the problem in O(n*log(n)).

Man I almost got D but TLE is kicking my butt.

Though i couldn't solve problem C, i enjoyed thinking about. Any ideas on how to solve it?

Man I have so much work to do, and I left all that in the hopes of giving this contest and solving some nice problems.

Wasted 2 hours of my time, and now I still have work to do. GGs.

In C, we were supposed to take ceil of s/m, given that the least bit of m must be less than or equal least bit of s, then answer exists. What am I missing?

D is too IO-bottlenecked, it's not humane

Is there an easier way to solve E than:

1. Maintaining BITs for prefix / suffix cnt / sum
2. Calculating $$$prefixScore_i = prefixCnt_i \cdot sortedA_i - prefixSum_i$$$ (and $$$suffixScore_i$$$ simularly) using the corresponding BITs.
3. Using BIT + binary lifting to quickly find the i-th currently used position in sorted order ($$$sorted_i$$$).
4. Binary searching on the inflection point of $$$prefixScore_{sorted_i} \gt suffixScore_{sorted_{i + 1}}$$$ and checking adjacent positions for optimality.

It took me like an hour to implement this T_T (though my implementation skills have never been good)

My solution for E got TLE in Python, but after translating it to C++ post-contest, it got AC. Sad for Python users, it’s time to learn C++ I guess.

Otherwise, fun contest!

For C i though check all the bits in S(from MSB to LSB) where there is a one and find all distances after the postion of the one in S to the ones in M bits, if some of those distances have been found before do nothing and if not add the min distance, after that sum up all the unique distances as power of 2. I could not prove why it is incorrect yet it gave me a wrong answer on the last test case in the problem. Can someone help me?

Could any please explain solution to C?

Why? My O(n log n) solution for Problem D got TLE on the 12th test case.364371872

i totally got cooked by C, reaching cm is so tough

Test Cases of D have IO Bottleneck.

My Contest Submission: TLE

Same Solution when attempted with this, worked:

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

Same Solution with Above Code: Accepted

Looks like D has very tight constraints. Can someone explain why my solution https://mirror.codeforces.com/contest/2203/submission/364365602

here gives TLE, whereas I can see similar solutions have got accepted

B was nice

Can someone either prove or disprove my solution for C? If it's incorrect you're welcome to hack it :)

EDIT: This has been answered here.

For D,

https://mirror.codeforces.com/contest/2203/submission/364378879 -this gives tle https://mirror.codeforces.com/contest/2203/submission/364379153 -this doesn't. why?

the only difference in both sol. is a extra set for all elements of b that isn't even used. weird

Most solve it as binary search solution, but actually there is an easier binary observation and this is the simplest approach.

Problem: 2203C - Test Generator Submission: 364327744

Since ai & m = ai, every ai can only use bits that are already set in m. So each ai is formed only from allowed bits of m.

First, look at the lowest set bit in m, which is (m & -m). This is the smallest value any ai can contribute. So if s is not divisible by this value, then it is impossible and the answer is -1. Also if m = 0, it is impossible.

To minimize n, think in binary. Iterate over bits from 0 to 60 and keep:

• sum1: total value of bits of s up to this bit.
• sum2: total value of bits of m up to this bit.

At any prefix, to build sum1 using numbers formed from m, we need at least ceil(sum1 / sum2) numbers.

Take the maximum of this value over all prefixes. That maximum is the minimum possible n.

So the whole idea is just binary counting, no need for binary search.

I have a solution for problem D but I'm pretty sure its not intended to pass.

I factorise the numbers and do some goofy caching to squeeze it under the time limit. I find the primes beforehand and then factorise and generate the factors for each number to tell if Alice can use the number or not.

An explanation of the intended solution would be interesting; or I'm not sure if my solution is intended to pass. I wasn't sure of the exact time complexity because of prime factorising and then constructing the factors for each number is difficult to bound.

E is really cool

Mostly probabilities are kind of disgusting but this one is really nice

But in comp I wrote i instead of n and forgot 1 modulo operation so no score for me :(

What's the reason to set $$$N = 5'000'000$$$ for pF? The TL/ML seems very tight under such constraint :/