chokudai's blog

By chokudai, history, 7 months ago, In English,

We will hold AtCoder Beginner Contest 138.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

(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!

»
7 months ago, # |
  Vote: I like it +117 Vote: I do not like it

Problem statements on AtCoder be like

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    when you finished the contest in less than 30 min. so you make a meme in free time during the contest

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      And Cheetas like you there to reply

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        i am getting TLE on E problem any solution i am doing it in 1 traversal dont know why ?? please help

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          my first 32 test cases out of 40 get passed & rest of them are giving WA
          :'(

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        when you first time give AtCoder & get rank under 500....#Durgesh the coder

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          same here i have used binary search as well then 40 passed but 8 are giving TLE i dont know why ?? anyone know the solution please share

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yup use c++ i was using python in c++ it passed @chaudhary use c++ it will be passed and do the binary search . not using two loops hope it helps ?

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I was also using python & binary search....sed lyf :'(

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Actually, I didn't participate in the contest.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    In Atcoder infinity is always an even number

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

ABCDE is quite easy, F is so hard.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    getting TLE in both D and E ;(

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are Purple ...but question E is hard for a noob like me

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      E is kinda classical problem, thus is easy to those who have solved similar problem

      PS: F is hard XD

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you give me a link to a problem that is similar to E on a education oriented site. Thanks

»
7 months ago, # |
Rev. 2   Vote: I like it -32 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    even if it is you shouldn't publicize it in midst of contest

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Don't you think it would have made more sense to post this comment after the contest ends? I think you should delete the comment so that others won't gain an unfair advantage.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

»
7 months ago, # |
  Vote: I like it +63 Vote: I do not like it

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.
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    maybe easier to understand without your template...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for the quick explanations.

    In F, could you please explain a little more on 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. I mean how do we infer this? Also what exactly does this mean the set of "on" bits in x should be a subset of the "on" bits in y.. An example would really help! Thanks in advance!

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it +7 Vote: I do not like it

      We need $$$y \geq x$$$ with $$$(y \textrm{ XOR } x) = (y \textrm{ MOD } x) = y - x$$$. $$$(y \textrm{ XOR } x) = y - x$$$ is true when $$$y$$$'s binary representation has $$$1$$$'s in all of the places that $$$x$$$'s binary representation does. $$$(y \textrm{ MOD } x) = y - x$$$ is true when $$$x > y/2$$$, which (in combination with the other requirement) simply means that they should have the same leading bit.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi can you tell what is wrong in my approach I am using DP for problem C just like in matrix chain multiplication.

    Here is my codecode

    I was able to solve D and E but not C can you please help me..

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't think there's a need for dp here.

      I used a greedy approach which is to build a multiset or priority queue and we just can take the minimum $$$2$$$ elements and remove them from the queue and push the new value $$$(x+y)/2$$$ to the queue until we end up with one element only which wil be the answer.

      Code

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the main logic behind taking the smallest element first is that every time you take two number and add it's sum to by taking half to another number the relevance of first number to your new sum becomes 1/4 then 1/8 then 1/16 .......and so on. that's why u would always like to decrease the smallest u have and add the largest numnber to your answer as here u want the sum to be maximum if they would have asked for minimum u would have gone another way round.that's why the approach of using priority_queue, multiset or sorting works. I hope this helps

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understand that but why does dp give wrong answer??

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think your solution is not standard, this problem just sorts arrays and solve

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are using false negatives, you could have simply said that my solution is not standard but now it seems as if you mean to say that my solution is standard ??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

ps:F anyone ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E and F?

»
7 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

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; } ~~~~

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I think its because of vector cur = ids[a -'a'] if there is 10 ^ 5 elements in ids[a — 'a'] and copying it 10 ^ 5 times from ids[a — 'a'] will be TLE, i think you can binary search for just ids[a — 'a'] without creating new array

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You so much. If you would not have told this, I would have been still wondering and be in doubt. Thank You really.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E I have thought of an idea using like most have said binary search but i AM GETTING RE and I don't know why

Can somebody please help me understand my mistake

https://atcoder.jp/contests/abc138/submissions/7006506 Atcoder

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ;)

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    You are doing upper_bound every time

    Let's check this test case

    s = contesc, t = c

    in line 53 you take ll ans2 = 0, and in this test case your answer would be 7 instead of 1

    You need to take ans2 as -1 in the start

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will test cases be made available?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Test cases are usually published weeks to two months later.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E can be solved without binary search. My sub

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This is O(n^2). Looks like testcases are weak chokudai

    Testcase
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where editorials can be found for this contest??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one give tutorial for Problem D and E

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Some test cases were added after the contest for problem D to deal with particular cases which vertex ai is not a parent of bi. So some codes on AC list are not useful anymore.

e.g. V = {1, 2, 3}, E = {1-2, 2-3}

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong is this submission for Problem E ?? https://atcoder.jp/contests/abc138/submissions/7016567 Thank you.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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;
}
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does your BFS solution fail because of Time Limit? Or Wrong Answer?

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it

      Wrong answer. I understood the problem with my bfs code. The tree is undirected and rooted at 1. So, in my adjacency list I should push both x-y and y-x and keep track of visited. Updated solution with BFS.

      #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);
              adj[c].push_back(p);
          }
      
          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;
      
          q.push(1);
          vector<bool> vis(n+1,0);
          vis[1] = 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++){
                          if(!vis[adj[pa][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;
      }
      
  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    In DFS code, you linked both (a[x], a[y]) and (a[y], a[x]), though only (a[x], a[y]) in BFS one.
    Additional testcases represent a tree structure like "1-3-2" (V = {1, 2, 3}, E = {(1, 2), (2, 3)}), which x isn't a parent of y.

    Try the case below. AC is "1 3 1" and DFS returns it but your BFS return "1 2 1".
    3 2
    1 3
    2 3
    1 1
    2 2

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks I just realized that mistake.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I finally know where I am wrong, I thought the data was given by the structure of the tree....

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I actually used dfs timer to convert the tree into an array, then did the prefix sum trick.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please tell me where are the editorials?

»
7 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

They should provide editorials in English, how to solve d?

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Is there tutorial part for Atcoder Problem ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I'm getting WA with This submission, any help?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need help in problem D.I got tle error My submission