1183A - Nearest Interesting Number

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int sum(int a) {
int result = 0;
while (a > 0) {
result += a % 10;
a /= 10;
}
return result;
}
int main() {
int a;
cin >> a;
while (sum(a) % 4 != 0) {
a++;
}
cout << a << endl;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int j = 0; j < n; ++j) {
cin >> a[j];
}
int mn = *min_element(a.begin(), a.end());
int mx = *max_element(a.begin(), a.end());
if (mx - mn > 2 * k) cout << -1 << endl;
else cout << mn + k << endl;
}
return 0;
}
```

Idea: MikeMirzayanov and Vovuh and BledDest

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
long long k, n, a, b;
cin >> k >> n >> a >> b;
k -= n * a;
if (k > 0) {
cout << n << endl;
} else {
k = -k;
++k;
long long diff = a - b;
long long turns = (k + diff - 1) / diff;
if (turns > n) {
cout << -1 << '\n';
} else {
cout << n - turns << '\n';
}
}
}
return 0;
}
```

1183D - Candy Box (easy version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int t = 0; t < q; ++t) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
sort(cnt.rbegin(), cnt.rend());
int ans = cnt[0];
int lst = cnt[0];
for (int i = 1; i <= n; ++i) {
if (lst == 0) break;
if (cnt[i] >= lst) {
ans += lst - 1;
lst -= 1;
} else {
ans += cnt[i];
lst = cnt[i];
}
}
cout << ans << endl;
}
return 0;
}
```

1183E - Subsequences (easy version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
string s;
cin >> s;
int ans = 0;
queue<string> q;
set<string> st;
q.push(s);
st.insert(s);
while (!q.empty() && int(st.size()) < k) {
string v = q.front();
q.pop();
for (int i = 0; i < int(v.size()); ++i) {
string nv = v;
nv.erase(i, 1);
if (!st.count(nv) && int(st.size()) + 1 <= k) {
q.push(nv);
st.insert(nv);
ans += n - nv.size();
}
}
}
if (int(st.size()) < k) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
```

1183F - Topforces Strikes Back

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n;
cin >> n;
set<int> st;
for (int j = 0; j < n; ++j) {
int x;
cin >> x;
st.insert(x);
}
int ans = 0;
int mx = *st.rbegin();
if (mx % 2 == 0 && mx % 3 == 0 && mx % 5 == 0) {
if (st.count(mx / 2) && st.count(mx / 3) && st.count(mx / 5)) {
ans = max(ans, mx / 2 + mx / 3 + mx / 5);
}
}
vector<int> res;
while (!st.empty() && int(res.size()) < 3) {
int x = *st.rbegin();
st.erase(prev(st.end()));
bool ok = true;
for (auto it : res) ok &= (it % x != 0);
if (ok) res.push_back(x);
}
ans = max(ans, accumulate(res.begin(), res.end(), 0));
cout << ans << endl;
}
return 0;
}
```

1183G - Candy Box (hard version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
scanf("%d", &n);
vector<int> cnt(n);
vector<int> cnt_good(n);
for(int i = 0; i < n; i++)
{
int a, f;
scanf("%d %d", &a, &f);
--a;
cnt[a]++;
if(f) cnt_good[a]++;
}
vector<vector<int> > types(n + 1);
for(int i = 0; i < n; i++)
types[cnt[i]].push_back(cnt_good[i]);
int ans1 = 0;
int ans2 = 0;
multiset<int> cur;
for(int i = n; i > 0; i--)
{
for(auto x : types[i]) cur.insert(x);
if(!cur.empty())
{
int z = *cur.rbegin();
ans1 += i;
ans2 += min(i, z);
cur.erase(cur.find(z));
}
}
printf("%d %d\n", ans1, ans2);
}
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
solve();
}
```

1183H - Subsequences (hard version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1e12;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
long long k;
cin >> n >> k;
--k; // the whole string costs nothing
string s;
cin >> s;
vector<vector<int>> lst(n, vector<int>(26, -1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
if (i > 0) lst[i][j] = lst[i - 1][j];
}
lst[i][s[i] - 'a'] = i;
}
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
for (int i = 0; i < n; ++i) {
dp[i][1] = 1;
}
for (int len = 2; len < n; ++len) {
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
if (lst[i - 1][j] != -1) {
dp[i][len] = min(INF64, dp[i][len] + dp[lst[i - 1][j]][len - 1]);
}
}
}
}
long long ans = 0;
for (int len = n - 1; len >= 1; --len) {
long long cnt = 0;
for (int j = 0; j < 26; ++j) {
if (lst[n - 1][j] != -1) {
cnt += dp[lst[n - 1][j]][len];
}
}
if (cnt >= k) {
ans += k * (n - len);
k = 0;
break;
} else {
ans += cnt * (n - len);
k -= cnt;
}
}
if (k == 1) {
ans += n;
--k;
}
if (k > 0) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
```

Can somebody explain how we solve B with Binary Search?

Here it is bro- https://codeforces.com/contest/1183/submission/56148789

i don't understand the idea bs, could you explain

See our search space is (maxElement-k to maxElement+k). Our answer lies between this interval. Now we binary search using the condition (minElement-mid)<=k) If our minElement satisfies this condition then all elements will surely do so we check for only minElement. and then we take max of all possible values.

Thanks

Set

`low = min(A) + k`

and`high = max(A) + k`

, and use binary search to find out the result in this range.For problem B, initially I wrote binary search solution for answer. But, it seems it is giving $$$-1$$$ for some valid case too.

Can someone please help me identify the mistake in my submission ?

I wrote almost the same solution but I got WA on test 3 :(

https://codeforces.com/contest/1183/submission/56084413

Ok, I get it. Even if for a certain value, we cannot satisfy the conditions, It does not mean that the answer should be less than the value, the answer can be more than the current value too.

For eg, Your array is 2 2 5 10 and let K be 4, the lower bound is 0 and the upper bound cannot be greater than (min+K). So you first check for (0+6)/2 = 3 (as mid). You see that condition is not satisfied as (10-3)>4, so you conclude that answer should be less than 3, which is not true, since the value 6 satisfies all the condtions.

So, I think that Binary Searching the Answer cannot work for this problem.

I have done with binary search only. You just need to look what to do if OK==false in the solution. https://codeforces.com/contest/1183/submission/56092348

Link is not working :(

Now check it.

you should initialize

loto the least valid value, but you're initializing it wrong. you should rather initialize to : max(a[n — 1] — k, 1) but only after checking if that valueisindeed a valid candidate for an answer. (which is easy you can iterate through the array and check that) my solutionyou should initialize lo to the

leastvalid value, but you're initializing it wrong (0 isn't a valid answer). you should rather initialize to : max(a[n — 1] — k, 1) but only after checking if that value is indeed a valid candidate for an answer. (which is easy you can iterate through the array and check that) my solution1183C - Компьютерная игра Can somebody explain why we need to do (-c+1)/(a-b) instead of (-c)/(a-b)? Thanks

Because you have to add some differences to obtain the charge at least $$$1$$$. See the following example: $$$-c$$$ = 4, $$$diff = 2$$$. Then your formula will say $$$2$$$ and after two additions we will obtain $$$c=0$$$ and this is bad for us.

Thnaks a lot, I did not consider that

Vovuh's contests : Always fast and high quality

In problem H, I wonder if we don't get min of 10^12, what will happen then ?

Theoretically, the number of subsequences of the string of length $$$n$$$ is $$$2^n$$$. This value is the upper bound but there can be strings that contain more than $$$2^{63}-1$$$ subsequences and if you not take the minimum with $$$10^{12}$$$ then your dynamic programming will overflow the 64-bit datatype. I takes $$$10^{12}$$$ because you never need more subsequences than $$$10^{12}$$$.

Thanks

what is the time complexity of solution of problem E ?

$$$O(n^2k)$$$ since it's a BFS that visits $$$k$$$ vertices, and processing each vertex takes $$$O(n^2)$$$ time (generating/checking $$$n$$$ strings, taking $$$O(n)$$$ time each).

(Edited to fix runtime, thanks Roach00.)

but what about unnecesary generated subsequences apart from visiting k vertices and O(n) in deleting character from string for each vertex string

You're right, it's $$$O(n^2 k)$$$ in the worst case where there are lots of duplicates and we only get one new string of each length.

we could reduce the time complexity of search,insertion and deletion to log(n),if we use suitable data structure.but that could be hell of implementation.

wc, Thanks to you too :)

Can anyone explain how to come up with the upper_bound(1e12) for any given string?

it's in the problem. ~~~~ 1<= k <= 10e12 ~~~~

It's great to see these problems which have two versions! It helps me have a deeper understanding of the problem~

what is the mistake in my idea in problem D my code here

Hey just check out this case:

No. of type 1 candy = 5

No. of type 2 candy = 5

No. of type 3 candy = 5

No. of type 4 candy = 5

No. of type 5 candy = 4

ans after soring would be 5,5,5,5,4. and just before you would be adding the last type of candy. State of map s would be : 5:4 4:1 3:1 2:1

& now you should increment at 1 but instead, you increment at (4-2+1) i.e 3.

A better approach would be to store the last number of candies added and then decide what to do in the next loop. If stuck you may check out: https://codeforces.com/contest/1183/submission/56115382

Have a look at this, i have tried to write it in the most simplest manner I could think of :: https://codeforces.com/contest/1183/submission/56165836

thank you all

tnx for fast tutorial and good explanation but lots of questions was mikemirzayanov's

Really liked the trick you applied to F . Nice contest and especially problem F.

Hello, Could you help me with H (hard version)? It says wrong answer on test 43. I have no idea what is wrong with it. Thanks in advance. http://codeforces.com/contest/1183/submission/56165101

Edit: Anyways, I solved it after long hours of hard work.

I solved H with slightly different approach where dp[i][j]=#of subsequences of length j on prefix [1..i]. Let character on position i be A, then the transition looks like: dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[last[A]-1][j-1]. It is correct, however it may overflow sometimes. What I did was first adding dp[i][j]+=dp[i-1][j], and if now dp[i][j]>1e18 i skip the second part of addition. It passed the tests, but im almost sure that this is not correct. If we substract this value of dp somewhere later it is not preceise, so later dp states may be not exactly correct. So here come my questions: 1. Am i right that it is not correct? 2. Is this really hard to construct counter-test?

In problem C, why should we round up (-c+1/(a-b))? Why can't we use the value directly?

Can someone pls explain to me the solution of Problem H

Can anyone explains the 3. Computer tutorial formula for turns i.e. turns = ceil(-c+1/(diff)). How this formula is derived?

Alright. Let the number of

just playturns be $$$x$$$, and let the number ofplay and chargeturns be $$$y$$$.The problem statement suggests that total number of turns should be $$$n$$$, hence $$$x+y=n$$$.

It also suggests that the battery that these moves consume altogether should be

strictly lessthan the initial charge.Just playmoves consume $$$a*x$$$ amount of battery, whereasplay and chargemoves consume $$$b*y$$$ amount of battery, hence $$$a*x+b*y<k$$$.Substituting $$$y$$$ from equation 1, you can obtain an upper bound on $$$x$$$, and hence you'll arrive at the aforementioned equation.

Thanks for your explaination. I got expression as y<(-c)/(a-b) as per your explaination above. But in code why are we taking ceil operation and adding 1 int he numerator. How its giving the correct answer

This comment explains it better.

Can someone please explain why my submission won't work for Candy hard where submission id is https://codeforces.com/contest/1183/submission/56124846?

Can someone please explain the validity of the solution given here for F?

My solution to F is: Sort the array (arr). Remove duplicate elements. Iterate for all i find maximum index j < i such that arr[i]%arr[j]!=0 and then find maximum index k < j such that arr[j]%arr[k]!=0 && arr[i]%arr[k]!=0, maximize the answer by arr[i]+arr[j]+arr[k].

Let prove this solution by contradiction: Suppose, for index i there are indexs j0, k0 (k < j0 < k0 < i) can be selected such that arr[j0]+arr[k0] > arr[j]+arr[k] and i, j0, k0 satisfies all the conditions, if this is possible then our soluton is wrong. But if we look carefully this is not possible. j0 was not selected as k so we are sure arr[j]%arr[j0] = 0, same k0 was not selected as k because arr[j]%arr[k0] == 0, So arr[j0] and arr[k0] are divisors of arr[j] and obviously smaller than arr[j]. And we know than some smaller divisor of a number n is <= n/2 so arr[j0] + arr[k0] <= arr[j]. So above condition arr[j0]+arr[k0] > arr[j]+arr[k] is not possible.

someone explain where my solution fails for Problem C? MY Solution

You are using ints, rather than longs. This overflows when you multiply n and b. I replaced your declarations of variables k, n, a, b with longs and it passes the first case you failed.

thanks,I got it and I should check K<n*b too.

How to solve F by iterating over all possible triplets?

Hey, you can just check out my submission: https://codeforces.com/contest/1183/submission/56166652

All you have to do is break out of the loop whenever appropriate.

Can anyone help me with the problem C why are we adding diff to k (k + diff — 1) / diff

ceil(a/b) = (a+b-1)/b

For C just use the binary search approach simple and efficient.

I looked at your submission. Really clever implementation.

Thanks:)

can someone explain the 2nd testcase of

problem Di didnt quite understand how they took the maximum possible size thanks.Vovuh

I tried D using max-heap but at the 19th case the response was TLE .. but as you guys have used sort() method [complexity will be nlogn]. So, as Mine...

https://codeforces.com/contest/1183/submission/56128383

any suggestion where am I wrong???

For 1183F - Возвращение Topforces, I tried all of the possible options for 30 biggest unique elements and failed in system testing (56093272). After the contest, I changed 30 to 40 and got accepted (56189352). Can anybody come with a counter test for my solution? The main idea is if $$$x \neq y \land x | y \rightarrow x \times 2 \leq y$$$.

This solution will fail at the test case where a lot of divisors of maximum should be omitted in greedy solution. So we can take a number $$$x$$$ with maximum number of divisors, omit one from $$$\{x/2, x/3, x/5\}$$$ and add two minimum numbers that are not divisors of $$$x$$$. This gives us a test with $$$n = 149$$$, where the least number is used in optimal answer.

TestGeneratorProbably this or something similar should be added to this problem testset, Vovuh

Thank you, I will add this test now!

Can someone explain me the Problem D ?

In this problem, you are provided with total different types of candies (n)

and then the type of a particular candy in a series

for eg- 8 1 4 8 4 5 6 3 8

8 is the total number of different types of candies

and the sequence in which they are present is

firstly a candy of type 1 then a candy of type 4 then a candy of type 8 again a candy of type 4

total number of candy of type 1 is = 1 total number of candy of type 2 is = 0 total number of candy of type 3 is = 1 total number of candy of type 1 is = 1 total number of candy of type 4 is = 2 total number of candy of type 5 is = 1 and soon

You have to find out the gift

Have a look at this, https://codeforces.com/contest/1183/submission/56165836 In this we try to first see the frequencies of all candies, and sort then in descending order. We all candies with highest frequency(say f for now) to our gift and the next optimal step would be to add f-1 candies of the next candy type(if available, else add all candies if its freq is less than f-1). We always try to add the number next candy type, based on how many candies of the previous type we added. Optimally we always try to add (prev_added_candies — 1) candies if available, int current step.

can anyone please explain tutorial for H. I don't understand how does it work.

I too am unable to understand the very first few lines.

"Initially all values are zeros except $$$dp_{i,1}=1$$$ for each $$$i$$$ from $$$0$$$ to $$$n−1$$$."

Why is this the case? Won't it count two different occurrences of the same character as two instead of one ( we need distinct subsequences right? )

UPD: (Adding example)

If the given string is "abca", then $$$dp[0][0]=1$$$ and $$$dp[3][0]=1$$$, but I thought we must count it as 1 times "a" is there not twice. How is that being taken care of?

You will not consider the first 'a' when you'll calculate the number of subsequences of length one. The same with other lengths, two dynamic programming states $$$dp_{i_1, j}$$$ and $$$dp_{i_2, j}$$$ can be non-zero and $$$s_{i_1} = s_{i_2}$$$ but you will not consider the first state in the answer.

Oh okay. So correct me if I am wrong, we are making dp such that each subsequence $$$t$$$ that ends with say some character $$$X$$$, will be counted at the maximum position $$$i$$$ such that $$$i \ge len(t)$$$ and $$$s[i]$$$ is $$$X$$$. ( $$$s$$$ is original string ).

Yes, this is true.

Thanks a lot! Finally understood and implemented.

Hey, can u please explain the solution in a detailed manner, I am not able to understand why are we doing the steps mentioned. Thanks in advance!

Maybe you should try to explain what exactly you did not understand, instead of asking someone to tell you the whole thing, especially when there is editorial where someone has tried to do what you exactly want.

Now, I will try to explain a simple example to you, to make sense of the dp ( not go through the whole process ). Maybe that will clear everything.

Consider given string $$$s = aba$$$. I will just tell you how to understand the $$$dp$$$.

Firstly, let's note ourselves, what are the subsequences. We have

{$$$aba,ba,aa,ab,a,b$$$}

Out of these,

Since $$$a$$$ is counted twice, I was confused, but finally while calculating total counts, we are only considering $$$last[n-1][ch]$$$ for each character $$$ch$$$ = [ $$$a$$$ to $$$z$$$ ], thus in case of $$$a$$$ only the one at index $$$2$$$ is counted at the end. The one at index $$$0$$$, however, is also important, because only using it you can count the strings $$$aba$$$ or $$$aa$$$.

Thanks Samarth!

## Problem B : Equalize Prices

i have just checked if (min+k >= max-k) then print min+k ; else print -1; still wrong answer on test case 3.Can somebody please explain.

Solution : https://codeforces.com/contest/1183/submission/56229913

What if $$$n=1$$$? You forgot to set the maximum value in your if statement (in

`if (i == 0)`

).think of it as an intersection problem that's how i solved it find the intersection segment l,r for all the given elements and print r if for some element there's no intersection with previous element output -1 https://codeforces.com/contest/1183/submission/56232830

thanks for all your help ....., now deleting this comment

teshar roy on youtue for videos hacker earth for graphs and math and all the basics expect for dynamic programming learn it from geeks for geeks any one who did it did it alone so cheer up and go solve a lot of problems and participate in lots of contests that'a the most important thing hope to do well enjoy .

Simple solution for H:

Let $$$dp[n][k]$$$ be the number of distinct subsequences of length $$$k$$$ using only the first $$$n$$$ characters of $$$s$$$. Then

where $$$l = lst_{n-1,s[n]}$$$.

Now greedily add substrings to $$$S$$$. Note that two subsequences of different length must be different. (We first use the $$$dp[n][n]$$$ subsequences, then $$$dp[n][n-1]$$$, etc)

Can someone explain the Dynamic Programming approach for Problem E — Subsequences (easy version).

I solved problem D with O(N) solution. I like when you guys hide the solution of the problems in the way you did in this tutorial. So when i go to read the solution of the problem A i don't end up reading the solution of problem B and a lot of times i don't want to do it.

56141485 Can someone please tell what am I doing wrong. When I run the code on my system with the test case : 1 10 100 100 100 100 100 100 100 100 100 100

I get the answer as 10, but on running in custom invocation answer comes out as 27.

Vovuh Why do n/2, n/3, n/5 never divide each other completely? Can this be proved? Thanks :)

cause n / 2 has more 3 factors than n / 2 and n / 3 has more 2 factors than n / 2. :)

In problem F editorial

`Let's imagine that the maximum element is divisible by 2, 3 and 5 and there are three following numbers in the array: maximum divided by 2, by 3 and by 5. Then their sum is greater than the maximum (and may be greater than the answer we have!) because 12+13+15>1.`

can someone give an example of such case... Thanks in advanceConsider one of test cases in problem sample:

Obviously, $$$n < n/2 + n/3 + n/5$$$ is $$$30 < 15 + 10 + 6$$$ here

Can anybody explain the complexity for Problem F (brute force) solution ,it would be really helpful?

For problem F,https://codeforces.com/contest/1183/submission/56308081

My submission is just a N^2 complexity solution, why can I get it passed?

For Problem D, Candy Box(easy version) can someone help me identify the error in my code?

https://codeforces.com/contest/1183/submission/56358474

Thank you!

1183(c) Can anyone tell me why its not working??

## include<stdio.h>

int main() { long n,k,a,b,q,c,turns,diff; scanf("%ld",&q); while(q--) { scanf("%ld%ld%ld%ld",&k,&n,&a,&b); c=k-(a*n); diff=a-b; if(c>0) printf("%ld\n",n); else { turns=(-c+1)/diff; if(turns>n) printf("-1\n"); else printf("%ld\n",n-turns); } } }

pls explain why in C

In the problem C, i am not able to get where in the problem statement its written that when vola plays the turn "play and charge", the charge of the battery increases by diff=a-b. It's written in the editorial as well. Kindly help me with the problem statement of the problem. Thanks in advance

Could anyone tell me why am I getting a wrong answer with problem D on the 3rd test?

https://codeforces.com/contest/1183/submission/56678366

Could anybody explain me please, why I have TLE on test 3 in problem F ? https://codeforces.com/contest/1183/submission/56682439 I have no ideas :( I use C#.

For all those who can't understand solution for

Hcan try this problem first https://www.spoj.com/problems/DSUBSEQ/What is the time complexity for solution of E?? .... they used set count which is O(n) (even more with strings)...but using map is slower than this !!

Can someone explain why Problem H solution works ? I don't understand why we are constructing these matrices and what is the logic to using them.

For Question A. Max step should be 7. Number = 997 steps taken will be 7 But the editorial says it's 5.

Thanks for these Good Editorial !