How to solve Div 2 B without a segment tree?

Same problem, can't find the mistake.

In Div1 B (football league problem) what is the mistake in my algorithm? I really don't see the bug. http://codeforces.me/contest/780/submission/25485848

He is a transbear.

Any ideas why this fails for problem B?

It seems the numbers are too big for long long.

Update: I found my mistake.

Thank you so much, you really helped me a lot. I spent hours trying to find the mistake. How did you find it? Did you look into the code or did you find a counterexample?

Thanks, here is my newest and clearest version and it passes this minimal test case, but not test 10. I really can't find the error here. http://codeforces.me/contest/766/submission/24810822

Wrote DSU for D without reading the solution. My idea is exactly the same as others' but it won't pass test 10. No matter what I do, no matter how much I fix it this solution just won't pass test 10. Here is my cleanest and last version of the program. Still won't pass test 10. http://codeforces.me/contest/766/submission/24810631 What the hell is in test 10?

I did exactly what you did and no matter how hard I try it won't pass test 10. I fixed everything I could, still the same. http://codeforces.me/contest/766/submission/24809940

I did it and it doesn't work. http://codeforces.me/contest/766/submission/24809940 No matter what I do it won't pass test 10.

Et tu, moejy0viiiiiv? How sad.

This might work. But why do you need 3 if you have already sorted them by the number of neighbours?

Read my first sentence.

Is it just me or Codeforces lags really hard?

Yeah, that sounds good.

Good idea, that may work.

First we create the graph itself by creating arrays for vertical and horizontal sides, then sort them(nlogn) and then iterate through this array using two pointers(linear). The resulting graph has O(N) vertices. We just start a DFS from some vertice, DFS all its neighbours and their neighbors and try to colour the vertice in a colour that its neigbours don't share. I think this should work.

What, the complexity will be O(nlogn).

Yeah bro, but Div1 B is an even bigger fail for most people here. :)

I know there's an easy solution for D, but what if the sides can be even too? I think this will work, correct me if I am wrong: Create 2 arrays, one for vertical sides and one for horizontal sides, sort each of them by y/r, then by beginning and end of a side. Then we just use two pointers to find all intersections of rectangles and build a graph. Then just DFS in this graph. I tried to implement this but the round ended. Do you think it will fit into the time limit?

Let's count what prefix of A you need to get every prefix of B. First let's look at prefix of B 1 character long. To get that prefix you need one character that is same as the first character of B, but from prefix A. Increase your counter until you find the first character from A that is equal to this first character of B. That's p[0]. Now let's count p[1]. You need p[0] to get the first letter and you also need a character from A that is same as the second character of B. So just increase counter starting from p[0] until you find this second character. And so on... Do this for suffixes now and the rest is easy.

Could somebody please explain C to me? I really don't understand what this stands for: "For every prefix of B, count how big of a prefix of A you will require." Same with suffix.

Update: I understood now.

Wow, that's even worse. The pretests are so weak.

Problem B not passed — nooooooo! So it's actually wrong to output yes when the piece is a rectangle.

I don't understand you, how can you get a rectangle from to pieces that look like this?

I hope so, because that's what I did. :)

LOL, this solution is really retarded. The pretests are really weak if it worked.

Well...you actually can. But you'll get a rectangle only when the pieces are initially rectangles. I don't understand the confusion about this problem.

Then why there seems to be such a confusion about this problem? This was the most obvious thing to implement.

Of course they are needed, you can't put edges between vertices that are connected to some capitals. The example contains such a test.

So what's the right solution for B? Check whether it's a rectangle? Or what? Even C is easier than this.

How to solve the problem about the table game?

Proof?

That feel when you don't understand the answer is 1 when the companies are different and instead find the nearest airport to airport B of the same company as airport A.

I am an idiot.

How to solve A?

This comment is just hilarious, why are you donwvoting it?

Thanks, but I still don't get this: "and count of such numbers can be obtained by maintaining a prefix count array ." What do you mean by "such numbers"? How do I use a prefix array to count them?

Ah, I started understanding this. Do we have to sort the initial array in a decreasing order?

You don't need a segment tree for problem D, just store three segments and update them each time you consider a new pair.

A question considering problem F: "then we know all P that P = k × Ai, find how many times P appears after modifying it is easy to solve by the array we created." What do you mean by this? Could you elaborate further on this statement?

I hope for an editorial for this contest, as well as for Technocup.

Thanks, that's so easy and obvious...I actually thought the same but then was misled by some example which I treated incorrectly.

How do you solve problem B? I wrote "something" which passed the pretests but it doesn't work it some cases. What's the normal solution for this problem?

Hell, how haven't I noticed it.(

Is the following approach for D right? I implemented this algorithm but it doesn't pass some pretests. Where is the mistake in this solution? Take two adjacent words, find the first position where letters are different. If the first letter is greater then we need to turn the wheel by minimum (c-a[i]) so that it becomes smaller than b[i]; if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. Store the maximum of the minimums and the minimum of the maximum and if the second value is less than the first then print "-1", else print the first value.

I got it. Good solution!

Yeah, you are right. I made a mistake.

This can be done even easier. If the sorting is O(N) then we can just sort the operations by left border and mark all the positions that were changed in O(N). Then we assume the default maximum value to be the maximum of all trims and watch every single position in O(N). If the position is not marked then we compare it with the maximum and check if it's better. Upd: mistake here, sorry.

But is the sorting really O(N)? OP hasn't clarified it.

We can do it simply, but it won't be O(N).

Not really messy, but I don't think there is a solution that works in O(N).

I had the same thoughts. Default answer is the maximum of all trims, the answer better that this can only be found in a point which is not covered by any segments. If there is a fast way to check whether the point is covered or not then we are done.

Update: But the fastest way to check whether it's covered is O(N). I give up.

Are you sure you need O(N)? All I can make up is O(NlogN).

That will be O(NlogN).

Of course, there were editorials for the previous Technocup.

That feel when you fail the round but still improve your rating and become blue. https://www.youtube.com/watch?v=BinWA0EenDY

Mark the checkbox "Show unofficial".

I Agree, but for some reason I thought it was easier than A and thus tried to solve it first.

I got this pretest working after I changed int to long long. This stupid mistake took so much time and score from me...

That solution for C was so easy! I tried to elaborate a mathematical solution but things got too complicated. BTW, is it possible to get time for each point in O(1)? It's pretty easy to convert time into coordinates, so there basically must be a way to do the opposite i.e. convert coordinates into time.

Why do I need a topological sort? Why can't I do the same DP as in the official solution but starting in the first vertex?

Do we really have to use a reversed graph to solve problem C? Can we use the given graph and do the same stuff but starting in point 1?

-

Problem E: "We also need to renumber our divisors according to their prime decomposition."

What does it exactly mean? Why do we even have to decompose the divisors?

This is all really weird.)

There are n vertices in a graph and the shortest way doesn't visit any vertex twice. So at most the algorithm visits n vertices and n-1 edges.

I can't get the point of problem C. When we remove the point which we want to turn into a centroid, do the incident edges get removed too?

I have a question regarding the C problem: could you please explain what does the "last colour" and "current colour" mean?

Will there be an analysis of all the problems?

They could at least let us still view tests in the Gym.

Auto comment: topic has been translated by Diplomate (original revision, translated revision, compare)

Me too, I also counted left turns)