Oh~All of us can participate in the Codeforces contest after finishing the Atcoder Beginner Contest,that's so good!

Good luck to all && High rating :D

(Unofficial) I'll do English problem discussion streaming starting from 13:50 UTC (10 minutes after the contest): URL

If you are interested but you are participating in the CF round, check it after the contest!

Problem statements on AtCoder be like

ABCDE is quite easy, F is so hard.

I didn't realized that the contest is not ended yet.

How to solve F? I was thinking with digit dp but was unable to think the states. Please Help

Quick editorial:

• A: Straightforward implementation.
• B: Straightforward implementation.
• C: The answer is a linear combination of the ingredient values. The earlier an ingredient is inserted into the pot, the smaller its coefficient will be in the final sum. So, they should be inserted in non-decreasing order of their value.
• D: Accumulate $$$s_j$$$ = sum of $$$x$$$ over all operations on vertex $$$j$$$. The task is to compute for each vertex the sum of $$$s_j$$$ over all of its ancestors (including itself). We can do it with a DFS on the tree.
• E: Process $$$s$$$ into sorted lists $$$\ell(c) =$$$ the indices at which character $$$c$$$ appears in $$$s$$$. We can use binary searches on these lists to compute $$$f(c, i) =$$$ the first index in $$$s'$$$ greater than $$$i$$$ at which character $$$c$$$ occurs. The answer is $$$f(t[-1], f(t[-2], f(t[-3], \dots f(t[1], f(t[0], -1)))))$$$.
• F: Notice that for $$$y \geq x$$$, $$$(y \textrm{ XOR } x) \geq y - x$$$ and $$$(y \textrm{ MOD } x) \leq y - x$$$. Hence we need $$$(y \textrm{ XOR } x) = (y \textrm{ MOD } x) = y - x$$$. These constraints mean that if we construct the bits of $$$x$$$ and $$$y$$$ from most significant to least significant, they should share their leading bit and the set of "on" bits in $$$x$$$ should be a subset of the "on" bits in $$$y$$$. We can do a DP to construct pairs of digit strings $$$x, y \in [L, R]$$$ having those properties with state: (number of digits placed, has $$$x$$$ diverged from $$$L$$$, has $$$y$$$ diverged from $$$R$$$, has leading digit been placed). The implementation is quite short and perhaps easier to understand.

even though i know memset can fuck me up at times, why do i still use it :|

ps:F anyone ?

How to solve F,it seems to be a math problem

How to solve F?

How to solve E and F?

For Task E, I used Binary Search just like others. But still I am getting TLE in 4 test cases even in C++. I tried to think really hard, but could not find the problem. I would really appreciate if someone can help me in this regard.

~~~~~

include <bits/stdc++.h>

using namespace std;

define ll long long

int main() {

string s,t; cin>>s>>t;

ll n = s.length(), m = t.length();

vector<vector > ids(26,vector());

for(ll i=0;i<n;i++) { ids[s[i]-'a'].push_back(i); }

ll prev = -1, ans=-1, count=0;

for(ll i=0;i<m;i++) {

char a = t[i];

if(!ids[a-'a'].size()) {
  cout<<-1<<endl;
  return 0;
}
else {
  vector<ll> curr = ids[a-'a'];

  ll low = 0, high = ((ll)curr.size())-1, res=-1;
  // cout<<1<<endl;
  if(prev<=curr[0])
    res = curr[0];
  else if(prev>curr[high])
    res = -1;
  else {
    while(low<=high) {
      ll mid = low+(high-low)/2;
      if(curr[mid]==prev){
        res = curr[mid];
        break;
      }
      else if(curr[mid]<prev) {
        low = mid+1;
        res = curr[low];
      }
      else {
        high = mid-1;
      }
    }
  }

  if(res==-1) {
    count++;
    ans = count*n + curr[0];
    prev = curr[0]+1;
  }
  else{
    ans = count*n + res;
    prev = res+1;
  }
}

} cout<<ans+1<<endl; return 0; } ~~~~

For me same problem with E.

I still don't get it why it does not work. I inspected several solutions. They all do more or less the same. But mine does not work :/

Can somebody point me in the right direction, or, once again post the link to the testcases? Thanks!

https://atcoder.jp/contests/abc138/submissions/7001559

PS: And I think that code looks really nice, fairly simple solution ;)

Will test cases be made available?

Problem E can be solved without binary search. My sub

where editorials can be found for this contest??

can anyone please explain logic behind Question D . It will be very helpful

In question D, my BFS solution got AC but now it is failing for 3 test cases added after competition, whereas DFS is getting AC unable to find the glitch, please help. My DFS and BFS codes are given below:

//DFS code: 
#include<algorithm>
#include <iostream>
#include<vector>
// #include<queue>
// #include<string>
#include <iomanip>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

void dfs(int v, int p, long long cost, vvi &a, vector<long long> &c, vector<long long> &up){
   c[v] = cost+up[v];
   for(auto u: a[v]){
       if(u==p) continue;
       dfs(u, v, c[v], a, c, up);
   } 
   return;
}

int main(){
    int n,m;
    cin>>n>>m;
    vvi a(n+1);
    for(int i=0;i<n-1;i++){
        int x, y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    vector<long long> up(n+1, 0);
    for(int i=0;i<m;i++){
        long long x, y;
        cin>>x>>y;
        up[x] +=y;
    }

    vector<long long> c(n+1, 0);

    dfs(1, -1, 0, a, c, up); 
    for(int i=1;i<n+1;i++){
        cout<<c[i]<<" ";
    }

}

//BFS Code :
#include<algorithm>
#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include <queue> 
using namespace std;

int main(){
    int n,Q;
    cin>>n>>Q;

    vector<vector<int>> adj(n+1);

    for(int i=1;i<n;i++){
        int p,c;
        cin>>p>>c;
        adj[p].push_back(c);
    }

    vector<long long> cost(n+1,0);

    for(int i=0;i<Q;i++){
        int v,c;
        cin>>v>>c;
        cost[v] += c;
    }

    queue <int> q;

    int a = 0;
    for(int i=0;i<adj.size();i++)
        if(adj[i].size()>0){
            a=i;
            break;
        }
    q.push(a);
    // vector<bool> vis(n+1,0);
    // vis[a] = 1;
    while(!q.empty()){
        int nc = q.size();
        
        while(nc>0){
            int pa = q.front();
            q.pop();
            nc--;
            long long pc = cost[pa];
            for(int i=0;i<adj[pa].size();i++){
                
                    // vis[adj[pa][i]]==1;
                    q.push(adj[pa][i]);
                    cost[adj[pa][i]] += pc;
                
            }
        }
    }

    for(int i=1;i<n+1;i++)
        cout<<cost[i]<<" ";
    cout<<endl;
}

Is there tutorial part for Atcoder Problem ?