Блог пользователя AnandOza

Автор AnandOza, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +131
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I think I have an easier solution for problem D.

Code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

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;
}
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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