AnandOza's blog

By AnandOza, history, 5 years ago, In English

Hi all, Atcoder Beginner Contest 143 was today. I wrote an unofficial English editorial. Hope it helps!

A: Curtain

The curtains can cover a maximum of $$$2B$$$. So either they don't cover the whole window and the remainder is $$$A-2B$$$, or they do and the remainder is $$$0$$$. So the answer is $$$\max(0, A-2B)$$$.

Runtime: $$$\mathcal{O}(1)$$$.

Sample code

B: TAKOYAKI FESTIVAL 2019

We can simply loop through every pair (taking care not to double count) and add the health points restored.

Runtime: $$$\mathcal{O}(N^2)$$$.

Sample code

Alternate solution (and code) by Tejs:

The product can be rewritten as $$$\frac{1}{2} \left[ \left(\sum_i d_i\right)^2 - \sum_i d_i^2\right]$$$.

Runtime: $$$\mathcal{O}(N)$$$.

Sample code

C: Slimes

We have to count the number of "runs" of consecutive slimes of the same color. We can do this by looping through the array and checking whether the current slime continues the run, then incrementing our answer when we reach the end of a run.

Runtime: $$$\mathcal{O}(N)$$$.

Sample code

D: Triangles

The total number of (unordered) triples of sticks is $$$\binom{n}{3} = n(n-1)(n-2)/6$$$. I think it's simplest to count the number of triples that cannot form a triangle, and subtract them. Let's first sort the input array, so if we have a triple $$$(i,j,k)$$$ with $$$i < j < k$$$, we also know $$$L_i \le L_j \le L_k$$$.

Then, we can loop through all pairs $$$(i,j)$$$ and determine how many values of $$$k$$$ make an invalid triple (but still maintaining $$$i<j<k$$$). Note that because we picked the two smaller sticks of our triple, we know the only possible disqualifying condition is $$$L_k \ge L_i + L_j$$$. We can find the smallest such value of $$$k$$$ using binary search, and then subtract $$$n-k$$$ from our answer.

Runtime: $$$\mathcal{O}(N^2 \log N)$$$.

Sample code

E: Travel by Car

First, observe that any path that has $$$K$$$ refills can be split into $$$K+1$$$ paths, each of which can be completed (starting with a full tank of gas) without refilling.

So, we can begin by finding all pairs of cities that can be traveled between on a full tank of gas without refilling. To do this, we can find the shortest path between all pairs of cities (for example, using Floyd-Warshall). Then, we build a new adjacency matrix for these paths, where two cities with distance $$$\le L$$$ have an edge of cost $$$1$$$, and two cities with distance $$$> L$$$ have no edge (or an edge with cost $$$\infty$$$). Then we compute the shortest path between all pairs using this new adjacency matrix, which tells us the minimum number of segments a valid path in the original graph can be broken into.

Then, given a query $$$(s,t)$$$, we simply find the distance in the new shortest-paths matrix and subtract $$$1$$$, and we have our answer (or print $$$-1$$$ if it's unreachable). We have to remember to subtract $$$1$$$ because it takes $$$K$$$ refills for a path of $$$K+1$$$ segments (or equivalently, the first tank of gas is free).

Runtime: $$$\mathcal{O}(N^3)$$$.

Sample code

F: Distinct Numbers

The key observation is that if you pick $$$M$$$ distinct numbers and remove all instances of them, and you have $$$S$$$ total numbers left, the maximum number of operations you can do is bounded above by $$$S/(K-M)$$$. Then, note that picking the $$$M$$$ most frequent distinct numbers gives the tightest bound (so instead of all subsets, we need to consider a lot less stuff).

So, we can count the instances of each number, so we end up with an array $$$C$$$ containing these frequencies. We can sort these frequencies, then for each value of $$$M$$$, compute the number of remaining numbers after we remove all instances of the top $$$M$$$ (let's call this $$$S_M$$$).

The function $$$f_K(M) = \frac{S_M}{K-M}$$$ is first decreasing, then increasing, so we can find its minimum by binary searching to find the first $$$M$$$ for which it increases. This gives us the tightest bound available. Once we do that, we simply need to check against the simple bound $$$N/K$$$ and return our answer.

Runtime: $$$\mathcal{O}(N \log {N})$$$.

Sample code

You can see my submissions here as well, if you prefer that to reading the code in the blog.

Thanks for reading! Let me know if you have any questions or feedback for me.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AnandOza (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Runtime for A should be O(1)

»
5 years ago, # |
  Vote: I like it 0 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 someone please help me. My submission code

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

    Consider the case where you have two paths between s and t, one goes through edges of weight 2 — 3 — 2 — 3 and the other 2 — 2 — 3 — 3. If your tank capacity is 5 then the first path needs one fill and the second needs two. Dijkstra by itself can't tell the two cases apart so this would fail.

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

      Yep, exactly. For another case where Dijkstra always fails, consider $$$L=10$$$ and paths $$$10+10+10$$$ vs $$$6+6+6+6$$$ (here the worse path is shorter, not just the same length).

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you mean L = 10.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, my bad, I was reading your comment while writing mine. :)

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

            E: Travel by Car can someone point out what is wrong in my idea bcz some test cases is giving wrong answer.

            I just find out minimum amount of gas required for all pairs of cities possible using Floyd-Warshall also I constructed a path matrix. Then for every query(A,B) I went through the shortest path(the path which required minimum amount of gas from A to B) A ->...i -> j ->.... ->B and checked for consecutive (i,j) cities that current amount of gas in tank is enough or not. since we know minimum gas require for travelling city j from I and hence I can either refill my tank or not. and this way I calculated my result. so what is wrong with this method?? Anyone can help please. my code is here...

            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Check the comments a few up for some examples where the shortest path isn't necessarily the best.

              Also, you should edit your comment to either link to your code/submission or put it in a spoiler tag, so it doesn't take up the whole screen.

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

    I wrote Dijkstra algorithm with little modification and it worked fine. At each node, store pair of (the minimum number of refueling require, fuel left). We should take number of refueling be the first priority and amount of left fuel be second one. The rest is the same as common Dijkstra. Code

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Applied same logic ,but I got wrong answer somehow :-( Code

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

        I found two bugs. First, you should skip the edge with weight > L, it causes negative vale in your dijkstra function. Second, when updating value, there is case distance is equal, but left fuel is greater. You didn’t consider this in your dijkstra as well. Fixing these two bugs, the rest is just TLE. https://atcoder.jp/contests/abc143/submissions/8054198 One obvious reason is #define int long long; Btw, seems like setters don’t want dijkstra to pass. They add the test that my solution is also TLE. Better to do Floyd solution. :)

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

          Actually I have considered these after the contest,but then also using the visited flag gave WA and without it -> TLE .Then i tried to optimise it by continuing the popping when current count is greater than the actual count.Yeah ,they added Test 51 which exceeded the TL on your soln.My AC solution.Code

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the same approach as yours and it is giving me AC on the last test added after the contest but I don't know why I am getting 9 WAs out of 51 TCs. I also tried some custom TCs but couldn't find out the mistake. It would be very generous of you if you please take a look at my code

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The problem E and your solution to it are really very beautiful.

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I dont fully get F, but have a different aproach. Which does not work well, I would like to know why. Here is what I did:

Observation: We can mostly use n/k operations, which eats (n/k)*k cards. If there is are values A for which exist more than n/k cards, these cards can never be eaten.

So, I count the 'cannot be eaten' cards, and then

ans=(n-cbe)/k;

Should work, doesn't it? Submisson

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anybody explain to my mistake in this solution

I am getting Wa and TLE in some cases...

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems you do simple Dijstrika without considering the tank stops or anything. What is the idea behind that?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have a another code. It gives tle dont wa.

      But this is giving tle too. It is unbelievable.

      My approach is this: I think that if your tank can be able to go this way with not fulling it then go.

      If you cant go you full it and go. And simple bfs or dijikstra can do it i think...

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think that we can also solve F by naively simulating the process for each K with a segment tree, this is true because the greedy algorithm of taking the K most frequent numbers each time works.

By properly modifying the segment tree you can take away k numbers in O(log(n)), and the total number of times you will take away K numbers for all K is: 1/2 + 1/3 + 1/4 + ... + 1/n, which sums up to O(nlogn), so in total the algorithm will work in O(nlog(n)^2).