atcoder_official's blog

AtCoder Beginner Contest 408 Announcement
By atcoder_official, history, 16 months ago, In English

We will hold AtCoder Beginner Contest 408.

We are looking forward to your participation!

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

Comments Comments (44)
| Write comment?
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why competitive companion is not working for atcoder problems?????

→ Reply
»
16 months ago, hide # |
← Rev. 3  
Vote: I like it +6 Vote: I do not like it

I wonder if the writers play Genshin? BCG are all repeated question

B

G

→ Reply
  • »
    »
    16 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Sure they play Genshin too much. If not, why do they copy problems which thousands of people passed.

    → Reply
»
16 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Another time

Spoiler

, and another time I couldn't implement at time because I didn't have it on my lib

→ Reply
»
16 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Problem $$$E$$$ seems really standard/common but I'm not able to solve it :(

Is it Dijkstra like d[u][x] = smallest mask with x set bits with which we can reach node u, starting from node n? I got 9 testcases WA with this approach.

Edit: I just read the editorial. What an amazing problem!

→ Reply
»
16 months ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

Why did you kill $$$\mathcal{O}(\log ^2 X)$$$ on G? Going from $$$\mathcal{O}(\log ^2 X)$$$ to $$$\mathcal{O}(\log X)$$$ is only an improvement in specific details of the algorithm, yet not any meaningful improvement.

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can anyone explain problem E i made the distance vector like dist[node][j] it is reprsenting the minimum distance to reach this node with the bit set at position j it is giving wrong please explain i have attatched the code

~~~~~ void solve(){ int n,m; cin>>n>>m; vector<pair<int,int>>adj[n+1]; for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } // vectorleastbitset(n+1,32);

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

q.push({0,1});
vector<vector<int>>dist(n+1,vector<int>(31,LLONG_MAX));
for(int i=0;i<=30;i++){
    dist[1][i]=0;
}


while(!q.empty()){

    int wt=q.top().first;
    int node=q.top().second;
    q.pop();
    bool todrop=true;
    for(int i=29;i>=0;i--){
        if((1LL<<i)&wt){
            if(dist[node][i+1]==wt){
                todrop=false;
                break;
            }
        }
    }
    if(wt!=0){
        if(todrop) continue;
    }

    for(auto it:adj[node]){
        int val=wt|it.second;
        if(val==0){
            dist[it.first][0]=0;
            q.push({val,it.first});
        }
        else{
            bool topush=false;
            for(int i=29;i>=0;i--){
                if((1LL<<i)&val){
                    if(dist[it.first][i+1]>val){
                        dist[it.first][i+1]=val;
                        topush=true;
                    }
                }
            }
            if(topush){
                q.push({val,it.first});
            }
        }

    }
}
int ans=LLONG_MAX;
for(int i=0;i<31;i++){
    ans=min(ans,dist[n][i]);
}
cout<<ans<<endl;

} ~~~~~

→ Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Suppose there are five bits. You are able to arrive node u with a value (01111)2 and (10000)2.

    And then we suppose it is neccesary to add (1<<4) to the answer if we want to arrive node n, than this dijkstra fails to find the best solution because it chooses (01111)2 rather than (10000)2 to arrive node u.

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      no my dist[u][5] will store the distance (10000)2 as minimum my dist[u][j] repreent minimum distance to arrive at node u with the bit set at position j

      → Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I saw the G of today's competition a long time ago. It's a very classic question. However, did atcoder not realize this at all and keep it? I'd like to ask the question setter: Do you play Genshin Impact?

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I don't know how to solve the problem D!!!! I have failed on problem for 7 times!!!

→ Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Using kadane's algorithm, try to pick as many 1 as you can, final ans would be total 1 — max 1s that you could pick (this is 1 — 0 continous count)

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      how did you get this intuition? can you please explain your thought process behind reaching to this solution. thanks in advance.

      → Reply
      • »
        »
        »
        »
        16 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        The question asks for the min number of ops (1 -> 0, 0 -> 1) such that after the ops the array has at most one continous 1s subarray.

        we have 2 options for each existing 1, either let that 1 be 1 in the final answer or else convert it to 0, now to minimize the number of ops, we would want to retain the maximum numbers of 1s.

        In order to retain max number of 1s we have to pick a subarray which has max number of 1s if continous if not then the cost to convert 0 -> 1 which occur in between should compensate against the additional 1s gained.

        eg 11100111, here it would be a better deal to convert 00 -> 11 we will end up do 2 ops but would get 3 1s in return hence profit, so we can calculate whats the max 1s we can retain using kadane algorithm.

        → Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    DP

    → Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

G is a repeated question

G: https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-2187

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve the E problem? can someone help?

Seemed like some sort of Dijkstras, but not sure how to do it.

→ Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Translated Japanese editorial

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thanks for the explaination, understood it was just a greedy 0/1 drop or pick problem over the bits starting from max to min significant and criteria is connectivity.

      → Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it +4 Vote: I do not like it

    I tried to solve it bitwise

    choose any bit position ( pos) and for each edge .. replace that edge with newWeight = ((1<<pos) & weight) > 0)

    this gives a 1-0 graph .. and if you can find a path with 0 distance.. then remove all edges which are not newWeight = 0 at this position ... else set this bit as 1 in the answer and keep all the edges.

    → Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Since we have to minimise OR, it makes sense that we start from the last bit and try to force every bit to become 0. If its possible to make ith bit 0, we will add that bit to our "forbid" variable otherwise we add that to our answer. To check a bit, we can use DSU. Initially, all nodes are in separate regions. Then we will combine any two nodes whose edge does not have any of the forbidden bit. Finally, if 1 and N are in the same component, then this bit can easily be forbidden. Code

    → Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

could anyone explain D ?

→ Reply
  • »
    »
    16 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +7 Vote: I do not like it

    this is how I did it

    suppose the answer is the range l to r

    so flips required = one outside + zero inside

    so we want min ( 1o + 0i) ... where o = outside, i = inside the range l to r

    min (1o + 0i) = min( (total 1) - 1i + 0i) = (total 1) + min( -1i + 0i) = (total 1) - max(1i - 0i)

    so we want to maximize count of 1 - count of 0 inside the range

    so if we replace every 0 with -1 .. then we just need to find maximum sum subarray .. which can be done in O(n) using kadane ( DP storing ans ending at a particular index)

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      can you please help me in finding what case i missed in my solution : https://atcoder.jp/contests/abc408/submissions/66336539

      → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Can you please explain what is wrong in this approach?

      Like we have to find the minimum no of flips required to get atmost one contiguous block of 1s. So I found out the first and last occurrence 1 in the string. Now either you flip all zeroes within this range (lets say flips required is x) or you flip all 1s except the largest contiguous block of 1s. So the final answer is min(x,totOnes-largestContiguousBlockof1s). Why this gives wrong answer? I just can't find any testcase where it fails

      → Reply
      • »
        »
        »
        »
        16 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        can you try this case


        1
2
100110110001

        Correct answer is 3 .. flip 1s at end and 0 in between

        I think your approach will give 4

        → Reply
»
16 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

downvoted. g is an already-existing problem... AGAIN.

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc408/submissions/66352331

hack data

3 5 1 2 16 1 2 2 1 2 3 1 2 4 2 3 4

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please give this contest a down vote.It's full of repeat problems.

Playing Genshin cause it.

→ Reply