Idk if this only happened to me, but I had to redownload input for 5 times. After that I couldn't create submission and got repetitive error responses. (Probably, I requested too much download) Then, the timer expired and I sent my output and code to clar within a minute and they made a submission for me.

It's weird that I could attach and send my submission in clar just fine, but not problem B.

You might misunderstand the notation here.

$$$(a + b)|b^2$$$ means that $$$b^2$$$ is divisible by $$$a+b$$$.

Yes. I'm talking about B2. :)

It should be reduced to count pair $$$(a, b)$$$ such that $$$(a+b) | b^2$$$

You just need to prove that if $$$(a + b) | b^2$$$ then $$$(a+b) | gcd(a,b) b$$$

It's actually enough to iterate over all factors of $$$b^2$$$ that no more than $$$b+n$$$

MikeMirzayanov salyg1n geranazavr555

I registered to this contest when I was 2100+, so I was labeled as out of competition. The rating is not updated for me. Can you fix this?

Asia Pacific, Thailand, Chulalongkorn University, Lucina, Mentholzzz,PineapplesOnPizza

Not direct duplication, but sub-problem with minor details different.

1479D - Odd Mineral Resource General case for tree. Ask for any valid answer. Input is not encoded.

1771F - Hossam and Range Minimum Query The tree is line graph. Ask for minimum answer. Input is encoded for online query.

Btw, most solutions on 1479D - Odd Mineral Resource are already online query and finding minimum.

The issue is in your struct node. The default opeator $$$=$$$ seems to have bug and writing constructor can fix it. 189669100

I believe this is some kind of GCC bugs. And I faced this exact issue years ago as well. 85383716

My issue back then was also in this line

struct segment_tree {
       node sg[nax << 2] = {};
};

After that, I never use default assignment in struct again and always write constructor instead.

The reason it worked on your computer might be because you use later version of GCC and this is already fixed on that version. But the GCC version is not updated here very frequently, so I guess we can do nothing, but wait or request for the new update.

SlavicG

Is something wrong with the checker of problem F? I tried to hack and kept getting "Unexpected verdict" result.

There are several duplicated problems in the past, but they never made a round unrated because of duplication. So I think it's still rated. (Though, I think it should be unrated in my opinion. I didn't like free rating like this very much.)

Yeah, got first solve on F because of this. lol

I used the same approach, but I also can’t prove it. But I know how to achieve it. Each position of B can be expressed as "not shifting in range [l, r]" which is equivalent to

~[x >= l and x <= r] = (~(x >= l) or (x >= r + 1)).

Now the requirement is just AND product of all boolean clauses which is nothing, but 2-SAT. I thought that they put some problems to practice Atcoder library, turned out that I overcomplicated things up. lol (They didn’t add library yet, so I got compile error.) code

There is one abs() outside namespace std and that abs() doesn’t support long long as argument. Change your code to std::abs() and it should work fine. 91432176

Usually, you can find $$$a_i$$$ from $$$A(x)$$$ if the function is expandable with taylor serires.

$$$a_i$$$ is simply $$$i-th$$$ term after you do partial fraction and expand it with taylor series.

For example, $$$A(x) = \frac{2x}{1-x^2} = \frac{1}{1-x} -\frac{1}{1+x} = (1+x+x^2+x^3+...)-(1-x+x^2-x^3+...) $$$

$$$=2(x+x^3+x^5+....)$$$ Then, you get $$$a_i=2$$$ if $$$i$$$ is odd, otherwise zero.

For Fibonacci number, I think explanation in generatingfunctionology (The book linked on the top of blog) is quite good.

I think the main part of this problem is how to find k-smallest elements sum. Usually you can do this by binary search tree, so treap can do the job. The easiest way to implement for me is to use segment tree that each node store pair of (number of element, sub of element) in subtree. To get sum of k-smallest elements. Check if left node size greater than k or not. If yes, try searching on left subtree, otherwise subtract sum of left subtree and search on right subtree. Fenwick tree can also do the job if you keep two fenwick trees that one store sum and one store number of elements and use binary lifting or binary search to find sum of k-smallest elements.

I saw many people solve using priority_queue or multiset, but I don't know how it works though.

Edit: I think I get it now. It’s similar to finding median by priority_queue or multiset. Notice that k is always increasing. So you can simply do the same thing. When you encounter query, just transfer elements between 2 multiset respected to value of k. The total number of operations will still be $$$O(n)$$$

I manage to make it compile now. Thanks for reply! The reason is I wrote this in my segment tree code.

node sg[nax << 2] = {};

erase "= {}" part fix the issue. I write this since I think it can prevent UB sometimes, probably it causes me UB this time...

What's the limit for compilation time? I submitted my code for E2 nearly the end of contest and got this verdict. "Can't compile file: Compilation process timed out." I guessed the reason is that my code is too long, but I don't think I can make it significantly shorter. Do you know how to make it compile?

85381670

Yeah, I messed things up a bit. Thanks for telling. :)

For me the useful idea is, $$$a+b=(a\oplus b)+2$$$(a & b)$$$ $$$. I didn't find this during that contest and thought it's quite tricky. The idea of digit dp is quite simple in my opinion.

I think F is quite similar to 1325D - Ehab the Xorcist. Knowing idea of this problem could be a massive help.

Agree. I have to read D and E many times to understand them correctly. The statements are easy to cause confusion.

You seemed to miss the case when there is no multiplicative order. ($$$ d|b$$$)

Oh, that’s strange. I thought that the test cases might be weak because my code gave wrong answer with that test case too. Turned out that I was wrong. I tested by hand and it did give correct answer too. I’ve tested many submissions, but I found only your codes having the same issue. I still don’t get the reason.

I test your code and think that it fail on this testcase.

I tested like this. Am I missing something?

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
string hidden = "#RBRRBBRBBR";

int askRow(int s, int n) {
	//cout << "?";
	int R = 0, B = 0;
	for (int i = s+1; i <= s+n; ++i){
        if(hidden[i] == 'R') R ++;
        else B ++;
    }
	//cout << ' ' << i;
	//cout << endl;

	string res = (R > B) ? "Red" : "Blue";
	//cin >> res;
	return (res == "Red") ? 1 : -1;
}
int askEq(int i, int s, int n) {
	//cout << "? " << i+1;
	int R = 0, B = 0;
	for (int j = s+1; j < s+n; ++j) {/*
		if (j > 2*n) cout << ' ' << j - 2*n;
		else cout << ' ' << j;*/
        int t = (j > 2 * n) ? (j - 2 * n) : j;
        if(hidden[t] == 'R') R ++;
        else B ++;
	}
	//cout << endl;

	string res = (R > B) ? "Red" : "Blue";
	//cin >> res;
	return (res == "Red") ? 1 : -1;
}

const int N = 100;
int col[2*N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	// Ask first N. Shift window right one-by-one until the answer changes.
	// Since last N must have opposite answer, this happens at some point.
	// Binary search where it happens. Note that we don't need to find the first such position.
	// 1 + log2(100) ~ 8 < 10

	int x = askRow(0, n); // Sum of first n has more of x
	int low = 1;
	int high = n;
	while(low != high) {
		int mid = (low + high) >> 1;
		int y = askRow(mid, n);
		if (x != y) high = mid;
		else low = mid + 1;
	}

	// Now askRow(low-1, n) and askRow(low, n) give different answers, hence both colors appear an equal number of times in [low, low+n-2].
	for (int i = 0; i < low; ++i) col[i] = askEq(i, low, n);
	for (int i = low; i < low + n - 1; ++i) col[i] = askEq(i, low + n, n);
	for (int i = low + n - 1; i < 2*n; ++i) col[i] = askEq(i, low, n);

	cout << "! ";
	for (int i = 0; i < 2*n; ++i) {
		if (col[i] == 1) cout << 'R';
		else cout << 'B';
	}
	cout << endl;
}

This problem can be solved by seive. The main idea is as followed.

Let $$$f(g)$$$ be the summation of pair which their gcd is equal to $$$g$$$. Then we can write $$$f(g)$$$ as ...

$$$f(g) = $$$ $$$ \sum_{gcd(i,j) = g} \lfloor{\frac{j}{i}} \rfloor$$$ $$$ = \sum_{g | x, g | y} \lfloor{\frac{y}{x}}\rfloor - \sum_{d \ge 2} f(g * d)$$$.

You should iterate $$$g$$$ from $$$n$$$ to $$$1$$$ to calculate this with seive. The key idea is to calculate $$$ \sum_{g | x, g | y} \lfloor{\frac{y}{x}}\rfloor $$$ in $$$O(1)$$$ while doing seive. (Not hard)

The answer is $$$f(1)$$$. Code (If you want)

I participated in national round at the same place before, today practice session is much better than the national round, I think. The issues in national round are as followed.

• Judging system didn’t accept any solutions for 1-2 hours. (The contest was extended by 30 minutes because of that.)

• In many problems, we had to wait like 10+ minutes for the result.(It was faster when the contest was almost finished.)

• The internet was broken nearly the end of the contest. We almost cannot submit one task in time.

• Maybe I was too bad at Ubuntu, so I asked the staff how to copy input from pdf and paste in terminal. Surprisingly, the staff didn’t know either, so we have to do input manually. (However, they figured how to do it later and told us.)

• The order was randomized as well. I don’t know the reason too.

Gladly, there was no problem with statements in that round. I hope there are no issues like these tomorrow.

I think you mean about div.3? If it’s that case, check this. It was rolled back once, but still not completely fixed.

How can someone with rating >= 1900 register in div.2? :P Or CF doesn’t care about division anymore? I saw some blue competed as rated in last div.3.

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

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

I can’t register for the contest unofficially. Is something wrong? Edit: Can now.

Go! Ps. I didn't implement this myself. Ref to this blog. :)

You should pick one. scanf,printf or cin/cout with fastio.

I think it's because of digit function in your code. I think it's $$$O(q*digits^2*log(n))$$$ in worst case.

Consider subsequence in [3,6]. The longest non-decreasing in input is 2, but your example is 3.

My $$$O(P^2 log(P))$$$ (I was just naively computing power by binary exponential) got TLE, so I had to optimize to $$$O(P^2)$$$. :( What is execution time of your solution?

My solution works in $$$O(P^2)$$$. Let $$$S(i,x) = \frac{\prod_{j=0}^{p-1} (x-j)}{x-i}$$$

The answer is $$$f(x)=$$$ $$$\sum_{i=0}^{p-1} \frac{\prod_{j=0}^{p-1} (x-j)}{x-i}*(\frac{a[i]}{S(j,j)})=\sum_{i=0}^{p-1}S(i,x)*\frac{a[i]}{S(i,i)}$$$

You can compute this in $$$O(P^2)$$$

Notice that when we compute $$$f(t)$$$ if $$$i \ne t$$$, $$$S(i,t)*\frac{a[i]}{S(i,i)}$$$ is always equal to $$$0$$$

So the only value left is $$$S(t,t)*\frac{a[t]}{S(t,t)} = a[t]$$$ which is what we want.

I don't know if this technique is well-known, but this was taught at my school about how to construct polynomial when we get set of $$$(x,f(x))$$$.

submission

Your size of array is not big enough.

If you send data without reference to function, the function will copy the value first. So complexity of each checking is $$$O(n)$$$. Sending reference as vector& and you will get AC. I think.

If $$$|S| \lt |T|$$$, it will never contain $$$T$$$ as its substring. When $$$|S| \gt |T|$$$, it has a chance that concatenating it again can make more copies of T as its substring. So we will concatenate it one more time although its length is now greater than $$$|T|$$$. Of course, concatenating doesn’t reduce the number of copies of $$$T$$$ nor get rid of $$$T$$$ in its substring, but cause bigger constant factor.

Not related to your question, but I have more optimized submission.(Cutting out log factor) Execution time is not that bad.(65 ms)

Link: https://atcoder.jp/contests/abc135/submissions/6593400

I have one bad solution for F. (Very slow and naive)
At first, like everyone, concatenate $$$S$$$ with itself until its length greater than $$$|S|+|T|$$$. Then, we want to find the greatest number of copy of $$$T$$$ which is substring of current $$$S$$$. There are many ways to do, but to be more naive, I did binary search and $$$KMP$$$ to find it. How to know if the answer is not $$$-1$$$? There are a lot of better ways to do, but I concatenate $$$S$$$ with itself one more time and did the same thing as previous $$$S$$$.

If the answer is greater than the previous one, then the answer is $$$-1$$$. Otherwise it's our answer.

Time complexity: $$$O((|S|+|T|)log(|S|+|T|))$$$ (with a very big constant)

Not recommend to do this solution. I have to optimize lots of things to make this naive brute force get AC. Submission link:https://atcoder.jp/contests/abc135/submissions/6585502

Yes, each path will be considered twice. There is a line $$$k*=2$$$ in his submission.

Why didn't you send a single announcement that you updated problem B statement? I didn't refresh and wasted a lot of time with it.

I think Summer informatics School like Codeforces Round 530 (Div. 2).

Hint :$$$(x-y)(x+y)(x^2+y^2)=(x^4-y^4)$$$

https://mirror.codeforces.com/blog/entry/53960 I learned from this blog. I think the explanation is quite good and there is a list of problems.

The first thing that popped up in my mind after reading E is 1106F - Lunar New Year and a Recursive Sequence too. Sad that I can't implement in time. Also, editorial solution for E is little tricky. I like it. Thanks for the problemset. :)

C is extremely hard to me. lol In my opinion D is easier than C. :)

I also got WA test 3. You should check in your connect function that you don't connect the same element.

I got WA from 15th test. But after I changed long double to double, I got pretest passed. I don't know why it passed too. High chance to fail system test.

Both of them would be fine. :) From the fourth condition, we can guarantee that $$$f=\frac{n}{2}-x-i \lt =a[3]+a[4]$$$. If you understand the concept, you will know that we can choose any $$$f$$$ numbers from $$$q[3],q[4]$$$ which is always possible since $$$f \lt =a[3]+a[4]$$$.(if it passed four conditions in my code). Of course, $$$f \gt a[3]$$$ is not necessary. It’s just alternate way of implementation. Sorry if array $$$a[]$$$ makes you confused, you can think of it as $$$q[].size()$$$ instead. :)

$$$f$$$ is the total of numbers need to be printed after printing values from $$$q[1]$$$ and $$$q[2]$$$. If $$$f \gt a[3]$$$ means that we have to use values from both $$$q[3]$$$ and $$$q[4]$$$, otherwise the value from $$$q[3]$$$ is enough( There is else statement before return 0). It's just more convenient for me to implement this way. It's not necessary. Array $$$a[]$$$ is not necessary too since we can use $$$q[].size()$$$ instead. My submission is still a bit messy.

There is simple O(n) solution for this problem. We have a + b + c + d = n / 2 and b + c + 2d = n_b + n_d which can reduce to a - d = n / 2 - n_b - n_d which can brute force in O(n). See my submission 51116077.