1183A - Ближайшее интересное число
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: MikeMirzayanov and vovuh and BledDest
Разбор
Tutorial is loading...
Решение
#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 - Коробка с конфетами (легкая версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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 - Подпоследовательности (легкая версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#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 - Коробка с конфетами (усложненная версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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 - Подпоследовательности (усложненная версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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?
We can do binary search over the final price and then check whether it differs not more than k from the minimum and the maximum original price.
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
you should initialize lo to 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 value is indeed a valid candidate for an answer. (which is easy you can iterate through the array and check that) my solution
you should initialize lo to the least valid 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 solution
1183C - Computer Game 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.
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.
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
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?
natofp did you find what was wrong? I also spammed min(1e12, dp(i, j)) everywhere and idk why it's passing. It should be failing as later states might suffer.
"к разбору H". Я забывал брать минимум с 10^12.У меня AC
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 play turns be $$$x$$$, and let the number of play and charge turns 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 less than the initial charge. Just play moves consume $$$a*x$$$ amount of battery, whereas play and charge moves 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.
Thanks, for the explanation. I was wondering what is the time complexity of this solution. I saw your submission, its execution time is 78ms, but from the approach above it should be O(n^2). Can you please explain what I am missing and how does the overall complexity is less than n^2.
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.
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
For 1183F - Topforces Strikes Back, 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.
Probably 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
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$$$.
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)).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)
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.
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 all those who can't understand solution for H can 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 !!
For Question A. Max step should be 7. Number = 997 steps taken will be 7 But the editorial says it's 5.
After rigorously proving problem G, I found it very cool. Thanks Mike!
You can also solve G with a priority_queue of pairs 80920737. In this case the default of priority_queue returning the max element is what you want unlike when you're implementing Dijkstra.