Only the $$$F$$$ or all the problems ?

I think that the $$$D$$$ has gotten a lot easier after it became a $$$6$$$ problem contest and yes the first $$$6$$$ problem contest was much easier than the subsequent ones.

You can actually check kenkoooo to see the ratings of the problems.

After the switch from 4-problem to 6-problem, I noticed that A to D are so much easier. Since I can't do any problems above D I'd rather not talk about it. Overall I think it is way harder for one to get perfect score, but way easier for people like me to solve at least 4 problems.

There's always this useful website that keeps track of the problem difficulties: https://kenkoooo.com/atcoder/#/table/

slowleak from north american 2019 icpc qualifier

Sort an array. In two nested loops run binary search : lowerBound and upperBound to find first and last indexes which can form a valid triangle.

We observe that for a pair (a, b), all values of c such that c < a + b and c > b — a and c > a — b form a valid triangle.

We consider all possible i, j such that a = L[i] and b = L[j] in O(N ^ 2). Without loss of generality, we let a <= b (implementation wise, we just swap them otherwise). We can keep an array of the number of occurrences of all values k such that 0 < k <= 1000 in the array L, and then prefix sum the occurrence array to solve range sum problem quickly. For a pair (a, b), the answer is just the number of elements with value in the range (b — a, a + b), which can be found with the prefix sum array in O(1) per pair.

Finally, we obtain an answer. However, note that a triplet (a, b, c) can be permuted in six different ways, hence we divide that answer by 6 and print it.

Edit: Oops, could have done it by sorting array and using binary search... Also, take note that a could possibly be in the range of (b — a, a + b), you need to account for that case.

Problem D is completely identical to https://www.geeksforgeeks.org/find-number-of-triangles-possible/

Sort first. Then enumerate the longest 2 sticks i,j(i<j) and we can get the range of the length of the shortest sticks i.e.(l[i]+l[j],l[j]-l[i]). So we can do a binary search to get the number of the shortest sticks. Because we enumerate in order, they won't be counted repeatedly.

(forgive my poor English)XD

Run a (for) on the array of numbers . Suppose that you are on the other element of the array. make vector that contains sum of all pairs of numbers whit index less than i. Run a for on vector and if the current number a(i) was less than the element of the vector , increase the ans by one. And then add new members to the vector paired with a(i). You search my solution with handle cfmasterr on atcoder.

When I saw it, I immediately thought of a problem I had done. http://acm.hdu.edu.cn/showproblem.php?pid=4609

So using fft and the principle of exclusiono (nlogn).

please explain the logic behind twice Floyd warshall

For F, we consider a modified problem. Consider the maximum K value possible for some number of operations O (number of times cards are eaten). We observe that if a particular type of card appears more than O times, we add one to the value of K. This is because we can use that card every time for all O operations. Now, we consider all cards that appear less than O times. Let's say there are a grand total of X such cards where their type appears less than O times. We add X / O (floored) to K. Thus, we obtain the maximum possible K value.

Now, we return to the original question. For each value of K, we perform a binary search on O. The value of X can be calculated with prefix sum and the number of types of cards appearing more than O times can be calculated with binary search. Thus, each query can be solved in O(log^2 N) time for the nested binary search. This yields a final time complexity of O(N log^2 N), which is AC.

My code: https://atcoder.jp/contests/abc143/submissions/8045984

Floyd first. Then for each vertex do a BFS (it's similar to a Shortest Path Algorithm) to dp: dp[i][u]: the minimum number of times to refuel from i to u if you refuel at u. dp[i][v]=min(dp[i][v],dp[i][u]+1) if dist[u][i]<=L. Process it in a BFS order for times just like SPFA.

First use Floyd Warshall to find all pair shortest paths. Then run a nested loop to check every value in the distance array if it's less than or equal to L. If it is, then set change the value in distance array to 1, otherwise set it to infinity.

In simple:

for (int i=1; i<=n; i++) {
   for (int j=1; j<=n; j++)
       if (distance[i][j]<=L)
          distance[i][j]=1;
       else
          distance[i][j]=inf;
}

Then run Floyd Warshall again on the distance array. Now for each query check if the value at distance[s][t] is inf or not. If it's inf then you can't reach this city. Otherwise you'll get the answer as distance[s][t]-1.

That's crazy, we did B, D, E, and F all differently from each other.

Bro, my last 8 cases were WA with the same approach as yours in E,please share what possible mistake i could have made if you could think of any?Thanks!

what is then the complexity of your E using standard Dijkstra with a modification

In problem E, I did what you said but it is giving TLE on last test case. I tried a lot to debug but not able to do it. I also tried to compare it to your solution it seems similar but my solution is giving TLE. Can you please debug my solution

Instead of calling Dijkstra in every query, try using Dijkstra from every possible source node as a preprocessing step.

O(QMlogM) (your method) is TLE as it can go up to about 10 billion operations in the worst case. O(NMlogM) is AC.

What is this previous[][] matrix good for?

One way to solve it is the following: 1.- First, you realize that as the number K increases, the number of operations that can be done, decreases or it remains the same. 2.- You solve the inverse problem, i.e. given a number of operations OP that you should do, you must calculate the maximum k that can be used. You solve it for 1 <= OP <= N 3.- Finally, for each K, you search for the maximum value of OP whose associated k value is greater or equal than K.

Complexity: O(N log N)

N = 2000 a_i = 1000 (for all i)