Problem C can be solved in O(h) aswell :D.

Here is my solution: 9530015

('D' means you are/ you want to go on the right son and 'S' means you are / you want to go on the left son)

507C done in O(h) and challenge part can also be done in O(h) using the similar logic my Solution 9530023

Thanks a lot... I have find my solution.

Problem E could be also solved with a bfs to mark the level of each node, and a dijkstra from node n to node 1, following the bfs tree, with cost of edges 0 or 1. It's time complexity is O(|E| * log |E|), but it's still good enough.

An interesting round... though I nearly solved E...:P (but failed in the end...T T)

Finally blue :) Yay!

Has someone tried to solve problem C "backwards"? As in generating it's path back to the root? Couldn't you calculate the answer as move up to the root summing up the size of subtree rooted at it's sibling (in case it's sibling happens to be visited first with the given traversal in the problem statement)? Also, is valid to consider that it's sibling is visited first only if the actual node we're currently on has the same parity (odd or even) as it's father (if you label them from 1 to 2^h+1 from left to right as you move to lower levels of the graph)?

I hope I made myself clear, any ideas are welcome.

Problem C can be solved in O(h) time. This was a really good question and my approach is stated below. The problem first requires you to convert (n-1) to its binary form (we took n-1 since we want to number the leaf nodes starting from 0). Next we observe that the binary conversion of (n-1) gives you the location of the node from the parent tree . Example if h=3 and n=6 we want to reach the leaf numbered 5 (taking 0 as the starting first leaf).

Converting 5 to its binary form, we get 101 What the number 101 tells us is that we reach this node by taking the path R-L-R. We then observe that the first element tells us if we have to take a right. But according to the pattern given we must traverse the left side of the tree. This would consist of (2^h)-1 (number of nodes on the left part of the parent node) nodes and 1 node (the parent itself). So in the first step we add 2^h to the number of nodes visited.

Now, we look at the next bit. In the previous step, since we already took a right we should take a left according to the guessing pattern given in the question. Even in the RLR pattern we observe for the number 5, we have to take a L so we mark the present node is visited by adding only 1 this time. This process continues till you reach the leaf of the tree.

To get a better understanding you can see my code in the link shown(I have written the necessary comments to help make it easier to read my code) http://codeforces.net/contest/507/submission/9531335

Now answering the challenge question to C if we want to solve the question for "LRRLLRRRLRLRLRR..." We repeat the process by converting n-1 to its binary form and proceed with the above algorithm by taking the new string into consideration. A pointer to the present index of the string would suffice. Thus, we can solve the challenge question in O(h) time as well.

Green again :-)

O(h) Gentle solution of С using bit manipulation in Java:

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int h = in.nextInt();
        long n = in.nextLong() - 1;
        long res = 0;
        for(int i = h - 1; 1; i >= 0; i--) {
            if ((n >> i & 1L) == 1) {
                res += 1L << i + 1;
            } else {
                res += 1;
                n = ~n; //inversion
            }
        }
        out.println(res);
    }

In problem E: how can we find the shortest path from 1 to x and the shortest path from x to n in time?

For problem E, I have another solution.

• Initially, let k be the number of usable roads, hence the ones we must destroy if we don't use it.
• Consider any path from 1 to N. If we use a usable road, we must subtract 1 from k, since we won't need to destroy it. If we use a broken road, we need to add 1 to k, since we'll need to repair it.
• We can solve it with Dijkstra. But we have the problem that we also want a path with minimum number of edges, so we can simply assign a cost of 10⁵ + 1 to each edge, that way we'll make sure that the shortest path Dijkstra finds will be one with the shortest number of edges. Additionally, using a broken road will cost 10⁵ + 2 while using a usable road will cost 10⁵. That way, in case of a tie in number of roads, the path where the minimum number of roads have to be demolished in the end will prevail.

My solution: 9530019

can any one tell me what is wrong with my solution to problem D ??

http://codeforces.net/contest/507/submission/9533089

I didn't understand the idea for problem D. How did you come up with such solution? I have an idea for the problem though it didn't produce the right answer right from test #3. Let's define dp[i] the number of suffixes y with length i such that and there is no true suffixes of y that divides k. Also we define cal[i][j] as suffixes y' with length i and . Also all suffixes y' have no suffix that divides k.

First we calculate cal[1][j] by trying out all numbers from 1 to 9. Then set dp[1] as cal[1][0] and we set the base value cal[i][0] = 1 (0 only). Then, for general i, j we shall have

(P[i][j] = number of indicies of )

Therefore the answer will be

Of course, all of them would be modded by m when actually coded. Please correct me if i'm wrong. Thank you all!

Why count(n,0) = 1 in 507D? There are more than 1 n-digit number divisible by k aren't there?

The one problem that i face is that i am unable to calculate the square root of the number in gcc(compiler). math.h file contain the function but math.h cannot be linked to code. how to resolve that problem i want to look at the solution which are submitted by the other in c.

I didnt understand the purpose of binary search in 507-B solution link provided in editorial...can anyone please explain...as suggested in editorial, we could have simply got the answer by ceil(dist/2*R).

can anyone elaborate on the solution of problem D-the maths lecture...

Here's really simple solution for problem C: http://codeforces.net/contest/507/submission/9522115 (in O(h))

very bad round the problems were easycoding and not interesting

In problem E — we actually don't need to know whether some node lies on shortest path or not; there are also different possible solutions with Dijkstra's algorithm described in comments, but you also don't need it. Solution with a single BFS sounds simpler.

Here is the idea — you can calculate values of dynamic programming right inside this bfs. If you'll store number of bad edges in shortest path to given vertex, along with length of this path — you will have answer for a problem after running single bfs from vertex 1 to vertex n.

My solution 9516327 from a contest works this way.

Nice :)) thanks a lot:))

I think the complexity of problem D is O(n*k*10)

What's the use of boolean change in 9529210 (D-Maths Lecture). I think it's used just to check that do we have atleast one non-zero number in the suffix so far?.

Also the condition if(ind == n || (rem == 0 && change)) return 0; can be if(ind == n) return 0;. because if (rem==0&&change) is true we must have already return-ed from above.

Can I categorize it as Digit-DP?

I have difficulty comprehending

We want to avoid repetition so by constructing the number from the right to the left when we reach a state with j = 0 with suffix  ≠ 0 we return the answer immediately so any other suffix that contains this suffix won't b calculated.

Can someone explain to me what this means?

507E Use 2 BFS one from 1 and other from n,mark the valid vertices then use 0-1 BFS.

Use double instead of float in B.... I was getting WA in test case 37..just saying if someone does the same in future.

I think I have a unique solution for c P.S. I didn't read the editorial yet.. hope I didn't waste your time

I did this in E problem : Made a set of pair<pair<int, int>, int> which stores {{distance from 1, no. of bad roads in the shortest path from 1}, node}. Thus, I have for every node, the min distance and the minimum no. of bad roads in shortest path from 1.

Now, I am tracing back from n and going to the node (say p) which has a distance of 1 less (distance from node 1) than the prev node and among all of the nodes satisfying the condition, I am choosing the one which has the least bad roads in the path from 1. if i am encountering a good road in this path i am removing it from the list of roads to blast. if i encounter a bad road, i am adding it to the list of roads to mend.

But it is giving wrong answer on test 22. Seems like my approach is changing 1 road extra than the answer provided.

I am not able to figure what's wrong in this approach. Can someone please help? 278717886

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#define intt int64_t 
 

void solve()
{
    intt n, m;
    cin>>n>>m;
    intt a, b, c;
    vector<vector<pair<intt, intt>>> v(n+1);
    set<pair<intt, intt>> good, ngood;
    for(int i=0;i<m;i++) 
    {
        cin>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        if(a>b) swap(a, b);
        if(c==1) good.insert({a, b});
    }
    
    set<pair<pair<intt, intt>, intt>> q;
    // {{distance from 1, bad roads in shortest path}, node number}
    q.insert({{0, 0}, 1});
    vector<intt> dis(n+1, 2e9), sp(n+1, 2e9);
    dis[1]=0;
    sp[1]=0;

    // dijkstras with (priority : min distance > min bad roads)
    while(!q.empty())
    {
        auto k = *q.begin();
        q.erase(q.begin());
        if(dis[k.second]<k.first.first) continue;
        else if(dis[k.second]<k.first.first and sp[k.second]<k.first.second) continue;
        for(auto i:v[k.second])
        {
            if(dis[k.second]+1<dis[i.first])
            {
                dis[i.first]=dis[k.second]+1;
                sp[i.first]=sp[k.second];
                if(i.second==0) sp[i.first]++;
                q.insert({{dis[i.first], sp[i.first]}, i.first});
            }
            else if(dis[k.second]+1==dis[i.first])
            {
                if(i.second==1 and sp[k.second]<sp[i.first])
                {
                    sp[i.first] = sp[k.second];
                    q.insert({{dis[i.first], sp[i.first]}, i.first});
                }
                else if(i.second==0 and sp[k.second]+1<sp[i.first])
                {
                    sp[i.first] = sp[k.second]+1;
                    q.insert({{dis[i.first], sp[i.first]}, i.first});
                }
            }
        }        
    }
    intt curr = n;
    while(curr>1)
    {
        intt mn = 2e9, z;
        for(auto i:v[curr])
        {
            if(dis[i.first]==dis[curr]-1 and sp[i.first]<mn) z = i.first;
        }
        if(z<curr)
        {
            if(sp[curr]-1==sp[z]) ngood.insert({z, curr});
            else if(sp[curr]==sp[z]) good.erase({z, curr});
        }
        else
        {
            if(sp[curr]-1==sp[z]) ngood.insert({curr, z});
            else if(sp[curr]==sp[z]) good.erase({curr, z});
        }
        curr = z;
    }
    intt ans = good.size();
    ans += ngood.size();
    cout<<ans<<"\n";
    for(auto i:good) cout<<i.first<<" "<<i.second<<" 0\n";
    for(auto i:ngood) cout<<i.first<<" "<<i.second<<" 1\n";
}
 
int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}