Friendly reminder that Round A starts in less than 24 hours (March 20th, 2022, 4:00 UTC).

Ok, someone please help me understand why do you put subtask 1 for problem D as difficulty div2A. Come on, its "problem D", why do you make it dead simple :/

speedstart

Felt like testcases for problem C were weak. Instead dp my recursion passes both the subtasks.

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

int cases = 0;

void rr() {
  cout << "Case #" << cases << ": ";
}

bool ok;

bool test(string &s, int i, int j) {
  if (i < 0) return false;
  while(i < j) {
    if (s[i] != s[j]) return false;
    i++, j--;
  }
  return true;
}

void solve(int i, int n, string &s) {
  if (i == n) {
    ok = 1;
    return;
  }
  if (s[i] == '?') {
    s[i] = '0';
    int a = test(s, i - 4, i);
    a |= test(s, i - 5, i);
    if (!a)
      solve(i + 1, n ,s);
    s[i] = '?';
  }
  if (s[i] == '?') {
    s[i] = '1';
    int a = test(s, i - 4, i);
    a |= test(s, i - 5, i);
    if (!a)
      solve(i + 1, n ,s);
    s[i] = '?';
  }
  if (s[i] != '?') {
    int a = test(s, i - 4, i);
    a |= test(s, i - 5, i);
    if (!a)
      solve(i + 1, n , s);
  }
}

void test_case() {
  int n;
  cin >> n;
  string s;
  cin >> s;  
  
  rr();
  ok = 0;
  solve(0, n, s);
  
  if (ok) {
    cout << "POSSIBLE";
  }
  else cout << "IMPOSSIBLE";
}

int32_t main() {
  int tt;
  cin >> tt;
  while(tt--) {
    cases++;
    test_case();
    cout << endl;
  }  
  return 0;
}

Did anyone else just write $$$dp[index][gcd(sumOfDigits, prodOfDigits)][sumOfDigits][curSum]$$$.

I think this is close to $$$O(S^{7/3} * |B| * Z)$$$ where $$$Z = number \space of \space digits$$$.

How to solve Palindrome Free Strings for 18 points ??

How many do we have to solve to reach the next round?

For problem D I overkilled with a $$$9D$$$ digit dp solution.

The product of digits will have at max 4 distinct primes in it prime factorization (2,3,5,7). Thus instead of representing the product directly in our dp we can instead represent it as the powers i.e. we can store a,b,c,d such that 2^a * 3^b * 5^c * 7^d is equal to the product of digits.

However this is still not enough.We will still need to optimize further to avoid MLE. To avoid MLE we can note that we don't need that we don't need the full factorization of the product i.e. since the sum can be at max 120 we can store prime factors required for product < 120.

With this optimization our dp table will fit in memory constraints. The states for the dp would be

pos [0,15] -> position from left we are at
small[0,1] -> are we smaller than the input number or equal to it till the i position
start[0,1] -> have we started building the number
zero[0,1] -> is the product of digits equal to 0
two[0,8] -> number of times 2 comes in the prime factorization of the product of digits till now
three[0,6] ->  number of times 3 comes in the prime factorization of the product of digits till now
five[0,3] -> number of times 5 comes in the prime factorization of the product of digits till now
seven[0,3] ->  number of times 2 comes in the prime factorization of the product of digits till now
sum[0,120] -> sum of all the digits till now

My code

Does Kick-Start get progressively difficult from A to E? or this is only a way to number these rounds?