chokudai's blog

By chokudai, history, 4 weeks ago, In English,

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!

 
 
 
 
  • Vote: I like it
  • +49
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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/

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem E is similar to SPOJ CLZDOUGH.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please ,publish editorials fast .....

»
4 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

Twice floyd is so cool.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain the logic behind twice Floyd warshall

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Refer to my code ,you may find it helpful.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        please explain this line ? why adding 1 ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem E?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E and F ?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to do F?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case handmade04 of problem D. Could you help me figure out what wrong with my code?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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