Hope to reach Specialist And complete my goal one month earlier In the bottom of the table....

Don’t worry it is probably ok because the non div 3 people were div 3 once too (probably)

haha, check my prev div 2

same

1-1-1-1-1-1-1-1

Use bubble sort , one thing i found more useful is

normally we say that bubble sort takes n^2 time complexity but in real it takes max (n)*(n+1)/2 in question n was max 40 so for the both the arrays this will pass

initial i thought that 2 (for both array )* n^2 (i assumed that bubble sort is n^2) operation will need and i was confuse to solve it later i realized bubble sort requires less then n^2 operation

it is very very good problem , you can check my submission

for me D is harder than E F G H

yeah d was just bubble sort

Mine too is failing:

https://codeforces.me/contest/2121/submission/324969264

Idea is it maintain a inverted fenwick tree on max as I iterate from left to right.

And then do binary search over indices.

Not sure what the dp solution is. I did it as follows:

Start comparing digits of l and r from most significant to least significant and find the longest common prefix. The number x will need to have the same digits here. If the length of this common prefix is p, then 2*p is added to ans.

Now for 1st mismatch in digits of l and r, if digit.r > digit.l + 1, then we can construct x with no more common digits to l and r. In this case 2*p is the final ans.

Otherwise, there are 2 cases:

1. assign digit.r to x. For all the immediately following 0's in r, x's digits will also be 0. If number of following 0's are q, then q+1 is added to ans.
2. assign digit.l to x. For all the immediately following 9's in l, x's digits will also be 9. If number of following 9's are r, then r+1 is added to ans.

So ans = 2*p + min(q+1, r+1)

A purely greedy / constructive solution in O(number of digits): 324911040.

I solved it without dp It wasn't a hard problem but there were a lot of small points! I hope this code helps you:

int ans=0;
bool khosh=false;

for(int i=0; i<n; i++) {
  if(res1[i]==res2[i] && khosh==false) {
    ans+=2;
  } else if( abs(res1[i]-res2[i])==1 && khosh==false) {
    ans+=1;
    khosh=true;
  } else if( res1[i]=='9' && res2[i]=='0' ) {
    ans+=1;
  } else {
    break;
  }
}

n is the number of digits and res1, res2 are the input numbers that I received as strings

see my Solution Purely Greedy we st

Here is my solution using DP. I am not sure if it is optimized properly, but it got accepted.

The goal is to minimize:

f(l, x) + f(x, r)

We solve this using digit DP. The DP state tracks:

• The current digit index
• The digit chosen at this position
• The state of x relative to l and r

DP State Definition

dp[i][d][s]: Minimum matches when

• i: Current digit position (from most to least significant)
• d: Digit placed at position i
• s: Current state of x:
  • 0: Equal to l only
  • 1: Equal to r only
  • 2: Equal to both l and r
  • 3: Strictly between l and r

Base Case

At the most significant digit p:

• If l[p] == r[p], we initialize dp[p][l[p]][2] = 2
• If l[p] != r[p], we initialize:
  • dp[p][l[p]][0] = 1
  • dp[p][r[p]][1] = 1
  • For digits in (l[p] + 1, r[p] - 1), set dp[p][d][3] = 0

Transitions

Loop from position i = p-1 down to 0, and try all digit/state transitions:

1. From state 0 (equal to l only):

   • Stay in 0 if current digit is l[i] (add +1)
   • Move to 3 if digit > l[i] (add +0 or +1 if digit also equals r[i])

2. From state 1 (equal to r only):

   • Stay in 1 if digit is r[i] (add +1)
   • Move to 3 if digit < r[i] (add +0 or +1 if digit also equals l[i])

3. From state 2 (equal to both l and r):

   • If l[i] == r[i], stay in 2 and add +2
   • Otherwise:
     • Move to 0 if digit is l[i] (add +1)
     • Move to 1 if digit is r[i] (add +1)
     • Move to 3 if digit is between (add +0)

4. From state 3 (strictly between):

   • Any digit is allowed
   • Add +1 if digit matches l[i] or r[i]

Final Answer

Minimum of all values dp[0][d][s] over all digits d and states s

Implementation Code: 324944536

this is actually crazy, might be the worst div3 i ever participated in

I did G as follows:

Define a function g(l, r) as the minimum of frequency of 0 and 1 in s[l...r]

f(l, r) + g(l, r) = r-l+1 It is easy to find summation of f(l, r) $$$-$$$ g(l, r) over all (l, r). For the given string, keep a prefix array p with p[i] = number of 0's in s[1...i] $$$-$$$ number of 1's in s[1...i].

f(l, r) $$$-$$$ g(l, r) = abs(p[r] $$$-$$$ p[l-1]).

The rest is just computing sum of abs(p[x] $$$-$$$ p[y]) over all (x, y) which can be done by sorting p.

For problem H: You can extend standard LIS algorithm for this question whose implementation is very simple (just 3-5 lines of code using multiset).

Submission link: https://codeforces.me/contest/2121/submission/324947588

I have a divide and conquer solution for G

~~~~~
#pragma GCC optimize("O3") 
#include 
using namespace std;
#include 
#include 
using namespace __gnu_pbds;
using ordered_set = tree<
    int,
    null_type,
    less_equal,
    rb_tree_tag,
    tree_order_statistics_node_update
>;
#define _USE_MATH_DEFINES
#include 
#define sahil_ki_mkc cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define int  long long
#define F first
#define S second
#define pii pair
#define ppp pair
#define dout cout << fixed << setprecision(15)
#define lc (2 * id)
#define rc (lc + 1)
const double PI = 3.14159265358979323846;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (int)5e5 + 10;

char a[maxn];
void solve(){

 int n; cin >> n;

 for(int i = 0 ; i < n ; i++){
    cin >> a[i];
 }

 int ans = 0;

 ans += n * (n + 1) * (n + 2);

 ans /= 6;

 vector diff(n,0);

 for(int i = 0 ; i < n ; i++){
    diff[i] += a[i] == '1';
    diff[i] -= a[i] == '0';

    if(i) diff[i] += diff[i-1];
 }

auto dnc = [&](int l,int r,auto&& dnc)->int{

 if(l > r) return 0;

 if(l == r){
    return abs(diff[l]);
 }

  int here = 0;

  int mid = (l + r) / 2;

  here += dnc(l,mid,dnc);

  here += dnc(mid+1,r,dnc);

  vector v;

  for(int i = l ; i <= mid ; i++){
     v.push_back(diff[i]);
  }

  sort(all(v));

  vector pref(v.size());

  for(int i = 0; i < v.size() ; i++){
       pref[i] += v[i];
      if(i) pref[i] += pref[i-1];
  }

  int tot = 0;
  for(int i = mid + 1 ; i <= r ; i++){
       int here1 = 0;
       tot += diff[i];

       auto idx = upper_bound(all(v),diff[i]) - v.begin() - 1;

       if(idx >= 0) here1 += pref[idx];
       
       here += (idx + 1) * diff[i];

       here -= here1;

       here += pref.back() — here1;

       here -= (v.size() — 1 — idx) * diff[i];

  }

  return here;


};


ans += dnc(0,n-1,dnc);

cout << ans / 2 << " \n";

}

signed main()
{
    auto begin = std::chrono::high_resolution_clock::now();

    sahil_ki_mkc;
    
    int tt=1;
    cin >> tt;
    while(tt--){
       solve();

    }

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast(end — begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";

    return 0;
}
~~~~~

vll &vec = mp[need];

This is the only change you need to do, you need to access vector by reference, otherwise it will take O(size of vector) time to access the vector from the map, using &, you can do it in O(1).

You brute forced over all candidates, which is $$$O(n^2\log(n))$$$. You could use binary search to reach $$$O(n\log^2(n))$$$.

exactly same here, wasted a bunch of time because of lacking experience.

It can be solved by sparse table or without one also can. I've done both but... after contest))

you have to wait for the system testing to finalize the rankings then it will be reflected on your account

The idea is this: consider the maximum value in the grid, call it $$$X$$$, and look at all of the cells which have value $$$X$$$. If it is possible to choose a row and column that encapsulate all of these cells, then that becomes the optimal choice and the answer is $$$X - 1$$$. Otherwise, the answer is $$$X$$$.

There are a few ways to do this; the important part is NOT writing a $$$O(N^2M)$$$ or $$$O(NM^2)$$$ solution. If you do, you'll TLE to test cases with large $$$N$$$ or $$$M$$$, respectively.

My solution takes advantage of one property: assume that we can encapsulate all of the cells containing the value $$$X$$$. Pick any one of these cells (it doesn't matter which) — we will have to use either its row or column in the optimal choice. Assume we use its row; consider the set of cells with value X not on this row. If they all belong on the same column, it works. Otherwise, it doesn't. Swap the rows and the columns for the other case. Since there are at most $$$NM$$$ cells containing the maximum value X, this solution runs in $$$O(NM)$$$ time. You can check my solution for implementation.

Na , u can not expect

you'll be receiving a penalty because you cheated during this round using AI... really well done dude

You still can; just go to the leaderboard, find a user's row, then Ctrl + click on a cell in that row to see the results. From there, you can click once more to find the original submissions.

its already up. Dont know why the author hasn't given the link, but this https://codeforces.me/blog/entry/143822 it the editorial.

tutorial posted here