AtCoder Beginner Contest 408 Announcement

16 месяцев назад, скрыть # |

← Rev. 3 →

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!

→ Ответить

neatisaac

16 месяцев назад, скрыть # ^ |

No,just DSU :D

→ Ответить

16 месяцев назад, скрыть # ^ |

can you explain your solution please?

→ Ответить

neatisaac

16 месяцев назад, скрыть # ^ |

maintain an edge set, let $$$i$$$ from $$$30$$$ to $$$0$$$ and connect an edge if it is in the set and it is $$$0$$$ at binary digit $$$2^i$$$.if $$$1$$$ and $$$n$$$ are in the same block,it is ok and we narrow the edge set.if not,add $$$2^i$$$ to answer.

→ Ответить

chromate00

16 месяцев назад, скрыть # |

-7

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.

→ Ответить

3a51

16 месяцев назад, скрыть # ^ |

← Rev. 2 →

I agree, thought $$$O(\log^2)$$$ can pass it and got TLE 5 times.

→ Ответить

bhavya_19

16 месяцев назад, скрыть # |

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;

} ~~~~~

→ Ответить

Michael-Li

16 месяцев назад, скрыть # ^ |

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.

→ Ответить

bhavya_19

16 месяцев назад, скрыть # ^ |

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

→ Ответить

wenlebo

16 месяцев назад, скрыть # |

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?

→ Ответить

qizhonglei

16 месяцев назад, скрыть # |

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

→ Ответить

16 месяцев назад, скрыть # ^ |

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)

→ Ответить

mathsdevil

16 месяцев назад, скрыть # ^ |

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

→ Ответить

16 месяцев назад, скрыть # ^ |

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.

→ Ответить

16 месяцев назад, скрыть # ^ |

→ Ответить

KaitoKIDO

16 месяцев назад, скрыть # ^ |

or maths and Prefix Sum

→ Ответить

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

16 месяцев назад, скрыть # |

G is a repeated question

→ Ответить

16 месяцев назад, скрыть # |

How to solve the E problem? can someone help?

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

→ Ответить

Translated Japanese editorial

16 месяцев назад, скрыть # ^ |

→ Ответить

16 месяцев назад, скрыть # ^ |

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.

→ Ответить

ashish1729

16 месяцев назад, скрыть # ^ |

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.

→ Ответить

16 месяцев назад, скрыть # ^ |

Thanks bro, got it.

→ Ответить

16 месяцев назад, скрыть # ^ |

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

→ Ответить

16 месяцев назад, скрыть # ^ |

got it thanks.

→ Ответить

Ylandolsi

16 месяцев назад, скрыть # ^ |

if (u < it.first) {

why do you have this condition ?

→ Ответить

16 месяцев назад, скрыть # ^ |

For example nodes 3,4. I will just compare 3 and 4 and not compare 4 and 3 since it will be redundant.

→ Ответить

Ylandolsi

16 месяцев назад, скрыть # ^ |

yea but its useless

→ Ответить