I solved A by checking if there is a letter that is not in the word "Yes", and checking that each Y has s before it, each e has Y before it, and each s has e before it. Also I solved D using lcm, for each i such that 1<=i<=18 check if lcm(n,10^i)/n<=m. If it is, multiply the answer by m/answer

Great round! Hope to see another Div.3 soon. Div.3 almost always meant +ve delta for me, so I am always hyped for them.

To point out, F didn't need a very complex data structure. A single set (a sorted set would be preferrableI just checked, an unordered set worked equally as fast) was enough. If you look at the constraints, you will notice that $$$n \leq 100$$$. Therefore, if you save digits that did exist in the original number and the number after a carry, the size of the set is guaranteed to be less than 200. Now if we follow the process I explained in that another comment, we know we can manage $$$\mathbf{pp}$$$ and $$$\mathbf{pk}$$$ linearly starting from $$$p$$$ and the number of the last digit, and the loop won't take over 200 iterations. This is more than enough to fit in the TL. (I have not tested using an array here though, but the process will be the same anyways.) One great thing to note is that this solution's time complexity only relies on $$$n$$$. Maybe for this reason (and due to some additional constants), my solution turns out to be 5x faster than the jury solution. Good to know!

Here is a submission based on this approach — 181506873.

upd: The TeX for problem D's tutorial seems to be broken. Maybe you forgot come curly braces?

1759D - Make It Round

Here's my clear and concise code for D

#include <iostream>
#define int long long int
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--){
        int n, m;
        std::cin >> n >> m;
        int x = 10, ans = n*m;
     
        while(1){
            int g = std::__gcd(x, n);
            int k = x/g;
            if(k <= m){
                ans = k*(m/k)*n;
            }
            else
                break;
            x *= 10;
        }
     
        std::cout << ans << "\n";
    }
}

Greedy approach : We will try to append as many 0's at the end within given constraint How to find it ?

Let's take input examples : 6 11

• We can have 30 60 90 120 ...
• But only 30 and 60 falls within constraint
• 6*5 = 30, k = 5
• 6*10 = 60, k = 10
• 6*15 = 90, k = 15 not possible

Now we will build our answer by checking if I append zeros can I get some k such that it falls under constraint, once we can't append 0's we will break loop

How to do it? How to find possible values of k? Well it's easy, we can use some mathematics

We will check if I can have some possible number as
z*10
z*100
z*1000
and so on... z [1, 9] z should be minimum possible as we are using greedy

we have our n as 6 so to append 0 at the end I can have z*10
n   = 2*3
ans = z*10
so we have ans = n*k, 1 <= k <= m
n = 6 k = 5  z = 3 ans = 30
n = 6 k = 10 z = 6 ans = 60

How to find k ?
Let g = gcd(x, n) = (10, 6) = 2
then k = x/g = 10/2 = 5, k can take minimum value as 5 within given constraints 
But as we have to find max answer if we append some zeros so we will find k as
k = (11/5)*k
k = 10

Thanks :), You can ask doubt

I solved D with binary search for answer. I think it would be better to add binary search tag to D.

I almost copy-pasted solution for problem E from the editorial and it's giving WA on test 1?!

Submission: 181810855

#include <bits/stdc++.h>
using namespace std;
int g, b;
int solve(vector<int> &a, int n, int i, long long h, int green, int blue) {
	if(i==n) return 0;
	if(h>a[i]) return solve(a, n, i+1, h+a[i]/2, green, blue)+1;
	g=(green?solve(a, n, i, h*2, green-1, blue):0);
	b=(blue?solve(a, n, i, h*3, green, blue-1):0);
	return max(g, b);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		int n;
		long long h;
		cin >> n >> h;
		vector<int> a(n);
		for(int i=0; i<n; i++) cin >> a[i];
		sort(a.begin(), a.end());
		cout << solve(a, n, 0, h, 2, 1) << '\n';
	}
}

For E, shouldn't it be $$$O(NlogN)$$$ instead of $$$O(N)$$$ since you need to sort the astronauts?

Can somebody explain why the solution to D works, or what is the idea about it?

Obviously it is somehow about the number of divisiors 2 and 5 in n, but how?

And how/why does the sol find "If there are several possible variants, output the one in which the new price (value n⋅k) is maximal."?

Problem E: Please someone explain to me why we use solve(0, h, 2, 1) in the initial call, I don't understand why we use 2,1.? what's the logic behind it.?

Can someone explain the segment tree solution for problem G?

For the problem G, can we binary search on the value we put before each element of the input array? For each element, the search space will be the elements in the unused set which are smaller than this element. And to check if a value is feasible, we will check that we still have sufficient options left for rest of the elements if we put this value before the current element in the final array. This can be done using ordered set (refer my solution). We will choose the least among all feasible values, to maintain the lexicographic condition. Also note that the search space will follow monotonicity.

I used the above approach, but got WA on TC3. Solution: LINK

can someone tell me the mistake in my code of problem G. I have done pretty much the same as editorial's approach,but I am getting WA on test case 14. (basically,my code is also including 0 in one of the outputs which I am unable to think of why) https://mirror.codeforces.com/contest/1759/submission/202043617

1759F - All Possible Digits

I implemented the algorithm below, which is O(n) time-complexity and O(n) space-complexity. But still, I am getting TLE for the 7th test case.

Could anyone tell me the error in my code and how I can optimize the algorithm's run-time?

The code can be found here: 218600714

In problem E, I kept failing using non recursive approach, didn't think about the case where you'd use green twice

what a incredible problem E

I was only thinking the recursive DP approaches which were too slow because to it depended on the health tooo, but reading editorial solution made me think I have lot to learn bring more problems like these.

In problem G, After getting the numbers not in the array, I kept track of the number of options available to be placed before each element in b. For example, if n = 8 and b = [8, 7, 4, 5], the numbers not in the array would be [1, 2, 3, 6], and 8 and 7 would both have 4 options (as they are greater than all four numbers not in the array b), and 4 and 5 would have 3 options (as they are not greater than 6).

It makes sense that for the number of options i, at most i elements of the array can have it. Example A: for n = 8, and b = [2, 3, 7, 6], both 2 and 3 have only one option ( 1 ), but only one of them can use it, so there would be no answer. Example B: n = 8 and b = [8, 7, 4, 5], 4 and 5 have three options, so we can use two for them, and that would leave two options for 7 and 8 each.

My solution (in Java) maintained a TreeMap of the numbers of options and the indices of the corresponding elements that have those options. For every iteration, I would check the smallest number of options, and check if the elements having that number are more (which means no answer), or less (which means I have room to give the next smallest number to the next element in b), or equal (which means that they must be given the next smallest numbers).

This seems reasonable to me, and it passed the first two tests. However, I got a WA in test 3, and the test case is hidden. Can someone help me understand what is wrong with my solution? Here is my submission — 270539680.