Thanks K1o0n for being the mvp of this round.
Idea: Vladosiya
Preparation: K1o0n
Let's prove why it's always better to add to the smallest number, let $$$a \le b \le c$$$, then compare the three expressions: $$$(a+1)\times b \times c$$$, $$$a \times (b+1) \times c$$$, and $$$a \times b \times (c+1)$$$. Remove the common part $$$a \times b \times c$$$, and we get: $$$b \times c$$$, $$$a \times c$$$, $$$a \times b$$$.
$$$b \times c \ge a \times c$$$, since $$$a \le b$$$, similarly, $$$b \times c \ge a \times b$$$, since $$$a \le c$$$. Therefore, we can simply find the minimum $$$5$$$ times and add one to it. And thus, obtain the answer.
Another, primitive approach is to simply iterate through what we will add to $$$a$$$, $$$b$$$, and $$$c$$$ with three loops.
Since we can only add $$$5$$$ times, the time complexity of the solution is $$$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])
Idea: Noobish_Monk
Preparation: K1o0n
Let's say we want to connect two casseroles with lengths $$$x$$$ and $$$y$$$. We can disassemble one of them into pieces of length $$$1$$$ and then attach them to the casserole of size $$$y$$$. In total, we will perform $$$2x - 1$$$ operations. Since we want to connect $$$k$$$ pieces, at least $$$k - 1$$$ of them will have to be disassembled and then attached to something. If we attach something to a piece, there is no point in disassembling it, because to disassemble it, we will need to remove these pieces as well. Therefore, we want to choose a piece to which we will attach all the others. It will be optimal to choose a piece with the maximum size and attach everything to it. Thus, the answer is $$$2 \cdot (n - mx) - k + 1$$$, where $$$mx$$$ $$$-$$$ the length of the maximum piece.
Solution complexity: $$$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 - Gorilla and Permutation
Idea: K1o0n
Preparation: K1o0n
Let $$$p$$$ be some permutation. Let's look at the contribution of the number $$$p_i$$$ to the sum $$$\sum_{i=1}^n {f(i)}$$$. If it is less than $$$k$$$, the contribution is $$$0$$$, otherwise the contribution is $$$p_i \cdot (n - i + 1)$$$. Similarly, let's look at the contribution of $$$p_i$$$ to the sum $$$\sum_{i=1}^n {g(i)}$$$. If it is greater than $$$m$$$, the contribution is $$$0$$$, otherwise it is $$$p_i \cdot (n - i + 1)$$$. Since $$$m < k$$$, each number gives a contribution greater than $$$0$$$ in at most one sum. Therefore, it is advantageous to place numbers not less than $$$k$$$ at the beginning, and numbers not greater than $$$m$$$ at the end. Also, numbers not less than $$$k$$$ should be in descending order to maximize the sum of $$$f(i)$$$. Similarly, numbers not greater than $$$m$$$ should be in ascending order to minimize the sum of $$$g(i)$$$.
For example, you can construct such a permutation: $$$n, n - 1, \ldots, k, m + 1, m + 2, \ldots, k - 1, 1, 2, \ldots, m$$$. It is easy to see that $$$\sum_{i=1}^n f(i)$$$ cannot be greater for any other permutation, and $$$\sum_{i=1}^n g(i)$$$ cannot be less for any other permutation, so our answer is optimal.
Solution complexity: $$$O(n)$$$.
for _ in range(int(input()):
n,m,k = map(int,input().split())
print(*range(n,m,-1), *range(1,m))
Idea: ArSarapkin
Preparation: K1o0n
In this problem, there are two main solutions: dynamic programming and greedy algorithm.
Dynamic programming solution: $$$dp_i$$$ $$$-$$$ the minimum number of meters that need to be swum to reach the $$$i$$$-th cell. The base case of the dynamic programming is $$$dp_0 = 0$$$. Then, the update rule is: \begin{equation*} dp_i = \text{minimum of} \begin{cases} dp_{i-1} + 1& \text{if } A_i = \text{'W'} \\ min(dp_j) & \text{for all } j, \text{where:} \max(0, i — m) \le j < i \text{ and } A_j = \text{'L'} \end{cases} \end{equation*} Solution complexity: $$$O(nm)$$$.
Greedy algorithm solution: If we can jump, we want to jump to the shore if possible. If we can't, we want to jump to any log ahead to jump from it later. If we can't, we jump as far as possible to avoid crocodiles and swim as little as possible.
Solution complexity: $$$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";
}
}
Idea: Noobish_Monk, K1o0n
Preparation: K1o0n
Notice that $$$n * a - b$$$ is strictly less than $$$10^6$$$, i.e., it has no more than $$$6$$$ digits. The number of characters in the strange calculation $$$n * a - b$$$ is equal to $$$|n| * a - b$$$, where $$$|n|$$$ is the number of digits in n. Let's iterate over the value of $$$a$$$, and then determine the boundaries $$$minB$$$ and $$$maxB$$$ for it, such that $$$|n| * a > maxB$$$ and $$$|n| * a - minB \le 6$$$. Then: \begin{cases} minB = |n| * a- 6 \\ maxB = |n| * a- 1 \end{cases} Let's iterate over all $$$b$$$ from $$$minB$$$ to $$$maxB$$$. To quickly check the strange calculation, let's only find its first $$$|n| * a - b$$$ digits. This way, we can find all suitable pairs $$$(a, b)$$$.
Solution complexity: $$$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)
Idea: Noobish_Monk
Preparation: Noobish_Monk
Let's consider the greedy algorithm ``take as long as you can''. Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct.
Now let's figure out how to quickly understand if the segment can be extended. First, find all divisors of the number $$$x$$$. If the number $$$a_i$$$ is not a divisor of it, then it cannot be included in any set of numbers whose product is equal to $$$x$$$, so we can simply add it to the segment. If $$$a_i$$$ is a divisor, we need to somehow learn to understand whether it, in combination with some other divisors, gives the number $$$x$$$ on the segment. We will maintain a set of divisors that are products of some numbers in the segment. To update the set when adding $$$a_i$$$, we will go through all the divisors of this set and for each divisor $$$d$$$ add $$$d \cdot a_i$$$ to the set. If we added the number $$$x$$$ to the set, $$$a_i$$$ will already be in the next segment and we need to clear the set.
P. S.: About implementation details and runtime. If you maintain the set in a set structure, then we get a runtime of $$$O(n \cdot d(x) \cdot \log(d(x)))$$$, where $$$d(x)$$$ is the number of divisors of $$$x$$$. Instead of a set, you can use, for example, a global array $$$used$$$ of size $$$10^5 + 1$$$, as well as maintain a vector of reachable divisors. Using these structures, you can achieve a runtime of $$$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;
}
Idea: Noobish_Monk, K1o0n
Preparation: K1o0n
We will iterate over the size of the set $$$k$$$ and its $$$\text{MEOW}$$$, $$$m$$$. If $$$2k \geqslant n$$$, then the set $$$x$$$ will fill all the remaining numbers up to $$$n$$$, and there may still be some larger than $$$n$$$ in it, so the $$$MEOW$$$ of all such sets will be $$$2k+1$$$, and there will be a total of $$$C(n, k)$$$ such sets for each $$$k$$$. If $$$2k < n$$$, $$$m$$$ lies in the interval from $$$k+1$$$ to $$$2k+1$$$. Notice that there can be exactly $$$m - 1 - k$$$ numbers before $$$m$$$, and correspondingly $$$2k + 1 - m$$$ numbers to the right of $$$m$$$, so the answer needs to be added with $$$C_{m - 1}^{m - 1 - k} \cdot C_{n - m}^{2k + 1 - m} \cdot m$$$.
Asymptotic complexity of the solution: $$$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;
}
Thanks for the fast text editorial!
Thanks for the fast text editorial! :D
Thanks for editorial
tks for the tutorial :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
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?
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.
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
Hey guys, I had an out-of-the-box solution for problem E. I wanted to know your opinion on the same as the approach might be controversial:
Brute forcing all possible combinations without giving much thought would take
O(n*max(a)*max(b))
amount of time. A general thumb rule is that the time forO(1e8)
operations is in the order of a second. Therefore iterating over alln,a,b
took me around 4-8 minutes, and did not take much effort to code it out. I stored the output into a file (removed the trivial cases ofn == 1
anda-b == 1
), and copied it into my final submission code, as each of the cases (except for 1) seemed to have not greater than 5 solutions each.This wasn't during the contest but it seems like a nice way to tackle questions that don't have a humongous output for all test cases combined, and the input range is very limited, and brute force fetches the output quickly(for a human) without much thinking. Obviously this question's solution was not so difficult to think about or implement, but it seems like a good idea nevertheless in general.
Feel free to give your comments on the same, albeit controversial or not. Below is a link to my submission for the same:
https://codeforces.net/contest/1992/submission/284429181