G Tutorial is not available?

In Problem G, I'm getting WA on test 12. Please help me out. 52149636

Why is problem D tagged as dfs and similar?

Interesting idea on E, very cool problem!

Solving E problem using Python gave TLE, don't know why. I stored the Number as int(base 26). Shouldn't it work?

У меня, кажется, третий вариант решения G:

Пусть dp[i] — минимальное значение последнего элемента возрастающей последовательности, если элемент i принадлежит убывающей. Посмотрим, как нужно его обновлять:

• из предыдщего элемента: всё просто, если $$$a[i - 1] < a[i]$$$, то $$$dp[i] = dp[i - 1]$$$

• если предыдущий элемент не из убывающей, то нам подойдут все такие $$$j$$$, что между $$$j$$$ и $$$i$$$ массив строго возрастает, $$$dp[j] < a[j + 1]$$$ и $$$a[j] > a[i]$$$. Само $$$dp[i]$$$ теперь станет $$$a[i - 1]$$$. Сооствественно, для релаксации в этом случае, нам достаточно лишь существования подобного перехода. Для его быстрой проверки заведем ДО по значениям, куда будем записывать все такие $$$j$$$, что $$$dp[j] < a[j + 1]$$$ и запрашивать максимум на отрезке $$$[a[i] + 1, maxval]$$$, а после проверять, дейсвительно ли от полученного индекса $$$val$$$ до $$$i$$$ все значения строго возрастают. В реализации я это проверял массивом $$$lst$$$, где $$$lst[i]$$$ — максимальный индекс, в котором нарушается убывание слева от $$$i$$$

Код : 52119835

I don't understand E's editorial,can anyone please explain?What are we doing? I thought of seeing the string as base 26,so we can convert it into decimal and take the mean. For example: az = 26^0*25 + 26^1*0 = 25, bf = 26^0*5 + 26^1*1 = 31 now taking the mean we get 28,converting into base 26 we get 12 (26^0*2+26^1*1 = 28),which is bc. But for large string lengths we may have to do 26^100000,so I thought it is not feasible. What are we doing in this editorial?

This is a real Div.3 :)

Another solution to G by considering whether the max.element in the array is in the decreasing or increasing subsequence:52159992

anyone please help. In problem F, why my code give me Runtime Error on test 15?.

My Submission: 52160039

Runtime error in F: can someone help me debug: https://codeforces.com/contest/1144/submission/52208937

for E:someone plzz explain how division by 2 is done in 26 base

for (int i = 0; i <= k; ++i)

{

    int rem = a[i] % 2;

    a[i] /= 2;

    if (i + 1 <= k) {

       a[i + 1] += rem * 26;

    } else {

       assert(rem == 0);

}

problem ID:1144F

problem F is also done by BFS

problem F code(happy coding)

Can I solve E using big integer?

for problem g is this correct approach? let say i have two array X(increasing),Y(decreasing) and A is Merge(X,Y). Find the longest increasing sequence of A this sequence will contain X and atmost one element of Y and after removing that element from Y Y will still remain decreasing.

Why is this solution for E giving TLE? https://codeforces.com/contest/1144/submission/52223063

there is a another way to solve problem G
first we found the LIS of the array and then there is a fact : if we can split the given sequence a into one increasing sequence and one decreasing sequence then at most one of the elements of the LIS could not appear in x ( x is the increasing sequence ) otherwise in the y ( the decreasing sequence ) we have two numbers A , B which a[A] < a[B] and A < B and its impossible so if we fix which index i is not gonna appear in x we can solve the problem

In problem E, why is it only allowed to do a[i] %= 26 when i > 0?

For this test case, for example:

6

nijfvj

tvqhwp

The sum in the base 26 is: 33 3 25 13 17 24

Why is it allowed to have this "33" in the first position?

Help me! I dont understand print problem F in tutorial: cout << (color[e[i].first] < color[e[i].second]); ???????????? please

In editorial 'G',what is the meaning of 'maximum possible minimal'?

Somebody please tell me why this submission 52323233 works but this submission 52321524 does not ??

The only difference in both the codes is that in accepted one, I've accepted the input as strings while in wrong answer I've accepted them in character arrays

Первый раз увидел на контестах длинную арифметику. Когда залил на питоне Медианную строку и увидел TL, подумал, что решение состоит в другой идее)

I can not understand the tutorial of problem G.

Please anyone Explain the tutorial.

In problem F,the solution does not include the visited array.So,won't it end in a infinite loop and give tle as it will keep on checking two vertices again and again?

But I my opinion , the statue may be dp[0][i] represent that "The i-th element is in increasing sequence and the max possible element in the decreasing sequence",and dp[1][i] represent that "The i-th element is in decreasing sequence and the min possible element in the increasing sequence" May be I am Wrong ,But I hope you can correct my mistake , Thank you

Problem F
Why does this give TLE??

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

#pragma GCC optimize "trapv"
#define ll long long
#define nline cout << "\n"
#define nl "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb(x) push_back(x)
#define pii pair<int, int>
#define db(str, x) cout << str << " = " << x << nl;
#define dbv(a)        for(auto it: a)cout<<it<<" "; cout << nl;
#define db1(a)        cout<<a<<"\n";
#define db2(a,b)      cout<<a<<" "<<b<<"\n";
#define db3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<"\n";
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);

const int M = 1e9+7;
const int N = 1e5;


int dfs(int u, vector<int>& color, set<pii>& edges, vector<vector<int>> adj){
  for(int child : adj[u]){
    if(color[child]){
      if(color[child] == color[u])
        return true;
    }
    else{
      if(color[u] == 1){
        color[child] = 2;
        edges.insert({u, child});
      }
      else{ 
        color[child] = 1;
        edges.insert({child, u});
      }
      if(dfs(child, color, edges, adj))
        return true;
    }
  }
  return false;
}

void solve(){
   int n, m;
   cin >> n >> m;
   vector<vector<int>> adj(n);
   vector<pii> tmp;
   int x, y;
   for(int i=0; i<m; i++){
      cin >> x >> y;
      x--,y--;
      adj[x].pb(y);
      adj[y].pb(x);
      tmp.push_back({x, y});
   }
   vector<int> color(n);
   set<pii> edges;
   color[0] = 1;
   
   if(dfs(0, color, edges, adj)){
    db1("NO");
   }
   else{
    db1("YES");
    for(auto pr : tmp){
      if(edges.count(pr)) cout << 0;
      else cout << 1;
    }
    nline;
   }
  
}

int main(){
  fastio()
  #ifndef ONLINE_JUDGE
  freopen("Input.txt", "r", stdin);
  freopen("Output.txt", "w", stdout);
  #endif

  int t=1;
  // cin >> t;
  for(int tc=1; tc<=t; tc++){
    solve();
  }
  
  return 0;
}