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

Oh, sorry, I've missed the bold line

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

same

haha, check my prev div 2

same

ha bhai badhane specialist nu keta keta expert thy jay tu

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

welcome to codeforces

A very Warm Welcome from my Side!

Welcome on Codeforces Hi!

Wish both of us will reach pupil

if u know bubble sort the problem becomes super easy, that is doing swaps of adjacent elements and passing it through the passes as many times as req to sort the array, just apply this process on array a and b and then just count the number of elements which are greater in array a and swap it with corresponding element of array b

Sort both arrays using bubble sort, then if a[i] > b[i] swap. I was able to prove this during the contest. 324898354

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

so its nice if u solved the problem , otherwise bad lol

For every row and column, keep the count of maximum element in it. If you are able to find such r, c such that max_count[r] + max_count[c] — (a[r][c] == max_element) is equal to total count of max element, you can reduce maximum by 1, otherwise you cannot.324845173

Doesn't it feel very standard if one knows how to solve LIS in nlogn.

for me D is harder than E F G H

yeah d was just bubble sort

Mine too is failing:

https://mirror.codeforces.com/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

Solution to E purely greedy 324948524

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://mirror.codeforces.com/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 reason it gives TLE. Use vector <$$$ll$$$> & vec = mp[need]

324934522

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))$$$.