No one gives a fuck about Chinese football matches.

Seems that you're not very experienced in football, Chinese football matches aren't worth watching...

I can understand your pain, guy. Chinese football matches are much better than foreign ones, and taking part in such a shitty contest is totally a shame! So all those who says "Chinese football matches aren't worth watching" please go away, far away!!!!!!!!

I think to publish it after the contest would be better.

As a writer of this contest, please refrain to write some hints about the problem during the contest. The fact like "this problem can be solved with DP" or "this contest is already published 3 years ago" should be written after the contest. It might cause BAN or some bad thing.

Could you please explain a solution?

Edit: https://mirror.codeforces.com/blog/entry/69500

And: https://szkopul.edu.pl/problemset/problem/vl-wrtcyzmOumStUcnXGiQTm/site/?key=statement ^^

Maybe a connection or cache issue, I had no problem with atcoder and mozilla rather than at the begin of the contest.

Not really, nowadays it's almost impossible to know all the problems from all platforms. In Poland, we're spending some time trying to find similar problems using Google. If we cannot find anything, then the task is fine.

For C, another approach is to let dp[i] be the number of moves you can achieve if you start from i.

I'm not so lucky like you. QWQ

I also used randomize + greedy, and I got WA.

Just maybe your sorting function is so good.

I actually generated testcase which naive hill climbing algorithm may fail. I think it's the case of chenxiaoyan.

However, I expected that simulated annealing algorithm may pass. Within this constraints, I don't think that there exists a killer case for SA algorithm. SA is so powerful that even solves a problem in AGC.

Nevermind, It worked, messed up the cycle check back then :( Check out my solution if anyone wants : https://atcoder.jp/contests/abc139/submissions/7293559

Can you please explain the logic behind your approach, thank in you advance

From what I could comprehend, after you apply a socket wire ( or whatever it was called, having parameter A), the old socket is converted to a multi — socket of size A. So how many minimum we need to apply to at least get B sockets? You can refer the image for A = 3 and transitions: Link : https://ibb.co/bXcss0W See the numbererd nodes?They are our sockets after adding each wire at each step of size A.

Initially, you have only 1 plug which is open. You want "B" open plugs. You have only "A" sized boards (which means each board has A open plugs.) Target is to find the minimum number of "A" sized boards required to get "B" open plugs.

The key idea is Whenever you use a brand new board, you will have to use an empty plug from previous to connect this.

So essentially whenever you add a board you add "A-1" open plugs and not "A". Just simulate this by adding boards until you reach B or more.

Useful conclusion: a convex hull on integral points with $$$x$$$ and $$$y$$$ coordinates both in range $$$[1,A]$$$ contains at most $$$O(\sqrt{A})$$$ points. In this problem, the maximum absolute value you can reach is $$$N \cdot maxX \leq 10^8$$$, so at most $$$O(\sqrt{N \cdot maxX}) \leq 10^4$$$ points.

Thus, even if you brute-force the convex hull after each vector, the total complexity will be $$$O(NP \log P)$$$(Let the size of the hull be $$$P$$$), which can fit the time limit.

Of course this won't work for $$$N=200,000$$$. In fact, we can scan the vectors with a half plane. Update the answer when their is a vector go into/out of the half plane. The total complexity is $$$O(N \log N)$$$(imo).

Maybe you can share your convex hull code here, because I didn't implement it :D

Wow, grats for actually thinking of this in contest fairly quickly. I saw it and immediately thought of https://mirror.codeforces.com/contest/995/problem/C, remembering that even though there was an elegant solution, randomization + greedy heuristic solved all cases and was hard to break.

Turns out same was true for this one.

Let's create a directed graph. Where each node is a match played between two players. Now let's add edges to this digraph. For an ith person's required order we add a directed each for each adjacent positions. That is for j in range (1..n-1) add directed edge from (j-1) to j. Also since match played between a&b and b&a is similar we merge these edges into one.

Now we have a directed graph. We just check the topological ordering of this graph. If it's cyclic then we don't have an answer.

Now to find the minimum days: For a node who has not yet finished (is still waiting on some nodes to finish), this node can only finish when the max days taking node it is still waiting for finishes and then it takes 1 more extra day to finish.

Obviously, the nodes which don't wait for others to finish end on day 1. For other nodes, we update them using the previously done. And maintain maximum throughout.

In E : first observation was to see, among all the possible matches , which would be the first match . if we say the i th player played the first match with the j th player. then in the column of i , j would be the first element and in the column of j , i would be the first element . Now since on day 1, i th and j th player has played , so they can't play more matches on day 1. so we try to find some more pairs for day 1, if they satisfy the above criteria . we can do this while traversing the first column. after finding all the pairs which played on day 1 , we can start to find pairs who played on day 2. for finding the pairs what i did was to initialize n pointers to 1. if some pair satisfy the criteria , I incremented their respective pointer by 1.when we find no pair , we break out of the loop. at the end, if all pointers are at n , which means all have played , we simply print the number of days , else we print -1 . Hope it helps. for more clarity, you can see my code : Link

well, an well known problem appearing in any contest doesn't destroy the fun of problem solving as long as the problem is elegant/crafty, right? if someone knows the solution beforehand they can just solve it quickly and go rewatch some rick and mortys. On the other hand, it might turn out to be a wonderful contest with cool problems :)

Assuming you are asking 0-indexed numbering: First of all taking minimum and maximum is to avoid distinction between pairs like (1,2) and (2,1) or you can say we need unordered pairs in the problem. Secondly the numbering is one of possible numbers you can take. This numbering is just indicating, say in a grid, you are at (1,5) and grid size is 6*6, so the assigning numbers from first cell to the required cell, starting with 0,you get number 1*6 + 5(only for 0 based indexing ), so think it like this, at (i, j) cell, you need to move n*i number of cells along rows and then the jth cell is your requirement, hence the number n*i+j.

you guys must have some kind of magic wand!