AnandOza's blog

By AnandOza, history, 9 months ago,

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

 » 9 months ago, # |   +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.
•  » » 9 months ago, # ^ |   +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.
•  » » » 9 months ago, # ^ |   0 I did the same.
•  » » 9 months ago, # ^ |   0 Exactly my solution as well. I think it's the standard solution for such a problem.
 » 9 months ago, # |   0 Auto comment: topic has been updated by AnandOza (previous revision, new revision, compare).
•  » » 9 months ago, # ^ |   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."
•  » » » 9 months ago, # ^ |   0 I edited an explanation into the post.
•  » » » » 9 months ago, # ^ |   0 Thnks sirji!
•  » » 9 months ago, # ^ |   0 Hello , Can you please explain Intuition for problem E , I read the editorial but Not able to get it!:)
 » 9 months ago, # |   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
 » 9 months ago, # |   0 Time to write: $O(1)$ The fastest solution in the west.
 » 9 months ago, # | ← Rev. 3 →   0 I think I have an easier solution for problem D. Code#include using namespace std; int main() { int k, cnt1 = 0, cnt2 = 0; cin >> k; string s; cin >> s; for(int i=0; i
•  » » 9 months ago, # ^ |   +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
•  » » 9 months ago, # ^ |   0 #include using namespace std; int main(){ int n; cin >> n; string str, s; cin >> str; s = str; sort(s.begin(), s.end()); int t = s.length()/2, ans = 0; for(int i=0;i
 » 9 months ago, # |   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#include #define ll long long using namespace std; int main() { int n,k;cin>>n>>k; double a[n]; for(int i=0;i>a[i]; double l=0,r=1e9; auto check = [&](double len,int k) { int req=0; for(int i=0;i
•  » » 9 months ago, # ^ |   +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.)
•  » » » 9 months ago, # ^ |   0 Hello, I don't understand here "So for a log of length x, this takes ⌊(x−1)/L⌋ steps. " Would you please explain in this formula why (x-1)?
 » 9 months ago, # | ← 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.
•  » » 9 months ago, # ^ |   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!
•  » » » 9 months ago, # ^ |   0 I have seen it in the editorial of https://codeforces.com/contest/1129/problem/D . The first half of the editorial explains how to solve this problem and the second half of the editorial solves one div1 D problem.
•  » » 9 months ago, # ^ |   +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?
•  » » » 9 months ago, # ^ | ← 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. SpoilerWith that said I have personally used GFG for reading some interview experiences. But a big NO if are learning algo's and want to do better in CP. You can still use it if you just want to ace an interview.
•  » » » » 9 months ago, # ^ |   +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
 » 9 months ago, # |   +29 Also, here's a video tutorial for people who are interested.
 » 9 months ago, # |   0 Auto comment: topic has been updated by AnandOza (previous revision, new revision, compare).
 » 9 months ago, # |   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.
 » 9 months ago, # | ← Rev. 2 →   0 Can someone confirm that this will TLE ? I think the Time complexity written is wrong in that article.
•  » » 9 months ago, # ^ |   0 Yes, I got TLE in last 3 test cases with this article
•  » » 9 months ago, # ^ |   0 Why just copy paste articles? It ain't taking you anywhere.
•  » » » 9 months ago, # ^ |   0 When did I say that I copied ? I tried the same approach and found this article after the contest ended.
•  » » » » 9 months ago, # ^ |   0 Oh. Sorry. I didn't mean you then.
 » 9 months ago, # |   0 Can anyone give simple explanation for question C?
 » 9 months ago, # |   +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.
•  » » 9 months ago, # ^ |   +1 pop3Let'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)
 » 9 months ago, # |   0 In Problem C, "proof of bound" part, how can you say, " Since k doesn't share any common factor with 10" ? AnandOza
•  » » 9 months ago, # ^ |   0 check out this
 » 9 months ago, # | ← Rev. 2 →   -17 In problem C Brute force also work #include 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; } `
•  » » 9 months ago, # ^ |   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.
•  » » » 9 months ago, # ^ |   0 I updated my solution. It does not require any proof.
 » 9 months ago, # |   0 My solution for D : https://atcoder.jp/contests/abc174/submissions/15606632
 » 9 months ago, # | ← 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.
 » 9 months ago, # | ← Rev. 4 →   0 I am getting WA in 2 tests for Task F. Can someone help me out?SubmissionI 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.
•  » » 9 months ago, # ^ |   +5 "which is <= l"You mean < l ?
•  » » » 9 months ago, # ^ |   0 Yes my bad. I meant < l, and that’s what I’ve done in the code too.
•  » » 9 months ago, # ^ |   0 spookywooky a little help? :|.
•  » » » 9 months ago, # ^ |   +5 Your AC Code: https://atcoder.jp/contests/abc174/submissions/15664290 See line 74.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 How did I forget that! :’(. Thank you so much! I was analysing my query function this whole time xD.
 » 9 months ago, # |   0 Can anyone Explain E in simple words??
 » 9 months ago, # | ← 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.
•  » » 9 months ago, # ^ |   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.
•  » » » 9 months ago, # ^ |   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.
•  » » » » 9 months ago, # ^ |   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.
•  » » 9 months ago, # ^ |   0 Can you please Explain E in simple words??
 » 9 months ago, # |   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?
•  » » 9 months ago, # ^ |   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.
 » 9 months ago, # | ← Rev. 2 →   0 What's the time complexity for the geeksforgeeks F solution?
 » 9 months ago, # |   0 Can anyone please tell me where my solution for problem E fails
•  » » 9 months ago, # ^ |   0 take lowerbound as 1 and not zero.