We will hold AtCoder Beginner Contest 143.

- Contest URL: https://atcoder.jp/contests/abc143
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20191019T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: capra, QWE_QWE, beet
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

I started doing ABCs starting with ABC 126 (I think the first 6-problem one). Does anyone else feel like they've been getting harder over time since then?

Edit: this is the first time I've solved all the problems in a while, so I wrote an editorial.

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/

Clashes with SRM 769 ;_; If possible, please move it to Sunday

The last 10 minutes of the contest clash with the first 10 minutes of Kickstart. Please move it half hour back if possible.

Problem E is similar to SPOJ CLZDOUGH.

slowleak from north american 2019 icpc qualifier

How to solve problem D?

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/

And this one : https://leetcode.com/problems/valid-triangle-number/

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.

And this is done in O(n^2)

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).

what amazing is , that i wrote a brute force algorithm without any optimization， and it AC ????????? code , i think atcoder should add hack system

please ,publish editorials fast .....

I think Problem E is fantastic! (Although I failed to solve it in contest time T_T )

Twice floyd is so cool.

please explain the logic behind twice Floyd warshall

Refer to my code ,you may find it helpful.

It will be really helpful if you provide some explanation or logic...bcoz I want to code it myself without looking at the solution

Refer to my editorial, you may find it helpful.

stops[i][j]=min(stops[i][j],1+stops[i][k]+stops[k][j]);

please explain this line ? why adding 1 ?

Because we are assuming k as a stop here.

How to solve F?

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

Good explanation, thank you. But why not use another prefix sum for “number of types of cards appearing more than O times”. Maybe use _times[i] to record how many types of cards appearing just I times, and then implement prefix sum. This part can be done in O(n) separately. So the whole algorithm will become O(N*logN).

Yes, it is possible https://atcoder.jp/contests/abc143/submissions/8053884 (but it gives more run-time instead :/)

I think it is a bit more complicated than just doing lower_bound, in contest you just want AC, not best complexity but longer time to implement.

Edit: my code give longer run-time because binary search range in each k always between 0 and n, changing it to [0, n / k] give 61 ms, updated code

I know what you mean. Complexity is just complexity instead not real run time. But I still think when N get larger( like 1e6 ), algorithm with complexity O(NlogN) will be quicker.

Can we do it by generalizing this question for k=1 to n https://codeforces.com/contest/1201/problem/B, here k is 2.

How to solve

Problem E?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.

running dfs on source and destination for each query will also work out maybe?? plzz have a look at my submission

here

By the way, after the first Floyd you can simply run a second Floyd to effectively calculate what your BFS+dp does.

First use

Floyd Warshallto 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:

Then run

Floyd Warshallagain 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`

.I wrote an unofficial English editorial! You can find it here.

My approach was to run Dijikstra for every query and at the same time store the shortest path. Once we have the path we can greedily check the minimum refueling required. Why does this fail on some test cases, can you please help me. My submission code

In worst case, running Dijkstra for finding all pair shortest paths by running it for every vertex will take

O(Nwhich may give TLE. Floyd Warshall on the other hand, run on^{3}log M)O(N, which should definitly pass.^{3})Here:

`N<=300`

and`M<=(N*(N-1))/2`

. In worst case there will be around300operations..which equals to around^{3}*log (300*299)/2108,000,000. And there will be at most300*299 = 89,700queries.Floyd Warshallon the other hand, will take27,000,000operations, and you'll need to run Floyd Warshall two times. And still it'll be faster than running Dijkstra for each vertex.Using Dijkstra may still pass, with modifications.....

how to solve E and F ?

My first AtCoder contest :) My solutions (hope they are understandable):

A) $$$max(a-2b, 0)$$$. https://atcoder.jp/contests/abc143/submissions/8036846

B) It's the same as $$$\frac{1}{2} \left (\sum_i d_i \right )^2 - \frac{1}{2} \sum_i d_i$$$. (This optimization is not necessary, you can just code the $$$O(n^2)$$$ one) https://atcoder.jp/contests/abc143/submissions/8037254

C) The number of slimes is the same as the number of letters that start a slime. I.e. the number of i's such that $$$s[i] \neq s[i-1]$$$. https://atcoder.jp/contests/abc143/submissions/8037631

D) I considered three different types of triangles with length $$$a \le b \le c$$$: (1) $$$a \le b < c$$$, (2) $$$a = b = c$$$, (3) $$$a < b = c$$$. As a helper-array I computed for each l: (i) the number of triangles with length $$$= l$$$ and (ii) the number of triangles with length $$$\le l$$$. For (1) you can just iterate through all pairs $$$(a, b)$$$ and count the number of values c such that $$$\text{max}(a,b) < c < a+b$$$. You can do this using the array of type (ii). For (2) you can just use the array of type (i) and use that the number of triples of k numbers is $$$\frac{k(k-1)(k-2)}{6}$$$. For (3) you can iterate through all values $$$l$$$. The number of pairs (b,c) such that b=c=l you can get from the array of type (i), and then you can get the number of values for a using the array of type (ii). https://atcoder.jp/contests/abc143/submissions/8039964

E) Here I used a standard Dijkstra with a modification. The distance from u to v is represented as a pair $$$(n, t)$$$ where $$$n$$$ is the number of times you need to get a full tank and $$$t$$$ is the fuel you've used after filling the tank up the last time. So if you use a road of weight w then the next distance will be $$$(n, t+w)$$$ if $$$t+w \le L$$$ and $$$(n+1, w)$$$ otherwise. Remember to discard all edges with weight $$$> L$$$. https://atcoder.jp/contests/abc143/submissions/8036592

F) Let B_i be the number of values j such that A_j = i. So B_i is the number of times i occur in A_1, ..., A_n. So you could say that there is a "group" of i's of size B_i. Let C_i be the number of times B_j = i. So C_i is the number of times i occur in B_1, ..., B_n. Or equivalently, C_i is the number of "groups" of size i. Let x_t be the answer for K=t. Now we need three observations: (1) We have $$$x_1 \ge x_2 \ge \ldots \ge x_n$$$. (2) $$$x_t \le \text{floor}(S/t)$$$, where $$$S = \sum_i C_i \cdot i$$$. (3) We can pretend that any groups of size $$$> x_t$$$ has size $$$x_t$$$. Now the algorithm is the following for t >= 2: We maintain S throughout. First we check if $$$\text{floor}(S/t) \le x_{t-1}$$$. If it is we decrease the size of all groups to size at most $$$\text{floor}(S/t)$$$. This will make S smaller. So we check if $$$\text{floor}(S/t) <= X_{t-1}$$$ again. And so on.. This is line 25-35 in my submission. You only need to decrase the groups with 1 at a time — this is OK since we only decrease n times in total meaning we still have a running time of $$$O(n)$$$. https://atcoder.jp/contests/abc143/submissions/8041589

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

Wow! You asked in revision 1 of the comment if you could use the alternative solutions for your editorial. Of course, go ahead :)

I might add some later, haha, I changed my mind because I was feeling a bit lazy. :)

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

Eusing standard Dijkstra with a modificationI think it would be N*(E*log(N))

My approach was to run Dijikstra for every query and at the same time store the shortest path. Once we have the path we can greedily check the minimum refueling required. Why does this fail on some test cases, can you please help me. My submission code

Atcoder is really much different to Codeforces. I can't solve problem F.

For problem E, I was calling Dijkstra for each query that gives me 30 ACs and 20 TLEs in total 50 test cases.. Want to know a better approach!! please help

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.

You did it with Dijkstra? am asking this bcoz I read in someone's comment that Dijkstra would not work coz it is possible that there are two shortest paths and the path u stored gives -1 or wrong answer

Yes, it works

I generated dijkstra tree (minimizing the total count of moves to reach a point, along with petrol) for all nodes, but last 8 test cases failed for my code.Anyone can tell what is wrong in my logic?

https://atcoder.jp/contests/abc143/submissions/8045251 Can anyone tell why my solution fails for last 10 test cases. I was adding an edge only if it's less than or equal to l and then applying Floyd–Warshall algorithm.

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

It's used for retracing the path for given 2 nodes.

Can someone explain how to do F?

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)

Thank you so much! I got it.

What is test case

`handmade04`

of problem D. Could you help me figure out what wrong with my code?N = 2000 a_i = 1000 (for all i)

Can I see test case on AtCoder like Codeforces? If yes, how? I'm new to AtCoder.