### chokudai's blog

By chokudai, history, 5 months ago, ,

We will hold AtCoder Beginner Contest 143.

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

We are looking forward to your participation!

• +49

 » 5 months ago, # | ← Rev. 2 →   +34 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.
•  » » 5 months ago, # ^ |   +12 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.
•  » » 5 months ago, # ^ |   0 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/
 » 5 months ago, # |   +5 Clashes with SRM 769 ;_; If possible, please move it to Sunday
 » 5 months ago, # |   +3 The last 10 minutes of the contest clash with the first 10 minutes of Kickstart. Please move it half hour back if possible.
 » 5 months ago, # |   +6 Problem E is similar to SPOJ CLZDOUGH.
•  » » 5 months ago, # ^ |   0 slowleak from north american 2019 icpc qualifier
•  » » » 4 months ago, # ^ |   0 Do you know the solution for it? Can't figure out what I should do with limited quantity of fuel stations.
 » 5 months ago, # | ← Rev. 2 →   0 How to solve problem D?
•  » » 5 months ago, # ^ |   +1 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 5 months ago, # ^ |   +1 Problem D is completely identical to https://www.geeksforgeeks.org/find-number-of-triangles-possible/
•  » » » 5 months ago, # ^ |   +1 And this one : https://leetcode.com/problems/valid-triangle-number/
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 Sort first. Then enumerate the longest 2 sticks i,j(i
•  » » 5 months ago, # ^ |   +1 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.
•  » » » 5 months ago, # ^ |   0 And this is done in O(n^2)
•  » » 5 months ago, # ^ |   +8 When I saw it, I immediately thought of a problem I had done. http://acm.hdu.edu.cn/showproblem.php?pid=4609So using fft and the principle of exclusiono (nlogn).
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 what amazing is , that i wrote a brute force algorithm without any optimization， and it AC ????????? code , i think atcoder should add hack system
 » 5 months ago, # |   0 please ,publish editorials fast .....
 » 5 months ago, # | ← Rev. 2 →   +6 I think Problem E is fantastic! (Although I failed to solve it in contest time T_T ) Twice floyd is so cool.
•  » » 5 months ago, # ^ |   0 please explain the logic behind twice Floyd warshall
•  » » » 5 months ago, # ^ |   0 Refer to my code ,you may find it helpful.
•  » » » » 5 months ago, # ^ |   0 It will be really helpful if you provide some explanation or logic...bcoz I want to code it myself without looking at the solution
•  » » » » » 5 months ago, # ^ |   0 Refer to my editorial, you may find it helpful.
•  » » » » 5 months ago, # ^ |   0 stops[i][j]=min(stops[i][j],1+stops[i][k]+stops[k][j]);please explain this line ? why adding 1 ?
•  » » » » » 5 months ago, # ^ |   0 Because we are assuming k as a stop here.
 » 5 months ago, # |   0 How to solve F?
•  » » 5 months ago, # ^ |   +22 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.
•  » » » 5 months ago, # ^ |   0 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).
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 Can we do it by generalizing this question for k=1 to n https://codeforces.com/contest/1201/problem/B, here k is 2.
 » 5 months ago, # |   0 How to solve Problem E?
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 running dfs on source and destination for each query will also work out maybe?? plzz have a look at my submissionhere
•  » » » 5 months ago, # ^ |   0 By the way, after the first Floyd you can simply run a second Floyd to effectively calculate what your BFS+dp does.
•  » » 5 months ago, # ^ |   +1 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.
 » 5 months ago, # |   +8 I wrote an unofficial English editorial! You can find it here.
•  » » 5 months ago, # ^ |   -9 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
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 In worst case, running Dijkstra for finding all pair shortest paths by running it for every vertex will take O(N3 log M) which may give TLE. Floyd Warshall on the other hand, run on O(N3), which should definitly pass.Here: N<=300 and M<=(N*(N-1))/2. In worst case there will be around 3003*log (300*299)/2 operations..which equals to around 108,000,000. And there will be at most 300*299 = 89,700 queries. Floyd Warshall on the other hand, will take 27,000,000 operations, 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.....
 » 5 months ago, # |   0 how to solve E and F ?
 » 5 months ago, # | ← Rev. 2 →   +20 My first AtCoder contest :) My solutions (hope they are understandable):A) $max(a-2b, 0)$. https://atcoder.jp/contests/abc143/submissions/8036846B) 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/8037254C) 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/8037631D) 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/8039964E) 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/8036592F) 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
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 That's crazy, we did B, D, E, and F all differently from each other.
•  » » » 5 months ago, # ^ |   0 Wow! You asked in revision 1 of the comment if you could use the alternative solutions for your editorial. Of course, go ahead :)
•  » » » » 5 months ago, # ^ |   0 I might add some later, haha, I changed my mind because I was feeling a bit lazy. :)
•  » » 5 months ago, # ^ |   0 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!
•  » » 5 months ago, # ^ |   0 what is then the complexity of your E using standard Dijkstra with a modification
•  » » » 5 months ago, # ^ |   0 I think it would be N*(E*log(N))
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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
 » 5 months ago, # |   -9 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
 » 5 months ago, # |   +6 Atcoder is really much different to Codeforces. I can't solve problem F.
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 5 months ago, # ^ |   0 Yes, it works
 » 5 months ago, # |   0 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?
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 What is this previous[][] matrix good for?
•  » » » 5 months ago, # ^ |   0 It's used for retracing the path for given 2 nodes.
 » 5 months ago, # |   0 Can someone explain how to do F?
•  » » 5 months ago, # ^ |   0 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)
•  » » » 5 months ago, # ^ |   0 Thank you so much! I got it.
 » 5 months ago, # |   0 What is test case handmade04 of problem D. Could you help me figure out what wrong with my code?
•  » » 5 months ago, # ^ |   +1 N = 2000 a_i = 1000 (for all i)
 » 5 months ago, # |   +1 Can I see test case on AtCoder like Codeforces? If yes, how? I'm new to AtCoder.