I have not done grid paths, but I did not require any optimization in Knights tour. I just used Warnsdorf's rule.

Thanks. ibit gave me the solution. The bound is pretty tight so you have to remove the redundant cases. The optimization you made of returning 0 when reaching vertex n, actually reduces the runtime by more than half and does the trick. Bottom Up or Top Down does not make any difference.

I have used the same algorithm. However something in my implementation gives TLE.

You can go to settings in talk to block a user. I don't think you can hide from a user. And your handle can only be changed once during New Year.

Hotel queries can be done in O(mlogn).

Instead of using binary search, we will descend the Segment Tree, starting at the root vertex, and moving each time to either the left or the right child, depending on which segment contains the vacancy greater than the required rooms.

ll get(ll val,ll v=1,ll tl=0,ll tr=n-1)
{
    if(val>tree[v])
        return -1;
    
    if(tl==tr)
        return tl;
 
    ll tm=(tl+tr)/2;
 
    if(tree[2*v]>=val)
        return get(val,2*v,tl,tm);
    else
        return get(val,2*v+1,tm+1,tr);
    
}

Here: https://mirror.codeforces.com/blog/entry/70018?#comment-548451

For Tree Distances I

max_distance[u] = max(distance_from_diametric_end1[u], distance_from_diametric_end2[u])

Is there any proof for this?

I implemented the same solution. It passed all tescases.

Check whether the Graph is Bipartite. A graph with an odd cycle can never be bipartite.

You can do this by running a BFS and coloring the odd and even levels with two colors. If you find any adjacent nodes with the same color, this means they are starting and endpoints of the odd cycle. Run another BFS/DFS to find the odd cycle.

I also thought the same thing.

• Most of the time I can think of the problem in my solution. But sometimes, no matter how hard I try, I cannot come up with testcases where my solution fails. In such situations, I have to turn up to others to figure out the problem. Although the codeforces community is really helpful, this method is not always reliable.

• 10^5 numbers are not possible to display. Hence, I am asking for a file that we can download. CSES has that feature.

• The CF judge usually tells us which testcase is wrong. Hence, it is not that hard to filter out. Even if it is not, we can build our own checker to filter out the wrong testcases.

Instead of using vis array, maintain a status array with 3 states: 0-unprocessed, 1-processing, 2-processed. If during the traversal you encounter a child with state 1 then there exists a cycle.

I use this implementation. It is from this book.

for (int i = 1; i <= n; i++) distance[i] = INF;
distance[x] = 0;
q.push({0,x});
while (!q.empty()) {
    int a = q.top().second; q.pop();
    if (processed[a]) continue;
    processed[a] = true;
    for (auto u : adj[a]) {
        int b = u.first, w = u.second;
        if (distance[a]+w < distance[b]) {
            distance[b] = distance[a]+w;
            q.push({-distance[b],b});
        }
    }
}

I calculated the complexity. Shouldn't it be O(k(m+nlogn))?. It is still giving me TLE for the above algorithm.

Secondly, why did you run a classical djikstra before? you are not using the distance array in the algorithm.

13) flight routes give TLE as its O(nmk)

Thanks! I was having the same problem.

You can refer to this for STL algorithms

Thanks, man. But figuring out the appropriate testcases is the hard part. I guess it will get better with practice. I usually face problems when the sample cases are not strong.

Thanks a lot!

Auto comment: topic has been updated by sarkarasm (previous revision, new revision, compare).

Auto comment: topic has been updated by sarkarasm (previous revision, new revision, compare).

Can anyone tell what is wrong with my solution?

86348075

You can easily prove this by contradiction. Assume there is no more moves possible and the string has both 0 and 1. But if both 0 and 1 exist then there must be at least one 0 with 1 as its adjacent neighbor and vice-versa.

Hence the opposite only wins when there is only 1 or 0 in the string.

Here is my approach and explanation for E1[problem:1371E1]

As Yuzu starts with x candies, we know the number of candies in each position of the array, i.e, x+1,x+2.....,x+n. This means at ith position with i starting from 0, the number of candies at that position must be strictly less than x+i+1.

Sort the array and iterate from the back. Let m1 be the maximum number. Now, how many positions can m1 occupy? It is x+n-m1 as m1 can only occupy positions having candies greater than m1.

Now, let m2 be the next(second maximum) number. It can occupy positions x+n-m2-1. We subtract 1 as one of the positons is already occupied by the maximum number. Similarly, for m3 it will be x+n-m3-2 and so on.

So, for ith number(array[i]), the positions it can occupy is x+n-array[i]-(n-i-1). If the number is less than x, then we have to subtract x-array[i] as the number of candies cannot be less than x, hence the number of positions it occupies will be x+n-array[i]-(n-i-1)-(x-array[i]).

On simplification, the number of positions for array[i]>=x is x-array[i]+i+1 and for array[i]<x is i+1. or simply min(x,array[i])+i+1-array[i].

Now f(x) is simply product the positions the numbers can occupy. 85781407

If someone has a simpler explanation for this approach, please let me know

The book is good if you are preparing for an interview(as the name suggests). It some really good tips and insights regarding interviews. But the questions IMO, are average and most of the techniques might be familiar to you.

I would suggest LeetCode if you are preparing for interviews.

Depends on what your goals are. If you are looking to improve your overall CP skills I would recommend doing rating wise. You will get to practice a variety of DS and Algorithms. Secondly, not knowing the topic beforehand helps you develop approaches to a problem. If you encounter a new topic, you can read and learn about it. If you still do not feel confident in solving that topic, then you can solve a few questions topic wise.

Secondly, some topics might have prerequisites. If you do not know recursion and start practicing DP, you will take a lot more time to learn and end up wasting time.

In Coin Combinations II(1636) shouldn't the vector x be sorted?

In my opinion, if you blindly follow one resource, then your growth will be slow. Rather I recommend you practice from different resources as each has its strengths and weaknesses. Also, it gets boring practicing from the same resources.

A2OJ ladders are good practice. You can also try CSES Problemset.

It depends on your rank in the contest, not the number of problems you solve.

During a live contest, your solution is not tested on all the testcases as it will increase judging time. So a small number of strong testcases called pretests are used. But sometimes the pretests turn out to be weak.

After the contest is over, your solution can be viewed by anyone. You can then run the solution on your custom testcases known as hacks. if the solution fails, then the hack is succesful.

Yes, Exactly.

Seeing your profile, I think you have not participated in many contests.

This is the same when pretests are weak. You move on to another question. I know it feels unfair, but those contests are not unrated. It will be unfair to those who actually solved that question correctly.

The checker was wrong. It was fixed later.

How is this any different from cases where pretests are weak?

I think the round should be rated. This case is the same as when pretests are weak and your solution passes. Since the hacks work, the checker is actually fixed

I don't know if this is possible, but can you a button which can toggle between the two graphs? BTW great extension!

Can you also add a pie chart of the problem tags solved? it would be really helpful

1379D - New Passenger Trams

You can see that for any value between y and mx the maximum sum segment will always be that chosen one.

Can Someone explain this?

`

Understood this one rather than the editorial. Thanks!

Imposter Syndrome Bro.

This guy made an account and went through all this effort just to prove a point. Hats Off!

Three contests back to back! Thanks for saving us this lockdown

Yes. That would be cool!

Yes. I am having a much better time coding now.

Why?