Editorial for Codeforces Round #739 (Div.3)

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int k;
		cin >> k;

		for (int i = 1; ; i++)
		{
			if (i % 3 == 0 || i % 10 == 3)
				continue;
			if (--k == 0)
			{
				cout << i << '\n';
				break;
			}
		}
	}
}

1560B - Who's Opposite?

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		ll a, b, c;
		cin >> a >> b >> c;

		ll n = 2 * abs(a - b);
		if (a > n || b > n || c > n)
			cout << -1 << '\n';
		else
		{
			ll d = n / 2 + c;
			while (d > n) d -= n;
			cout << d << '\n';
		}
	}
	return 0;
}

1560C - Infinity Table

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int k;
		cin >> k;

		int a = 1;
		int x = 1;
		int i = 1;

		while (k >= x + a)
		{
			x += a;
			a += 2;
			i += 1;
		}

		int m = k - x + 1;
		if (m <= i)
			cout << m << ' ' << i << '\n';
		else
			cout << i << ' ' << (i - (m - i)) << '\n';
	}
}

1560D - Make a Power of Two

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll P2LIM = (ll)2e18;

int solve(string s, string t)
{
	int tp = 0;
	int sp = 0;
	int taken = 0;

	while (sp < s.length() && tp < t.length())
	{
		if(s[sp] == t[tp])
		{
			taken++;
			tp++;
		}
		sp++;
	}

	return (int)s.length() - taken + (int)t.length() - taken;
}

vector<string> ts;

int main()
{
	for (ll p2 = 1; p2 <= P2LIM; p2 *= 2)
		ts.push_back(to_string(p2));

	int t;
	cin >> t;

	while (t--)
	{
		string n;
		cin >> n;

		int ans = n.length() + 1;
		for (auto p2 : ts)
			ans = min(ans, solve(n, p2));
		cout << ans << '\n';
	}

	return 0;
}

1560E - Polycarp and String Transformation

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int cntsrc[26]; // don't forget to memset it but not cnt
int* cnt = cntsrc - 'a'; // so cnt['a'] = cntsrc[0] and so on

pair<string, string> decrypt(string s)
{
	string order;
	reverse(s.begin(), s.end());
	for (auto c : s)
	{
		if (!cnt[c])
			order.push_back(c);
		cnt[c]++;
	}

	int m = order.length();
	int originalLength = 0;
	for (int i = 0; i < m; i++)
		originalLength += cnt[order[i]] / (m - i);

	reverse(order.begin(), order.end());
	return { string(s.rbegin(), s.rbegin() + originalLength), order };
}

string encrypt(pair<string, string> p)
{
	string result = p.first;

	for (auto c : p.second)
	{
		string temp;
		for (auto d : p.first)
			if (d != c)
			{
				temp.push_back(d);
				result.push_back(d);
			}
		p.first = temp;
	}

	return result;
}

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		memset(cntsrc, 0, sizeof(cntsrc));
		string s;
		cin >> s;

		auto ans = decrypt(s);
		auto check = encrypt(ans);

		if (check == s)
			cout << ans.first << ' ' << ans.second << '\n';
		else
			cout << "-1\n";
	}

	return 0;
}

1560F1 - Nearest Beautiful Number (easy version)

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

string solve1(string n)
{
	string res(n.length(), '9');
	for (char c = '8'; c >= '0'; c--)
	{
		string t(n.length(), c);
		if (t >= n)
			res = t;
	}

	return res;
}

string solve2(string n)
{
	string res = solve1(n);

	for(char a = '0'; a <= '9'; a++)
		for (char b = a + 1; b <= '9'; b++)
		{
			bool n_ok = true;
			for (int i = 0; i < n.length(); i++)
			{
				if (n[i] < b)
				{
					string t = n;
					if (t[i] < a) t[i] = a;
					else t[i] = b;
					for (int j = i + 1; j < n.length(); j++)
						t[j] = a;
					if (res > t)
						res = t;
				}

				if(n[i] != a && n[i] != b)
				{
					n_ok = false;
					break;
				}
			}

			if (n_ok) return n;
		}

	return res;
}

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	if (k == 1) return solve1(n);
	else return solve2(n);
}

int main()
{
	int t;
	cin >> t;

	while (t--)
		cout << solve() << '\n';

	return 0;
}

1560F2 - Nearest Beautiful Number (hard version)

Tutorial

Short solution

#include <bits/stdc++.h>

using namespace std;

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	while (true)
	{
		set<char> s;
		for (auto c : n) s.insert(c);
		if (s.size() <= k) return n;

		s.clear();
		int ptr = 0;
		for (; ; ptr++)
		{
			s.insert(n[ptr]);
			if (s.size() > k)
			{
				while (n[ptr] == '9')
					ptr--;
				n[ptr]++;
				for (int i = ptr + 1; i < n.size(); i++)
					n[i] = '0';
				break;
			}
		}
	}
}

int main()
{
	int t;
	cin >> t;

	while (t--)
		cout << solve() << '\n';
	
	return 0;
}

Long solution

#include <bits/stdc++.h>

using namespace std;

string solveFillingSuffix(string& n, char d, int from)
{
	for (int i = from; i < n.length(); i++)
		n[i] = d;
	return n;
}

void decAt(map<char, int>& d, char c)
{
	if (d.count(c))
	{
		d[c]--;
		if (d[c] == 0) d.erase(c);
	}
}

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	map<char, int> d;
	int pref = 0;

	while (pref < n.length())
	{
		if (d.count(n[pref]))
		{
			d[n[pref++]]++;
			continue;
		}
		if (d.size() == k) break;
		d[n[pref++]]++;
	}

	if (pref == n.length())
		return n;

	while (true)
	{
		if (n[pref] == '9')
		{
			decAt(d, n[--pref]);
			continue;
		}

		if (d.size() < k)
		{
			d[++n[pref]]++;
			return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1);
		}

		auto it = d.upper_bound(n[pref]);
		if (it == d.end())
		{
			decAt(d, n[--pref]);
			continue;
		}

		n[pref] = it->first;
		return solveFillingSuffix(n, d.begin()->first, pref + 1);
	}
}

int main()
{
	int t;
	cin >> t;

	while (t--)
		cout << solve() << '\n';
	
	return 0;
}

int n; cin >> n; int y = sqrt(n); if(y*y == n){ cout << y << ' ' << 1 << '\n'; return; } int z = y+1; if(n > z*z - z){ cout << z << ' ' << z*z - n + 1 << '\n'; return; } cout << n - y*y << ' ' << y+1 << '\n';

Comments (84)

Show archived | Write comment?

Wrongy_

3 years ago, # |

← Rev. 5 →

-8

Very Good Round with Balanced Problemsets! Problem C was very interesting to me. Thanks!

→ Reply

ArPiT_PanDeY

3 years ago, # ^ |

-41

How dare you say something wholesome here? No wonder you got downvoted. /s

Jerry__Jiang

-16

It seems that you get downvotes too.):

troolllllllll

They are just spoilt children don't mind them.

prabhav_

C was pretty similar to a CSES Problem-

https://cses.fi/problemset/task/1071

lethan3

+42

Thank you for the round! Problems were interesting and of the right difficulty for a Div. 3.

For problem F1, there's a simpler solution:

Simply generate all beautiful numbers for $$$k = 2$$$, my program counts about $$$80,000$$$. Link

Pie-Lie-Die

Can you please explain what i,j,k,l,m denote in your code?

i and j are the two digits that are in the number. k is the number of digits in the number. I use l as a bitmask to determine which digits are i and which are j. Then I loop over the digits of the bitmask with m and construct the new number, which I insert into the set. I don't let i == j by setting j = i + 1 since that is already covered when the bitmask is all 0 or 1.

Got it. Thanks!

theviz

-30

Prob C was very interesting ngl.

pugnahor25

← Rev. 2 →

-35

Completely agree ! Pre-computing all powers of 2 upto 10^18

+13

That was D i guess

PracticeAlt

One great observation was that the leading row in the table was forming an arithmetic progression with common difference of 2.Great problem

rishabh1889

← Rev. 3 →

Well, not the row elements, but the differences between consecutive elements form an arithmetic progression with a common difference of 2. This is because $$$\sum\limits_{i=0}^{k}2k+1 = k^2$$$ and every element in first row will obviously be $$$k^2 + 1$$$ and numbers $$$2k+1$$$ form an arithmetic progression with a common difference of 2.
Using this, we can also solve it in less than $$$\mathcal O(\sqrt k)$$$. The time complexity will depend on how you calculate the square root.

linkret

+22

I liked all problems. For F I made a dp with bitmasks (normal dp on digits), you could've set the constraints to disallow this solution, because it was pretty brainless (no cases to think about, just "brute-force")

O(T * 2^LEN * LEN), where LEN is the number of digits of N.

sam000013

-12

But don't you think this thing is above Div3 level for like 98% official particpants of Div3?

+25

idk I never went to Div3 before, thinking carefully about many cases can be harder and more tricky.

zenolus

I implemented a similar solution (126326225) with complexity O(LEN * 1024) per test case. However, I feel considering a Div. 3 round, it wouldn't be brainless for official participants to think of a Digit DP there. However, what could have been changed was that instead of bombarding with 10^4 test cases, the length of the number could have been increased to let's say N <= 10^1000.

defnotmee

Could you elaborate on how the recurrence of the dp worked?

alwerty

Isn't it O(T*2^LEN)?

EDIT: No, there is popcount in every recursion

You can avoid popcount by having a 4th argument (which you don't need to use for memoization). So, ll dp[1<<10][10][2] but the function ll solve(int mask, int pos, bool flag, int popcount) { ... } . But this does not change the complexity

_kite

linkret I see no do major difference in our approach ( sorry , if there is) Can you tell why mine is TLE ? Here is my submission 126427896

I think it's better to always count the bits, and immediately return INF if there are too many, instead of just doing it in the end.

Hey [user:linkert] even after that , for clearing the array the whole complexity is (10^4 * 2^10 * 10 * 2) . Shouldn't it be TLE ?

2*10^8 is fast enough for Codeforces, even 10^9 is, too. My solution is about 100ms.

Counting bits worked and AC

thelastenvoy29

Hey , can you explain the approach a bit too?

DP (memoized recursion). Use a bitmask to remember which digits from 0 to 9 have already been used. The number of 1s in this bitmask will tell you the number of different digits you had used: it must not exceed K.

In the DP, try out every possible digit for the current position, and move to the next position, adding it to the bitmask.

Also you will need to keep track of a 3rd state, weather the number you are currently building (from left to right) is already larger than the target number N, or not. Whenever you choose a digit larger than the corresponding digit of N, from then on you will always be larger and those dp states are allowed to choose any digits. But if you are not already larger than N, then it is not allowed to choose the current digit that is LESS than the corresponding digit of N. And if you choose the same digit, then the next recursion call still has to be careful (since it is not yet larger). You can google "digit dp" to get a better explanation about this part.

fie_claussell

Just curious, how did you come up with problem E? What motivated this particular string construction?

It was a nice problem :)

brobat

A clean solution for C

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 200100
#define MOD 1000000007
 
void solve() {
    int k;
    cin >> k;
    int n = ceil(sqrt(k));
    int diff = n*n - k;
    if(diff >= n) {
        cout << 2*(n-1) - diff + 1 << " " << n << endl;
    }
    else {
        cout << n << " " << diff + 1 << endl;
    }
 
}
 
int32_t main() {
    int t; cin >> t; while(t--)
    {solve();}
    return 0;
}

lis05

$$$sqrt()$$$ runs in $$$O(logK)$$$

hydroshiba

+11

I'm not pretty good at math, so I solved C using binary search.

I noticed that the last number of the $$$i_{th}$$$ row is $$$i^2$$$, so I do a binary search to find the row which $$$n$$$ belongs to. Then the starting number of the new column is $$$i^2 + 1$$$ (let's call this $$$start$$$), thus the number $$$corner$$$ at the position $$$(i + 1, i + 1)$$$ is $$$start + i$$$.

I finally check whether $$$n$$$ exceeds $$$corner$$$ or not, if it does then the answer is $$$(i + 1, i + corner + 1 - n)$$$, else the answer is $$$(n - start + 1, i + 1)$$$

Here's my submission

aaaaa123

Why does the short solution in F2 work in m^2 ? Couldn't figure it out:(

Btw problems are pretty good!!

kfqg

Suppose n = 789152352 and k = 3. Then the algorithm takes you to:

789200000

789300000

789400000

789500000

789600000

789700000

Now this is a special point in the algorithm. The fourth character of the number is now among the 3 previously used digits, and now you just have to fill the 0's.

This act of "filling in the 0's" is O(M^2). (For each of the 0's, you have to do O(M * B) work where B the base, in this case the number is base 10 so B = 10. And there are O(M) 0's. So in total it is O(M^2 * B). Or just O(M^2) since B = 10, is a constant.)

There is another case, where you have to "loop around" because the character that was being incremented (in this case the 1 got incremented to 2, 3, .., then 7) hit 9 and then looped back around to 0. For example, if:

n = 456713538, k = 3. Then you have to do:

456800000

456900000

457000000

But you still end up with a state where now you just have to "fill in the 0's". Again O(M^2).

pst1823

+18

Example test cases were really handy for giving AC in one go.. DigitForces

UIgoku_watchMeTurnRed

-17

My O(1) solution to the problem C. CLICK

DioHERO

it is O(40000 * 100)

As a newbie I just wanted to show my solution and hopefully get some feedback ( which apparently I got ). Maybe my rating is what made you all to downvote. I was working hard, but now I'll double my hard work. Ciao :)

aniervs

← Rev. 7 →

Problem A could be solved in $$$\mathcal{O}(1)$$$ time complexity:

The unit digit is cyclic, and the cycle's length is 10.
The sequence of remainders when dividing by 3 is cyclic, and the cycle's length is 3.

Let's define $$$f(x)$$$ to be $$$1$$$ if Polycarp likes $$$x$$$, and $$$0$$$ otherwise. Then, $$$f(x)$$$ is cyclic, and its cycle's length is $$$lcm(3, 10) = 30$$$.

We can compute the number of liked numbers among the first $$$30$$$ positive integers, let's call it $$$M$$$. Let's also say that there are $$$T$$$ contiguous ranges of size 30 between 1 and the number we're looking for (excluding that number).

Then $$$T \cdot M < K$$$, which means that $$$T = \left\lceil\frac{K}{M}\right\rceil - 1$$$. Now, we just need to find the $$$(K-T\cdot M)$$$-th liked number strictly greater than $$$30\cdot T$$$, which is less than 30 steps away from $$$30\cdot T$$$.

OO_Jaane_Jana

Can anyone tell me that in the problem B can there be any testcase like:-

1 2 2

as 2 people are in the circle 1 is next to 2 and we have to output the person next to 2.

While I am hacking my solution by myself it's showing invalid input

ujjwal_keshri

No a,b,c should be distinct

kushagra219

I solved D 30s after contest got over. Worst feeling ever :/

jeal0uspengu1n

I submitted E after a min, and man I felt sed cause my rank was pretty low and I hadn't solved D

rahul_rax

E was easier to observe, but I wasted all my time on F1 and couldn't even solve it. Bad luck for me.

atleast you solved D orz ;)

Dev_Manus

" Let's iterate a prefix of n starting from the empty one so that the prefix will be the prefix of x. This prefix must contain only the digits a and b" can someone explain what this means. Problem F1

shivambhagat02

Look at my submission for problem D. Link: https://codeforces.com/contest/1560/submission/126381278

Why this is getting TLE

neUwUbie_for_ever

I submitted your code in pypy3 it passed

https://codeforces.com/contest/1560/submission/126414861

AURRUM

-27

MathForces

gigaByte.org

Guys i had submitted solution for E problem with the same logic. It ran fine in my local IDE but codeforces gave wrong answer on test 1. Is this some bug in the codeforces or is there some part of the code which is wrong. Please do let me know.

126357466

Thank you.

it gave WA on my machine too, it is very messy so I couldn't find the mistake, maybe you could add some comments.

Birdcantfly

I solved F1 and F2! At 2 minutes after contests finished. :(

ehh, that sucks, but you know that you are good enough to even Fs in Div3, now you can try increasing speed:)

ganesh_6

You did it very fast from A to D. Any tips on how to increase speed?

I try giving virtual contests, would recommend that, or you can do mashup of problems within time limit. Basically, solving problems in a timed environment helps ig.

skartik

For problem E, this submission gives different output on CF judge and local machine for some inputs, for e.g. for the i/p string v

Output of the above submission on OJ is -1, but when I run locally, the o/p is v v.

Can anyone please help in figuring out why this is happening.

I submitted your solution with GNU G++17 compiler and it gave Runtime error on test 2. I have faced problem like yours on codeforces too and submitting on GNU G++17 compiler always helped me.

This is my code for F2.

IshtiaQ99

Can you please explain your idea?

It's just to adjust each digit from high to low.

Please explain why you did this way

optozorax

Very clean code, thanks!

BreakPlus

It's a pity that I didn't attend.

Tsovak

+10

I have another solution for Problem F2.

First, take the longest prefix of $$$n$$$, such that there are at most $$$k$$$ distinct digits. Let's call that prefix $$$p$$$.

If $$$p = n$$$, the answer is $$$n$$$.

Otherwise, let's call $$$i$$$ as the first index after $$$p$$$ (for example: if $$$n = 199754$$$, $$$k = 3$$$, then $$$p$$$ will be $$$1997$$$ and $$$i$$$ will be $$$4$$$ (indexes start at $$$0$$$)).

Now find the minimum $$$x$$$ such that $$$p$$$ contains $$$x$$$ and $$$x$$$ is greater than $$$i-th$$$ digit of $$$n$$$ ($$$x$$$ can't be equal to $$$i-th$$$ digit of $$$n$$$, because in that case you can choose longer prefix than $$$p$$$).

Now there are $$$2$$$ cases:

If $$$x$$$ exists, change the $$$i-th$$$ digit of $$$n$$$ into $$$x$$$. Then change the all remaining digits of $$$n$$$ (from $$$i+1$$$ to the last) into the smallest number in $$$p$$$.
Otherwise, you can see that all digits of $$$p$$$ are less than $$$9$$$ (because in that case the $$$i-th$$$ digit of $$$n$$$ can't be bigger than all digits of $$$p$$$). Now you have to change one of the digits of $$$p$$$ into a bigger one. It's easy to see that you have to change the digit which have the biggest index. Lets call that index $$$j$$$. At fist $$$j$$$ will be $$$i-1$$$. Now if you want to change $$$j-th$$$ digit (let's call it $$$a$$$), insert all digits before $$$j$$$ (from $$$0$$$ to $$$j-1$$$) into a $$$multiset$$$. Let's call that $$$multiset$$$ $$$s$$$. Now there are $$$3$$$ cases:

If $$$s$$$ doesn't contain $$$a$$$, change $$$a$$$ into $$$a+1$$$ and insert $$$a+1$$$ into $$$s$$$. Now if $$$s$$$ contain less than $$$k$$$ distinct digits, change all remaining digits into $$$0$$$, otherwise, change them into the smallest digit in $$$s$$$.
If $$$s$$$ contains $$$a$$$, check if there is a digit in $$$s$$$ greater than $$$a$$$, find that minimum digit (let's call it $$$b$$$), change $$$a$$$ into $$$b$$$, then insert $$$b$$$ into $$$s$$$. Now if $$$s$$$ contain less than $$$k$$$ distinct digits, change all remaining digits into $$$0$$$, otherwise, change them into the smallest digit in $$$s$$$.
Otherwise $$$j$$$ will become $$$j-1$$$ and the digit before $$$a$$$ will be deleted from $$$s$$$ (after this $$$s$$$ may contain the digit before $$$a$$$).

Time complexity: $$$O(len$$$ $$$\mathrm{log}$$$ $$$len)$$$, where $$$len$$$ is the number of digits of $$$n$$$. This means that this solution will also work for $$$n \leq 10^{10^5}$$$ or even for bigger $$$n$$$.

My code

ngochauhoang_9A

May I ask you 1 thing ? Does this contest rates for people who are having rating under 1600? - If yes, why I have been rated yet ? - I need an answer.

Kevin114514

If there's no blog updates or notifications saying it's unrated,it will be rated for you. Just wait :)

Thank you very much. I received the scores. :)

tomnjerry18

Great Contest, I became pupil for the first time.

Congratulations!

Why my $$$O(t2^{10}mk)$$$ solution got $$$Accepted$$$ for problem F2...

upd : got hacked lol

Ah you get hacked,orz!

SPyofgame

I think we have the same approach but I break when the value will only rise, that will only take $$$O(2^k \times m \times 2)$$$ memory but $$$O(mk)$$$ query

senR

For problem C, I got my answer wrong on just one number: 999950883 . Can someone please tell why did this happen. Is this number special in some terms? My submission link: https://codeforces.com/contest/1560/submission/126314408

ZergTricky

Disliked this contest, 7 constructive/greedy approaches, really? Nothing educational/interesting. Your div.3 #734 was far more better: it had cool dp and graph problems.

opPO

I have the same opinion.

vandijk

Very good Editorial,and very good problem!

especially for problem F2,a short solution and a long solution are very good for readers.

And it is pretty suitable for beginner coders!

AATANK

Problem C is similar to the CSES Number Spiral, here is the O(1) solution comparatively easy from the editorial.

sqrt() doesn't work in $$$O(1)$$$. It works in $$$O(\mathrm{log}$$$ $$$n)$$$.

2rally

I really liked this contest, genuinely enjoyed doing problems C,D,E,F.

CrocHold

what kind of error is this?"wrong answer order too long"...everything seems alright...getting all the outputs that are visible, matching...can someone help? string trans problem https://codeforces.com/contest/1560/submission/126609563

haajihaa2508

Can anyone please help me with understanding why this code gives TLE though it's mostly similar to the solution given in editorial. https://codeforces.com/contest/1560/submission/126656613

paliwalap7

Can anyone please provide more beginer friendly tutorial for problem D. I understand the whole, but didn't understand how we come to consider power of two that are less than 10^18. I understand why it is needed but don't know how to approach so that figure out power should be less than 10^18(20digits) long.

Flyed

2 years ago, # ^ |

Because max length of input string n is 9 bc n < 10^9 except 10^9 itself. You can always delete all 9 digits and add a 1, making the total 10 moves. Or for 10^9, just delete all the zeroes, which is also 9 moves. That means there's no reason to go past powers of two greater than 18 digits, because starting from 19 digits, you can just make the number 1 instead. So, you only have to check powers of two < 10^18.

sidakbhatia

2 years ago, # |

I brute-forced my way through problem E and it worked. The algo I used was after finding order in which elements were to be deleted, I took a string s0 which contained all k unique elements to be deleted, then I made a string s1 delting first elment to be deleted.

eg:s=polycarppoycarppoyarppyarppyrpprppp

s0=polycar s1=poycar

After this I used to rabin-karp to find all occurences of s1 in input string s then I kept updating my s0

v=[first index of occurence of s1 in s]

for all j in v

s0=[0.....j-1]

then I applied the algo given in qs to see if it worked. The solution worked. But shouldnt it be n^2 in worst worst case? Maybe the test cases were weak

https://codeforces.com/contest/1560/submission/145174200

MrPaul_TUser's blog