AnandOza's blog

Atcoder Beginner Contest 174 — Unofficial English Editorial
By AnandOza, history, 4 years ago, In English

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

A: Air Conditioner

We simply write an if statement.

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

Sample code

B: Distance

We can loop through all the points, and test each one. To avoid potential rounding errors, it's simplest to check $$$x^2 + y^2 \le D^2$$$, so we can keep everything in integers.

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

Sample code

C: Repsept

First, we simplify: if $$$k$$$ is a multiple of $$$7$$$, then we can look for a number like $$$1111$$$ that's a multiple of $$$k/7$$$. Otherwise, using $$$7777$$$ instead of $$$1111$$$ doesn't help us.

If you consider the sequence of numbers to check as $$$a_i = 10 a_{i-1} + 1$$$ modulo $$$k$$$, there is guaranteed to be a solution within $$$k$$$ steps if and only if $$$\mathrm{gcd}(10, k) = 1$$$. So we can check for impossibility using this fact, and then iterate through the choices otherwise and check them all until we find the smallest one that works.

Proof of bound

Take care to test locally on $$$k=1$$$ specifically, it's easy to get this wrong with a loop.

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

Sample code

D: Alter Altar

A few quick observations:

  • At the end, we want a sequence that looks like RRRRWWWWWWW (some number of red stones, followed by some number of white stones, and one of these could possibly be zero).
  • If we want to change a red stone's color and a white stone's color, this takes 1 step as we can swap them.

Now, we can simply try all values of the final number of red stones from $$$0$$$ to $$$N$$$ (let's call this number $$$R$$$). For a given value of $$$R$$$, the cost is given as

$$$X = (\text{number of white stones in the first $$$R$$$})$$$
$$$Y = (\text{number of red stones in the last $$$N-R$$$})$$$
$$$C_R = X + Y - \min(X,Y)$$$

If we compute prefix sums to help us compute this, we can test one value in $$$O(1)$$$, so testing them all will run in time.

Bonus: this function is convex, so we can minimize it using ternary search.

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

Sample code

E: Logs

It's hard to figure out which logs to cut greedily, but given a value $$$L$$$ for the final answer, we can easily check whether it's attainable in $$$O(N)$$$.

In order to do this, we loop through all the logs and cut off pieces of exactly length $$$L$$$ from them, until they are length $$$L$$$ or shorter. So for a log of length $$$x$$$, this takes $$$\lfloor(x-1)/L \rfloor$$$ steps.

It's also easy to see intuitively that the cost is non-increasing as $$$L$$$ increases, so we can binary search to find the smallest length $$$L$$$ so that the numbers of steps is $$$\le k$$$.

Runtime: $$$\mathcal{O}(N \log L)$$$, where $$$L$$$ is the maximum possible length of a log.

Sample code

F: Range Set Query

This is a standard algorithm, which I didn't figure out myself but learned some time ago by web search, from the following link: https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/

To implement it efficiently without bugs, I copy/pasted from my submission for a previous Codeforces problem (85732941).

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

Time to write: $$$O(1)$$$.

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
  • +131
  • Vote: I do not like it

Comments Comments (43)
| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

An alternate perspective for D : Alter Altar.

We know that the answer starts with a stream of R and ends with a stream of W. So, we can start with 2 pointers from both ends, and greedily advance them as long as we see R on the left and W on the right. Once a mismatch happens, swap them and continue.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Or to simplify even further, we can count the number of "R" in array, store in variable 'r' and find number of "R" in first 'r' places and subtract it from r, that's your answer.

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

    Exactly my solution as well. I think it's the standard solution for such a problem.

    → Reply
»
4 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).

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

    Will you please explain how can we say that-: "If you consider the sequence of numbers to check as ai=10ai−1+1 modulo k, there is guaranteed to be a solution within k steps if and only if gcd(10,k)=1."

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D since all the red stones should be before white stones, so i just checked the number of white stones till index X(X=number of Red stones) which was the answer

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think I have an easier solution for problem D.

Code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I was also did the almost same thing with little difference. First, count total "R" (say cnt) present all over the string , then for upto cnt check whether all characters are "R" or not, if not that means there is "R" present after cnt and hence to do swap bring it inside cnt ( no need of actual swap ) and hence increasing my answer by 1. Here is my submission: https://atcoder.jp/contests/abc174/submissions/15609443

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I binary searched on float values for Problem E and rounded off finally for the answer. Verdict WA. Can someone tell the reason for it??

Code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Without reading your code, it's possible that you get a rounding error. Whenever possible, I try to avoid using doubles/floats because it's just one more risk -- you can see that in my solutions for B and E of this contest. Personally, also, I find it difficult to have good intuition about what tolerance/epsilon to use when doing things with floating-point numbers.

    Actually, now that I read it, I don't think the logic of rounding makes sense. This problem is sort of discrete, so I'd recommend you reinvestigate that. (But I'm not sure.)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

X+Y-min(X,Y) is just max(X,Y)

P.S. — Think twice and check trice before sharing GFG links here. Prefer other websites over it.

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

    I would love a better source for that, since I had some trouble reading it when I originally learned the algorithm, but I wasn't able to find one easily. Let me know!

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

    Why?? GFG links are good for beginners I think so....although I know some algorithms are implemented in a wrong/bad way....is there any other issue with GFG links?

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

      Most of them are wrong and buggy.
      Beginners are the ones who should avoid them. Others can at least find errors while reading. And swear not to use gfg again.

      Spoiler
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        I still remember that day when the interviewer opened random links from GFG and was asking problems....he himself didn't have any idea what he was asking and while I was trying the problem he was reading the solution

        → Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Also, here's a video tutorial for people who are interested.

→ Reply
»
4 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).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello sir, I tried question F using segment trees but I think my solution is not optimal and right too, because I'm getting AC, WA, and TLE. Can you look at my solution and let me know where I have to improve my code. My submission link: https://atcoder.jp/contests/abc174/submissions/15638569 Thanks in advance.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

F: https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/

Can someone confirm that this will TLE ? I think the Time complexity written is wrong in that article.

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

    Why just copy paste articles? It ain't taking you anywhere.

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

      When did I say that I copied ? I tried the same approach and found this article after the contest ended.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am still not able to understand why in problem C, a solution is guaranteed in k steps :( If anyone can explain , it would be of much help.

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

    pop3

    Let's believe that it takes >k steps. So, at every step there is a remainder (when we do %k) not equal to 0. So, if number of steps>k, then it is for sure that (atleast) any 2 steps have the same remainder. Let those steps be ith and jth (j>i), and remainder be r. So,

    ai % k = r and aj % k = r.

    Let's do (aj — ai), 7/9(10^j — 10^i) = [7/9(10^(j-i) — 1)]*(10^i) = a(j-i) * 10^i (Eqn 1)

    (Note: an = 7/9(10^n — 1)

    Also, (aj — ai)%k = (aj%k — ai%k)%k = (r — r)%k = 0%k = 0.

    Therefore, aj — ai = a(j-i) * 10^i (from Eqn 1)

    is divisible by k. Which means a(j-i) is divisible by k, i.e., rem=0, which is a contradiction as (j-i)<k.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

In problem C Brute force also work

#include<bits/stdc++.h>
using namespace std;
int main()
{

  int k;  cin >> k;
  int n = 0;
// for even value of k check
  if(k%2==0)
  {
    cout<<"-1";
    return 0;
  }
  for (int i = 0; i < pow(10, 6); i++)
  {
    n = (n * 10 + 7) % k;
    if (n == 0)
    {
      cout << i+1;
      break;
    }
  }
  if (n != 0)
    cout << "-1";
  return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please use spoiler tag (and code block), or just link to submission instead of copy/paste.

    Also, this is basically the same as the solution already posted, but with the check for divisibility by 5 moved to the end.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D : https://atcoder.jp/contests/abc174/submissions/15606632

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Simplest solution for D:

Sort the string s. Check which characters are different from the original string (Let this be count). Answer will be count/2.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I am getting WA in 2 tests for Task F. Can someone help me out?

Submission

I have used merge sort tree. Storing the previous occurrence of every color. (-1 if this is the first occurrence). Now for a query, I will query number of elements in the prevOcc array, from index [l, r], which is < l.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you explain why using integer binary search for problem E gave us the correct answer.I got confused due to that rounding off part and tried to use double binary search and got WA due to incorrect implementation.

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

    For the binary search it does not matter which datatype is used. However, the calculations tend to be errnous using double due to rounding issues.

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

      But how do we know that without using double data type the answer we get is correct.I did not implement the integer binary search thinking,that,it would give incorrect result,as we need to round off the decimal values.

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

        The calculations can be done using int, there is no special problem. See the example code in tutorial or the vast majority of solutions.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE for problem F with Mo's algorithm and i don't understand why. Somebody please explain what did i miss?

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

    I know some people who got AC with Mo's, but the time limit was very tight, so you might need to micro-optimize and fix your constant factors.

    The bounds are so high that I feel they wanted to discourage $$$\mathcal{O}(n \sqrt(n))$$$ solutions, but the test data wasn't strong enough to catch all of them.

    There is a "proper" way to solve it offline using segment/Fenwick trees.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the time complexity for the geeksforgeeks F solution?

→ Reply