Спасибо K1o0n за то, что он был mvp при подготовке раунда.
Идея: Vladosiya
Подготовка: K1o0n
Докажем, почему всегда лучше прибавлять к наименьшему числу. Пусть $$$a \le b \le c$$$, тогда сравним три выражения: $$$(a+1)\times b \times c$$$, $$$a \times (b+1) \times c$$$ и $$$a \times b \times (c+1)$$$. Уберем общую часть $$$a \times b \times c$$$, и получаем: $$$b \times c$$$, $$$a \times c$$$, $$$a \times b$$$.
$$$b \times c \ge a \times c$$$, так как $$$a \le b$$$, аналогично, $$$b \times c \ge a \times b$$$, так как $$$a \le c$$$. Поэтому можно просто $$$5$$$ раз найти минимум и прибавить к нему единицу. И таким образом получить ответ.
Иной, примитивный подход просто перебрать то, что мы будем прибавлять к $$$a$$$, $$$b$$$ и $$$c$$$ тремя циклами.
Так как прибавить можно всего $$$5$$$ раз, то асимптотика решения $$$O(1)$$$.
for _ in range(int(input())):
arr = sorted(list(map(int,input().split())))
for i in range(5):
arr[0]+=1
arr.sort()
print(arr[0] * arr[1] * arr[2])
Идея: Noobish_Monk
Подготовка: K1o0n
Пусть мы хотим соединить две запеканки с длинами $$$x$$$ и $$$y$$$. Мы можем разобрать одну из них на куски длины $$$1$$$ и затем присоединять их к запеканке размера $$$y$$$. Суммарно мы сделаем $$$2x - 1$$$ операций. Так как мы хотим соединить $$$k$$$ кусков, хотя бы $$$k - 1$$$ из них нам придётся разобрать, а затем присоединить к чему-то. Если мы к какому-то куску присоединяем что-то, его уже нет смысла разбирать, так как чтобы его разобрать, нам нужно будет в том числе убрать эти куски. Поэтому мы хотим выбрать какой-то кусок, к которому мы будем соединять все остальные. Оптимальным будет выбрать кусок с максимальным размером и к нему всё соединять. Таким образом, ответ получается $$$2 \cdot (n - mx) - k + 1$$$, где $$$mx$$$ $$$-$$$ длина максимального куска.
Асимптотика решения: $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
signed main() {
int T;
cin >> T;
while (T--){
int n, k;
cin >> n >> k;
vector<int> s(k);
int m = -1;
for (int i = 0; i < k; i++){
cin >> s[i];
m = max(m, s[i]);
}
cout << 2 * (n - m) - k + 1 << '\n';
}
}
for _ in range(int(input())):
n,k = map(int,input().split())
mx = max(map(int, input().split()))
print((n - mx) * 2 - (k - 1))
1992C - Горилла и перестановка
Идея: K1o0n
Подготовка: K1o0n
Пусть $$$p$$$ $$$-$$$ некоторая перестановка. Посмотрим на вклад числа $$$p_i$$$ в сумму $$$\sum_{i=1}^n {f(i)}$$$. Если оно меньше $$$k$$$, вклад равен $$$0$$$, иначе вклад равен $$$p_i \cdot (n - i + 1)$$$. Аналогично посмотрим на вклад $$$p_i$$$ в сумму $$$\sum_{i=1}^n {g(i)}$$$. Если оно больше $$$m$$$, вклад равен $$$0$$$, иначе $$$-$$$ $$$p_i \cdot (n - i + 1)$$$. Так как $$$m < k$$$, каждое число даёт вклад, больший $$$0$$$, не более чем в одну сумму. Поэтому выгодно поставить числа, не меньшие $$$k$$$, в начало, а числа, не большие $$$m$$$, в конец. Также числа, не меньшие $$$k$$$, должны идти в порядке убывания, чтобы максимизировать сумму $$$f(i)$$$. Аналогично числа, не большие $$$m$$$, должны идти в порядке возрастания, чтобы минимизировать сумму $$$g(i)$$$.
Например можно построить такую перестановку: $$$n, n - 1, \ldots, k, m + 1, m + 2, \ldots, k - 1, 1, 2, \ldots, m$$$. Легко видеть, что $$$\sum_{i=1}^n f(i)$$$ не может быть больше ни для какой другой перестановки, а $$$\sum_{i=1}^n g(i)$$$ не может быть меньше ни для какой другой перестановки, поэтому наш ответ оптимален.
Асимптотика решения: $$$O(n)$$$.
for _ in range(int(input()):
n,m,k = map(int,input().split())
print(*range(n,m,-1), *range(1,m+1))
Идея: ArSarapkin
Подготовка: K1o0n
В этой задаче есть два основных решения: динамическое программирование и жадный алгоритм.
Решение с динамикой: $$$dp_i$$$ $$$-$$$ минимальное количество метров, которое надо проплыть в воде, чтобы добраться до $$$i$$$-й клетки. База динамики: $$$dp_0 = 0$$$. Тогда пересчет происходит так: \begin{equation*} dp_i = \text{минимум из} \begin{cases} dp_{i-1} + 1& \text{если } A_i = \text{'W'} \\ min(dp_j) & \text{по всем } j, \text{таким что:} \max(0, i — m) \le j < i \text{ и } A_j = \text{'L'} \end{cases} \end{equation*} Асимптотика решения: $$$O(nm)$$$.
Решение с жадным алгоритмом: Если мы можем прыгать, мы хотим прыгать на берег, если можем. Если не можем, мы хотим прыгать на любое бревно впереди, чтобы потом прыгать с него. Если не можем, прыгаем максимально далеко, чтобы избежать крокодилов и плыть как можно меньше.
Асимптотика решения: $$$O(n)$$$.
def run() -> None:
n,m,k = map(int, input().split())
A = input()
logs = [i for i in range(n) if A[i] == "L"]
logs.append(n+1)
i = -1
next_log = 0
while i < n-1:
if m >= logs[next_log] - i:
i = logs[next_log]
else:
i+=m
if i > n-1:
print("YES")
return
while i < n and i < logs[next_log]:
if A[i] != "C" and k > 0:
i+=1
k-=1
else:
print("NO")
return
next_log +=1
print("YES")
for _ in range(int(input())):
run()
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> dp(n + 2, -1);
dp[0] = k;
for (int i = 1; i <= n + 1; i++) {
if (i != n + 1 && s[i - 1] == 'C')
continue;
for (int t = 1; t <= m; t++)
if (i - t >= 0 && (i - t == 0 || s[i - t - 1] == 'L'))
dp[i] = max(dp[i], dp[i - t]);
if (i > 1 && s[i - 2] == 'W')
dp[i] = max(dp[i], dp[i - 1] - 1);
}
if (dp[n + 1] >= 0)
cout << "YES\n";
else
cout << "NO\n";
}
}
Идея: Noobish_Monk, K1o0n
Подготовка: K1o0n
Заметим, что $$$n * a - b$$$ строго меньше $$$10^6$$$, то есть имеет не больше $$$6$$$ цифр. Число символов в странном подсчёте $$$n * a - b$$$ равно $$$|n| * a - b$$$, где $$$|n|$$$ $$$-$$$ количество цифр в n. Давайте будем перебирать значение $$$a$$$, а дальше определим для него границы $$$minB$$$ и $$$maxB$$$ так, что $$$|n| * a > maxB$$$ и $$$|n| * a - minB \le 6$$$. Тогда: \begin{cases} minB = |n| * a- 6 \\ maxB = |n| * a- 1 \end{cases} Переберём все $$$b$$$ от $$$minB$$$ до $$$maxB$$$. Чтобы быстро проверять странный подсчёт, давайте будем находить только его первые $$$|n| * a - b$$$ цифр. Таким образом мы можем быстро найти все подходящие пары $$$(a, b)$$$. Асимптотика решения: $$$O(a)$$$.
for _ in range(int(input())):
n = int(input())
sn = str(n)
lenN = len(str(n))
ans = []
for a in range(1, 10001):
minB = max(1, lenN * a - 5)
maxB = lenN * a
for b in range(minB, maxB):
x = n * a - b
y = 0
for i in range(lenN * a - b):
y = y * 10 + int(sn[i % lenN])
if x == y:
ans.append((a, b))
print(len(ans))
for p in ans:
print(*p)
Идея: Noobish_Monk
Подготовка: Noobish_Monk
Рассмотрим жадный алгоритм "берём пока набирается". Докажем, что он работает. В любом оптимальном разбиении, если мы взяли первый отрезок не максимальной длины, мы не нарушим критерий, если от второго отрезка перекинем один элемент в первый. Следовательно приведенный жадный алгоритм корректный.
Теперь разберёмся, как быстро понимать, можем ли мы удлинить отрезок. Во-первых, найдём все делители числа $$$x$$$. Если число $$$a_i$$$ не является его делителем, то оно не может входить ни в одно множество чисел, произведение которых равно $$$x$$$, поэтому мы можем просто добавить его в отрезок. Если же $$$a_i$$$ является делителем, нам надо как-то научиться понимать, даёт ли оно в произведении с какими-то другими делителями на отрезке число $$$x$$$. Будем поддерживать множество делителей, которые являются произведениями каких-то чисел на отрезке. Чтобы обновить множество при добавлении $$$a_i$$$, пройдёмся по всем делителям этого множества и для каждого делителя $$$d$$$ добавим $$$d \cdot a_i$$$ в множество. Если же мы добавили число $$$x$$$ в множество, $$$a_i$$$ будет лежать уже в следующем отрезке и нам надо очистить множество.
P. S.: О деталях реализации и времени работы. Если поддерживать множество в структуре set, то мы получаем время работы $$$O(n \cdot d(x) \cdot \log(d(x)))$$$, где $$$d(x)$$$ $$$-$$$ число делителей $$$x$$$. Вместо множества можно сделать, например, глобальный массив $$$used$$$ размера $$$10^5 + 1$$$, а также поддерживать вектор достижимых делителей. Используя эти структуры можно получить время работы $$$O(n \cdot d(x))$$$.
#include <iostream>
#include <vector>
using namespace std;
const int A = 1e6 + 1;
bool used[A];
bool divs[A];
void solve() {
int n, x;
cin >> n >> x;
vector<int> a(n);
vector<int> vecDivs;
for (int d = 1; d * d <= x; d++) {
if (x % d == 0) {
divs[d] = true;
vecDivs.push_back(d);
if (d * d < x) {
vecDivs.push_back(x / d);
divs[x / d] = true;
}
}
}
for (int i = 0; i < n; i++)
cin >> a[i];
int ans = 1;
used[1] = true;
vector<int> cur{ 1 };
for (int i = 0; i < n; i++) {
if (!divs[a[i]])
continue;
vector<int> ncur;
bool ok = true;
for (int d : cur)
if (1ll * d * a[i] <= x && divs[d * a[i]] && !used[d * a[i]]) {
ncur.push_back(d * a[i]);
used[d * a[i]] = true;
if (d * a[i] == x)
ok = false;
}
for (int d : ncur)
cur.push_back(d);
if (!ok) {
ans++;
for (int d : cur)
used[d] = false;
used[1] = true;
used[a[i]] = true;
cur = vector<int>{ 1, a[i] };
}
}
for (int d : vecDivs) {
divs[d] = false;
used[d] = false;
}
cout << ans << '\n';
}
signed main() {
int T;
cin >> T;
while (T--)
solve();
return 0;
}
Идея: Noobish_Monk, K1o0n
Подготовка: K1o0n
Будем перебирать размер множества $$$k$$$ и его $$$\text{MEOW}$$$, $$$m$$$. Если $$$2k \geqslant n$$$, то множество $$$x$$$ заполнит все оставшиеся числа до $$$n$$$ и возможно в нём останется ещё какие-то большие $$$n$$$, поэтому $$$MEOW$$$ от всех таких множеств будет $$$2k+1$$$, а всего таких множеств для каждого $$$k$$$ будет $$$C(n, k)$$$. Если же $$$2k < n$$$, $$$m$$$ лежит в интервале от $$$k+1$$$ до $$$2k+1$$$. Заметим, что чисел до $$$m$$$ может быть ровно $$$m - 1 - k$$$, а чисел справа от $$$m$$$ соответственно $$$2k + 1 - m$$$, а значит к ответу надо прибавить $$$C_{m - 1}^{m - 1 - k} \cdot C_{n - m}^{2k + 1 - m} \cdot m$$$.
Асимптотика решения: $$$O(n^2)$$$.
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int add(int a, int b) {
if (a + b >= mod)
return a + b - mod;
return a + b;
}
int sub(int a, int b) {
if (a < b)
return a + mod - b;
return a - b;
}
int mul(int a, int b) {
return (int)((1ll * a * b) % mod);
}
int binpow(int a, int pw) {
int b = 1;
while (pw) {
if (pw & 1)
b = mul(b, a);
a = mul(a, a);
pw >>= 1;
}
return b;
}
int inv(int a) {
return binpow(a, mod - 2);
}
const int N = 15000;
int f[N], r[N];
void precalc() {
f[0] = 1;
for (int i = 1; i < N; i++)
f[i] = mul(f[i - 1], i);
r[N - 1] = inv(f[N - 1]);
for (int i = N - 2; i > -1; i--)
r[i] = mul(r[i + 1], i + 1);
}
int C(int n, int k) {
if (n < 0 || k < 0 || n < k)
return 0;
return mul(f[n], mul(r[k], r[n - k]));
}
inline void solve() {
int n;
cin >> n;
int ans = 1;
for (int k = 1; k <= n; k++) {
if (2 * k >= n) {
ans = add(ans, mul(2 * k + 1, C(n, k)));
continue;
}
for (int m = k + 1; m <= 2 * k + 1; m++) {
int c = mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m));
ans = add(ans, mul(mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m)), m));
}
}
cout << ans << '\n';
}
signed main() {
int T = 1;
cin >> T;
precalc();
while(T--)
solve();
return 0;
}
Автокомментарий: текст был обновлен пользователем Noobish_Monk (предыдущая версия, новая версия, сравнить).
Thanks for the fast text editorial!
Thanks for the fast text editorial! :D
Thanks for editorial
tks for the tutorial :D
tysm!!!! :D
E WAS BETTER THAN D
Could you also solve problem D by using game theory logic and designing an array that will mark spots that are winning and others that are losing, so an array w[d+1] for which w[d] is winning, for every i that path[i]=='C' w[i]=losing ... I tried to solve it during the contest with this approach, but failed on implementation so I want to know if the approach is valid to polish the implementation or to try a different approach.
just simulate the game + greedy :)
ok tnx
Sounds like what I did but since I'm noob so test 2 failed, unfortunately
Seems like you are looking for a dp solution, one of which is described in the tutorial. However it turns out you need to keep more information than a binary value in that array because of the swimming constraint
Yes, but in an implementation with a vector<tuple<....>> I could keep winning state, if 1 a char('c',...), and swimming or jumping constraint, which I could update correctly so the game conditions are satisfied.
I think my submission can help you understand the implementation details. I keep in each index a $$$pair$$$ indicating whether we can reach that cell or not, and $$$min$$$ water cells swam till now.
Transitions are the same as editorial
i just simulate his optimal moves (greedy). i am him.
Ah yes I see what he meant now.
small advice: try to adjust your indentation to $$$4$$$ spaces instead of $$$8$$$ as it's more readable, and name your variables for easier idea understanding (It took me much to understand your code) and also to help you in debugging matters
noted!
Thank you :)
I did it with graphs XD
:)
Notice that n∗a−b is strictly less than 10^6 , i.e., it has no more than 5 digits.
Please edit that to 6 digits. Thanks!
that (the editorial) is correct. strictly less than 10^6 means <= 99999 -> max 5 digits :)
Oh sorry, my bad :')
Niko-Bellic is right.
I actually started questioning myself for a moment xD
u trippin
oh shoot :))) so sorry. ahhh
aap toh badmaash hain ji
A simpler implementation for F
Could you please explain your solution?
let $$$x$$$ be the number that will make our current segment good, means that if there is numbers in our segment such that $$$a_i \cdot a_j \cdot \cdot \cdot a_l = x $$$, the segment will be counted as good, however the problem wants only bad segments so we need to make sure that we can't have $$$x$$$
notice that in order to have $$$x$$$ all of $$$a_i \cdot a_j \cdot \cdot \cdot a_l $$$ need to be divisors of $$$x$$$
let $$$s$$$ be a set that contains any number that will make our segment good so initially it will be $$$s =$$$ { $$$x$$$ }
now we iterate over the numbers, and check if this number is in $$$s$$$, if it's in $$$s$$$ then this number will make our segment good if we contain it with our current segment, we don't want that as we only want bad segments, so we need start a new segment and increase our $$$ans$$$ by $$$1$$$ and reset $$$s$$$
if the number is not in $$$s$$$, we need to work with it because lets say or $$$s = $$$ { $$$4$$$ , $$$8$$$ }, and we find $$$a_i = $$$ $$$2$$$ , that means we need $$$4$$$ or $$$8$$$ but we got $$$2$$$, what if we got another $$$2$$$ after some time ?
that would be $$$2$$$ $$$\cdot$$$ $$$2 = $$$ $$$4$$$ which is a number that we are looking for, so we need to iterate over $$$s$$$ and check if ($$$s_i \mod a_i == 0$$$ ) then we add $$$s_i \div a_i$$$ to $$$s$$$
so $$$s$$$ will be $$$s =$$$ { $$$2$$$ , $$$4$$$ , $$$8$$$ } and then when we get to the second $$$2$$$ we will check if its in $$$s$$$ and so on ...
the lower bound is to fast things up as we may not need to iterate over all $$$s$$$ but to start from a number thats $$$ a_i \le s_i$$$
if its still not clear please copy my code and try to work with it and test it with samples
Understood perfectly, Thanks for your nice explanation.
How? i've been trying to understand how this approach doesn't exceed the time limits for hours. isn't its complexity O(n x number of divisors of x)? In that case doesn't it exceed 10^7 as no. of divisors of x can go uptil 100 and n can go up till 10^5?
As I know, $$$10^7$$$ fits within even 1s
Is it possible for ~9k+ people to solve D in DIV 3 ?
people are more genius than we think
or maybe im more dumb ? :(
Yes, it was much easier than normal Div. 3 D.
yes
All thanks to telegram
F solution should contain 17 lines of code.
I agree. F seems easier than E, although I couldn't reach either of them during the contest. Afterwards, it took me about 10min to figure out a solution for F, while E required a fair amount of mathematical reasoning.
The hardest part of F was understanding the problem statement. xD
A simpler solution to F: 270026683 with a time complexity $$$O(n d(x) log(d(x)))$$$
The set
avoid
stores values that should not occur in the current segment. For example, let x = 12, a = [2, 3, 2, ...]. Initially the set contains 12. When encountering 2, we put 6 into set, because 6*2=12; encountering 3, we put 4 and 2 into set, because 4*3=12 and 2*3*2=12. After that when encountering another 2, we find that it is already in set, so we need to split here, and reset the set with {12, 6}.My solution complexity is just $$$O(n d(x))$$$
Sorry for misreading the tutorial. Then it's a shorter but less efficient solution lol (but I think mine can also be optimized with the same trick or by using unordered_set
oh yeahhhhhhhhh. i should've think simpler
E can be solved in constant time just iterating over the number of digits of n*a-b 270038095
Your solution is mind-blowing to me. Great Job! Can you give some idea behind the proof, that, no other solutions would exist besides these for the cases?
If you have the number of digits of n*a-b, then you can have the difference between a and b, then you can replace b in function of a, and calculate a from n*a-b.
This is my First Contest.. And I'm able to solve only A, and try B after the contest and i solved B.Is I'm the Only one who solve A with recursion?
Many people are not able to solve a single question in your first contest. You did well for your first. Also, recursion is not needed in the first one. So you might be the only one:)
Pretests were too weak. My solution of F got an FST with TL but passed pretests with time of 200ms, and in B there wasn't a pretest with big enough a
what are the conditions to get MLE like if we make a vector of 10^10 or if we make a 2-3 vectors of 10^5 like which type of dps can we make what is make value of n for an 2DP and 3DP if anyone can tell or refer me to a post telling these
umm, can you restate? hard to read.
He's asking how much memory you can allocate before MLE. A vector of size 10e10 would definitely MLE, 2-3 vectors of 10^5 would be fine, 2DP would be around max 5000, and 3DP would be around max 500.
oh why so less for a 2dp but its way to less
I don't understand what you're saying.
I solved D using 0-1 BFS. Each cell can go to no more than 10 cells next to it ( except if it contains a crocodile). So if the next cell is water the cost is 1 otherwise the cost is 0. Then after calculating the shortest path from cell 0 , the answer is YES if the cost is less than or equal k and NO otherwise.
Here is my submission:
https://codeforces.net/contest/1992/submission/269951020
a bit overkill tbh...
oops i had G left with 30 minutes to spare but was too lazy to read it im math main so coudlve (maybe?) reached pupil :(
I WANT JUSTICE.
My contest submission : 269977715
Same code submission: 270045857
My submission getting runtime error but other submission accepted, this whole thing ruined my contest rating.
Please do something about this.
Same Code submission: 270185546
Accepted Again.
Please rejudge my contest solution, and change my standings in leaderboard.
PLEASE AUTHORS.
I wouldn't tunnelvision on rating. You can see here https://leetcode.com/u/echen5503/ that I had a contest with negative delta(submitted solution 2 min after contest end), then the next contest where I did well was unrated. If you are skilled enough to do it once, you can probably do it again in a later contest. GL on expert.
In problem C, numbers between $$$m$$$ and $$$k$$$ affect neither $$$f$$$ nor $$$g$$$, so their permutation is irrelevant. In fact, you don't even need $$$k$$$ to solve the problem: just iterate from $$$n$$$ down to $$$m+1$$$, then from $$$1$$$ to $$$m$$$.
In fact, test case 3 of problem C has bad input format (maybe extra spaces in somewhere), which causes my submission 269935508 got a wrong WA in fst. If reading tokens one by one, it (270282247) gots a AC.
Even little probability, if Noobish_Monk, K1o0n can take a look and rejudge, I will give much appreciate for that.
I looked in my generator, in fact there are no extra spaces, but there is a newline character in the end of file as it is in all the problems if it matters to you. Sadly I/we can't rejudge your submission. Sorry. Fun fact, I submitted your solution myself with no changes , it got OK. xD. I guess you're just unlucky...
Thanks for your reply. It's the most sad story during my cf life. 2 problems got fst. C is mysterious wrong verdict, and F is tle due to Node.js.
Can anyone please help me correct this solution to problem D
Got WA on 845th test of test case 2.
9 5 1
LWLLCWCCW
answer is "YES". Your code gives "NO".
I think It's because you're changing k in the dp state but not storing in the dp array.
it is not enough to set dp[i] = true/false .
it should be the minimum distance he can swim to reach n+1 from i
Can Someone explain me why this submission of mine (For problem F) does not give a TLE , i mean while implementing i was considering some sort of a test case which could break this algo , maybe the set runs out of overflow , or traversing the set takes too long , or something like that Here is the Link to the submission. Link
good contest , thanks for fast editorial !
the problem D was bit different !
here is my solution to the problem ( greedy , c++ ) — 269977837
prblm D with iterative DP:`` Your text to link here...
My alternate approach for E:
Let $$$ans = n\cdot a-b$$$ for some pair of integers $$$(a, b)$$$. We know the number of digits in $$$ans$$$ is equal to $$$|ans| = |n|\cdot a-b$$$ and for all $$$n > 1$$$, $$$n > |n|$$$ (here again $$$|n|$$$ is the number of digits in n). Now, $$$ans$$$ can be reformulated as:
$$$ans = (n-|n|)\cdot a + |n|\cdot a-b$$$
Simplifying this we get;
$$$a = \frac{ans - |ans|}{n - |n|}$$$
$$$b$$$ can be computed in $$$O(1)$$$ once we calculate $$$a$$$. So traversing over all possible $$$ans$$$ gives the answer in practically $$$O(1)$$$ (not sure about the complexity).
My implementation
The complexity is actually $$$O(log^2(n*a - b))$$$ for $$$a\neq 1$$$. I also did the same thing.
I got the $$$O(\log n)$$$ part in my calculations, which I decided to report as practically $$$O(1)$$$ because of the bounds on $$$n$$$ in the task. How did you get the $$$O(\log a)$$$ part though?
I just looped through all possible values of $$$n*a-b$$$ which take $$$O(log(n*a-b))$$$ time. Then, the process of computing the number of digits also take that time. (can be optimized a bit though)
My solution for problem F is very similar to the tutorial logic but still I'm getting TLE. Can anyone point out the reason. 270213270
Sure. Your "possible" vector should be turned into a set because you are processing the same factors over and over again.
https://codeforces.net/contest/1992/submission/270260270
Got it, thanks. Initially I also used a map which got accepted but following the tutorial I tried optimizing my solution but missed this edge case. 270268923
Oh nice. This one is n*d(n) instead of nd(n)log(d(n))
Could someone please explain that how 270218105 gets accepted but 270217104 got TLE ?
I figured out the problem in the TLE submission. I had assumed that the products of 2 divisors of x such that the product < x will still be a divisor of x. This is clearly wrong (consider x to be 24, the divisors to be 2 and 8, 16<24 but 16 is not a divisor of 24). Thus, my curr vector contains unnecessary numbers increasing its size outside of the permissible bound.
You saved me! I had worked for many hours to find where mine went wrong.
anyone please explain r array here in G solution
It's for reverse factorials. They are calculated this way:
$$$r_n = inv(f_n)$$$
$$$r_i = r_{i+1} \cdot (i+1)$$$
Can't we take f[n]*(inv(f[r]*f[n-r]))
Yeah but that's $$$O(log MOD)$$$ for every binomial coefficient, which results in longer runtime
Ohk thanks.
I'm not getting it how the greedy is working in problem D?? As if everytime we get the log and try to jump as further as possible then in O(N) how can we be sure that we will not get any crocodile in such jump?? And if we do get the crocodile or we get the water but we have spent all the k's then how we'll make the informed decision about that in just O(N) time ??
The thing is, with a jump you can get past any crocodile, as long as you land in either a log or water. If there is such a log, then it is best to land at the farthest possible one; otherwise, if there is water at the end of the jump, then it is best to land there, so long as there is available $$$k$$$ at that moment.
Thank you for your suggestion but it's still confusing to me. I found another approach using BFS which is also in order of O(N) which is less than DP.
A better way to look at this is, let's say you have many logs that you can jump on:
lets call last log as F If you choose any log but the last one, then any of these logs will eventually, after some jumps, have to surpass that last log (F). They can't surpass it by more than (m-1) steps. So picking the final log from the start would have granted you these (m-1) steps plus an extra one.
if we have two logs that you can jump on one at index 1 and the other at index 8 it's always better to jump at index 8 lets say m is equal to 8 now when you jump at 1 you have 2 3 4 5 6 7 8 and 9 as options to jump on
but if you jump at 8 you still have the 9 and you have now more options 10,11 ...
there is no point in picking the earlier log because picking the farthest will give you more options and It will not make you miss anything
could anyone plz help me with my soln 270036296 of problem D . i don't know why i am getting wrong output.
In tutorial for F they said
What does this even mean?
It's short for "proof by induction". If we have some split in segments, where the length of the first one isn't maximal, we can move one element from the second and it would still be a correct split, while the number of segments could've only gotten less. Doing this process with every segment is the proof for greedy
The editorial for A doesn't prove that incrementing the smallest number is optimal when we repeat the process 5 times. It only proves that it's optimal for 1 time.
Yes, I agree that at the end they should have written: "Let's run this algorithm 5 times and get the answer to the problem.". But they did everything else, because at the beginning they announced that a<=b<=c, which means that the variables must be sorted initially, which means if you just do this algorithm 5 times everything will work.
If my understanding is correct, that's not what he is saying. I think his point is that just because you take the locally optimal choice every time doesn't necessarily mean that you will get the globally optimal result. For this problem, it is true. That's not the case for every problem.
There are only 4 stages of this algorithm which are:
Where a is lowest number and c is largest of these 3. Let's look at all the options for starting:
This only works if the variables are in the range from 1<=a,b,c<INF.And accordingly, it works in THIS task.
Prove me that im wrong instead of downvoting. I really dont care about it.
Imma be honest. I have no idea what you are talking about.
I came up with some proof but it doesn't sound very easy for D3A. Please tell me if you know a simpler proof. On the positive side, the following proof works for any number of operations and more than three numbers.
Consider two sequences $$$p$$$ and $$$q$$$ where $$$p$$$ is the result of the greedy algorithm from the editorial and $$$q$$$ is any other sequence obtained via the same process described in the statement. I claim that $$$p' \prec q'$$$ ($$$p'$$$ minorizes $$$q'$$$) where $$$p'$$$ and $$$q'$$$ are versions of $$$p$$$ and $$$q$$$ sorted in non-increasing order. This is rather intuitive because the greedy algorithm from the editorial achieves the minimum possible sum of the first $$$k$$$ elements in sorted order for any $$$k$$$, corresponding to minorization.
Consider a function $$$f(x) = -\log x$$$ on domain $$$[1, +\infty)$$$. It is convex because its second derivative $$$d^2/dx^2 (-\log x) = 1/x^2 > 0$$$ on our domain. According to Karamata's Inequality we now conclude that $$$\sum_i (-\log p_i) \le \sum_i (-\log q_i)$$$, which is equivalent to $$$\sum_i \log p_i \ge \sum_i \log q_i$$$. Exponentiate both sides to obtain $$$\prod_i p_i \ge \prod_i q_i$$$.
Yeah this is overcomplicated, but the idea to take logs is very good.
If we generalize to wanting to maximize the product $$$a_1 a_2 \dots a_k$$$ at the end ($$$a_i \ge 0$$$), this is equivalent to maximizing $$$\log a_1 + \log a_2 + \dots + \log a_k$$$ (we can say $$$"\log 0" = -\infty$$$).
Now if we consider the function $$$d(n) = \log(n + 1) - \log n$$$, this function is strictly decreasing over $$$n$$$. Since $$$d(a_i)$$$ is the benefit we get from incrementing $$$a_i$$$, it's clear that a straightforward greedy approach of always choosing the smallest first is the right way to go.
Can it be proved by AM-GM inequality ? GM<=AM and equality occurs only if all of the numbers are equal , so we should always try to increase the lowest number.
Proof by AC
even without proving, it's still possible to solve in 6^3 * 1,000 time:
I believe it's possible to solve this problem for any number $$$n$$$ of initial values and any number $$$m$$$ of operations, in $$$O(m + n \log n)$$$ using a greedy approach.
First, sort the initial values and append some huge number. Let $$$i$$$ denote the index of the current number, modulo $$$k$$$, where $$$k$$$ is the index of the next greater number. While $$$a_i$$$ is less than $$$a_k$$$, increment $$$a_i$$$ and then $$$i$$$. When $$$a_i$$$ becomes equal to $$$a_k$$$, increment $$$k$$$ and keep iterating until all operations are used. Finally, compute the answer.
You can actually solve it in just nlogn.
https://codeforces.net/contest/1992/submission/270395681
in question D he has to swim k units right? #include
include
include
using namespace std; typedef long long ll;
ll f(vector &ar, int n, int k, int m) { if (n == 0) return k == 0 ? 0 : -1; ll min_steps = LLONG_MAX; bool found = false; for (int i = 1; i <= m; i++) { if (n — i < 0) break; if ((ar[n — i] == 'W' && k > 0) || ar[n — i] != 'W') { int new_k = k; if (ar[n — i] == 'W') new_k--; ll steps = f(ar, n — i, new_k, m); if (steps != -1) { min_steps = min(min_steps, steps + 1); found = true; } } } return found ? min_steps : -1; }
int main() { ll t; cin >> t; while (t--) { ll n, m, k; cin >> n >> m >> k; vector ar(n + 1, '0'); for (ll i = 1; i <= n; i++) { cin >> ar[i]; } ll check = f(ar, n, k, m); if (check == -1) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } this is giving worng on test 2 idk why...the k is 2 but available only 1 W so how can k be equal ?so it shud be no ryt?
He is allowed to use $$$k$$$ or less.
can someone tell me what is problem in my code
https://codeforces.net/contest/1992/submission/270266835
Is a segment always a continuous array(subarray)?
for F,
input :
4 8
4 2 2 4
optimal division should be 4 4, 2 2
as per the editorial its 4, 2 2, 4.
help please.
yes it is always a subarray
in problem G's solution, shouldn't m be MEX and not MEOW
I am also confused on the same, I believe m should be MEX
The problem D can be solved by just iterating through the string right?
Problem: 957E
Can someone explain why is this code taking so long to execute even when I've made some modifications in the range for b ??
probably because u r concatenating n a times and each time it may require allocating new memory
don't implicitly generate the string, you are creating a massive array: ['a', 'aa', 'aaa', 'aaaa', 'aaaaa', ......] which has size of A^2. Remember that strings are internally char arrays.
Instead, only generate the first 6 characters. Here's my solution for reference: https://codeforces.net/contest/1992/submission/270266899
Tks for the editorial?
Problem F was really good, given the combination of the use of the greedy idea and the $$$dp$$$ approach to find subsequence products. Learnt something new!
can u explain the dp approach of problem f?
I was referring to the same approach mentioned in the editorial. Let me elaborate it here for you.
The greedy idea is to always extend our segment to the right as long as possible until it remains "bad" that is, no subsequence in the segment multiplies to $$$x$$$. This was proved in the editorial that it works, but to know when to stop extending the segment, we need to perform a dynamic programming that will tell us what all factors of $$$x$$$ have been produced by some subsequence in our current segment.
Now, we maintain a set of numbers $$$\text{products}$$$ that can be obtained by multiplying the numbers of some subsequence in the segment that we are currently extending. Now, to know if we can include the current element $$$a[i]$$$ or not in the segment, we need to check if this can create a product of $$$x$$$. This can simply be done by checking if $$$a[i] \mid x$$$ i.e. $$$x$$$ is divisible by $$$a[i]$$$; and the product $$$\frac{x}{a[i]}$$$ exists in $$$\text{products}$$$. If both of the above conditions are true, then we need to end the current segment here and start a new segment from $$$i$$$ (thus making the set empty)
Otherwise, we will update our set of products by iterating through it and for each product $$$p$$$ in it, we will insert the new product $$$p\cdot a[i]$$$ into the set. Note that this might involve duplication of products, so we must update the set using another temporary new set. Details can be found in this submission, which runs in approx. $$$1$$$ s.
The complexity of the solution is $$$O(n\sqrt[3]{x})$$$ as $$$x$$$ has at most $$$\sqrt[3]{x}$$$ divisors.
Can anyone explain the proof of F? Why does this greedy algorithm work. I am stuck in understanding that why taking as much as possible will produce minimum number of bad segments?
Consider the first two segments. If the first one isn't as long as it can be, we can move one element from second segment to the first and both segments are still {bad}. Second segment might become empty, no new segments appear, so by moving element to the first segment we can't mke our answer worse. After we added as many elements to the first segment as possible, we can erase it from the array and use the same logic for next segments. That's why greedy works
Thanks, I was thinking that Segments may not be continuous that's why I couldn't understand.
How a Specialist come up with these ideas?
I am wondering is it possible to solve problem G with O(n) time complexity?
Can someone explain why in problem G with $$$2k<n$$$ when we pick m the answer is $$$\mathrm{C}_{m-1}^{m-k-1}.\mathrm{C}_{n-m}^{2k+1-m}.m$$$. I know two first multiplier is the ways we pick elements before and after m but why we need to multiple with m.
Oh forget that we need calculate the sum of MEX so we need to multiply with m.
coule you tell me why my code is worry?if I turn the push_back into the emplace_back,it will be corrected.
include <bits/stdc++.h>
using namespace std; typedef pair<int,int> PII; int n,l,len,len2;
void solve(){ cin>>n; string s=to_string(n); len=s.length(); while(s.length()<10) s+=s; int val[10]; for(int i=1;i<10;i++) val[i]=val[i-1]*10+(s[i-1]-'0');
}
int main() { int t; cin>>t; while(t--) solve(); return 0; }
Text editorial is very intuitive..!!!
Sorry for late comment, but why doesn't my solution pass? I think I'm missing an edge case.
I did problem E using binary searching for finding value of b, and iterated on a from 1 to 1e4.
273309283
here is my code https://codeforces.net/contest/1992/submission/273669300 for problem D iam getting wrong answer Yes in case 5 1 1 LLWWW , but iam running this case in local editor its giving No , what iam doing here someone please help .
In the tutorial of G , for the case 2k<n , there is a typo, the answer needs to be added with
(m-1)C(m-1-k) * (n-m)C(2k+1-m) * m
Noobish_Monk