Atcoder Beginner Contest 174 — Unofficial English Editorial

№	Пользователь	Рейтинг
1	jiangly	3640
2	Benq	3593
3	tourist	3572
4	orzdevinwang	3561
5	cnnfls_csy	3539
6	ecnerwala	3534
7	Radewoosh	3532
8	gyh20	3447
9	Rebelz	3409
10	Geothermal	3408

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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

int x = in.nextInt();
out.println(x >= 30 ? "Yes" : "No");

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

int n = in.nextInt();
long d = in.nextInt();
d = d * d;
Point[] points = Point.readPoints(in, n);

int answer = 0;
for (Point p : points) {
    if (p.x * p.x + p.y * p.y <= d)
        answer++;
}

out.println(answer);

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

int k = in.nextInt();
if (k % 7 == 0)
    k /= 7;

if (gcd(10, k) != 1) {
    out.println(-1);
    return;
}

long v = 1 % k;
int len = 1;
while (v != 0) {
    v = (10 * v + 1) % k;
    len++;
}

out.println(len);

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

int n = in.nextInt();
char[] c = in.next().toCharArray();

int[] w = new int[n + 1];
for (int i = 0; i < n; i++) {
    w[i + 1] = w[i] + (c[i] == 'W' ? 1 : 0);
}

IntUnaryOperator moves = left -> {
    int wrongLeft = w[left];
    int wrongRight = (n - left) - (w[n] - w[left]);

    return wrongLeft + wrongRight - Math.min(wrongLeft, wrongRight);
};

int answer = ternarySearch(moves, 0, n);
out.println(moves.applyAsInt(answer));

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

int n = in.nextInt();
int k = in.nextInt();
int[] a = in.readIntArray(n);

IntPredicate cuts = l -> {
    if (l <= 0)
        return false;
    long c = 0;
    for (int x : a) {
        c += (x - 1) / l;
    }
    return c <= k;
};

out.println(binarySearch(cuts));

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

int n = in.nextInt(), queryCount = in.nextInt();
int[] c = in.readIntArray(n);
for (int i = 0; i < n; i++) {
    c[i]--;
}
Pii[] queries = new Pii[queryCount];
for (int i = 0; i < queryCount; i++) {
    queries[i] = Pii.of(in.nextInt() - 1, in.nextInt());
}

List<Integer>[] byEnd = Util.arrayOfLists(n + 1);
for (int i = 0; i < queryCount; i++) {
    byEnd[queries[i].second].add(i);
}

IntSumSegmentTree st = new IntSumSegmentTree(n);
int[] last = new int[n];
Arrays.fill(last, -1);

int[] answer = new int[queryCount];
for (int i = 0; i < n; i++) {
    if (last[c[i]] != -1) {
        st.update(last[c[i]], 0);
    }

    st.update(i, 1);
    last[c[i]] = i;

    for (int j : byEnd[i + 1]) {
        answer[j] = st.query(queries[j].first, queries[j].second);
    }
}

for (int x : answer)
    out.println(x);

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.

#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; }

Комментарии (43)

Показать архивные | Написать комментарий?

Just__a__Visitor

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.

→ Ответить

raxtar

4 года назад, # ^ |

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.

alon276

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

AnandOza

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

code_warrior

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

I edited an explanation into the post.

AGRU

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

_Sazid_

← Rev. 3 →

I think I have an easier solution for problem D.

Code

#include <bits/stdc++.h>
using namespace std;
     
int main() {
     
    int k, cnt1 = 0, cnt2 = 0;
    cin >> k;
    string s;
    cin >> s;
    for(int i=0; i<k; i++)
        if(s[i] == 'R') cnt1++;
    if(cnt1 == k) 
        cout << 0;
    else{
        for(int i=0; i<cnt1; i++)
            if(s[i] == 'R') cnt2++; //If there is any R already, then there is no need to swap
     cout << cnt1 - cnt2;}
}

saurabh_coder

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

liit_mixer

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

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
	int n,k;cin>>n>>k;
	double a[n];
	for(int i=0;i<n;i++)	cin>>a[i];
	double l=0,r=1e9;
	auto check = [&](double len,int k) {
		int req=0;
		for(int i=0;i<n;i++) {
			int factor = (int)((1.00*a[i])/len);
			req+= (factor - ((factor*len==a[i])?1:0));
			// cout <<a[i]<<" "<<len<<" "<< factor<<"\n";
		}
		return req<=k;
	};
	int count=0;
	while(l<=r && (count++)<1000) {
		double mid=l+(r-l)/2;
		if(check(mid,k)) {
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<int(r+.5)<<"\n";
	return 0;
}

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

aryanc403

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

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!

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.

Umnik

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?

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

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

SecondThread

+29

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

_aadiupadhyay_

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.

hetp111

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.

hossainzarif

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

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

Oh. Sorry. I didn't mean you then.

pop3

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.

shubhanito

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.

non--stop

-17

In problem C Brute force also work

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.

sumit_kk10

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

waltz47

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.

aneee

← Rev. 4 →

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.

"which is <= l"

You mean < l ?

Yes my bad. I meant < l, and that’s what I’ve done in the code too.

spookywooky a little help? :|.

Your AC Code: https://atcoder.jp/contests/abc174/submissions/15664290 See line 74.

How did I forget that! :’(.

Thank you so much! I was analysing my query function this whole time xD.

hardy_9795

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.

spookywooky

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.

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.

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

tejas

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

Shisuko

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.

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

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

A: Air Conditioner

B: Distance

C: Repsept

D: Alter Altar

E: Logs

F: Range Set Query