A. FashionabLee :
Invented by DeadlyCritic.
$$$\mathcal Brief\;\mathcal Solution :$$$
A $$$n$$$-regular convex polygon is beautiful if and only if $$$n \% 4 = 0$$$. ($$$\%$$$ is the modular arithmetic symbol)
t = int(input())
for testcase in range(t):
n = int(input())
if(n%4 == 0) :
print("Yes")
else :
print("No")
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
if(n % 4 == 0){
cout << "YES\n";
}
else cout << "NO\n";
}
}
B. AccurateLee :
Invented by DeadlyCritic.
$$$\mathcal Brief\;\mathcal Solution :$$$
If the string $$$s$$$ is non-decreasing, then the answer is $$$s$$$ itself, otherwise the answer is $$$x+1$$$ zeroes and $$$y$$$ ones, where $$$x$$$ is the number of leading zeroes of the string $$$s$$$, and $$$y$$$ is the number of trailing ones of the string $$$s$$$.
t = int(input())
for testcase in range(t):
n = int(input())
s = input()
lef, rig, sw = 1, 1, 0
for i in range(n-1):
if(s[i] > s[i+1]):
sw = 1
break
if(sw == 0):
print(s)
continue
for i in range(n):
if (s[i] == '1'):
lef = i
break
for i in range(n-1, 0, -1):
if (s[i] == '0'):
rig = i
break
st = s[:lef] + '0' + s[rig+1:]
print(st)
#include <iostream>
#include <string>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
string s;
cin >> s;
int sw = 1;
for(int i = 1; i < s.size(); i++){
if(s[i] < s[i-1])sw = 0;
}
if(sw){
cout << s << '\n';
continue;
}
string ans;
for(int i = 0; i < s.size(); i++){
if(s[i] == '1')break;
ans.push_back('0');
}
ans.push_back('0');
for(int i = s.size()-1; i >= 0; i--){
if(s[i] == '0')break;
ans.push_back('1');
}
cout << ans << '\n';
}
}
C. RationalLee :
Invented by DeadlyCritic and adedalic.
$$$\mathcal Brief\; \mathcal Solution$$$ :
Give greatest elements to friends with $$$w_i = 1$$$. For the rest sort the elements in non-descending order of $$$a_i$$$ and sort the friends in non-ascending order of $$$w_i$$$ then give first $$$w_1-1$$$ elements to friend $$$1$$$, next $$$w_2-1$$$ elements to friend $$$2$$$ and so on, also give $$$k-i+1$$$-th greatest element to friend $$$i$$$ $$$(1 \le i \le k)$$$.
t = int(input())
for tc in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
w = list(map(int, input().split()))
a.sort(reverse = True)
w.sort()
ii, l, r = k, 0, n-1
ans = 0
for i in range(k):
if(w[i] > 1):
ii = i
break
ans = ans+a[l]*2
l = l+1
for u in range(k-1, ii-1, -1):
i = w[u]
ans = ans + a[l] + a[r]
r = r-i+1
l = l+1
print(ans)
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define int ll
using namespace std;
const int MN = 2e5+7;
vector<int> v[MN];
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
for(int i = 0; i <= n; i++)v[i].clear();
ll a[n], w[k];
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < k; i++){
cin >> w[i];
}
sort(w, w+k);
sort(a, a+n);
for(int i = 0; i < k/2; i++)swap(w[i], w[k-i-1]);
int po = 0;
for(int i = 0; i < n-k; i++){
while(w[po] == v[po].size()+1)po++;
v[po].push_back(a[i]);
}
ll ans = 0;
int qf = 1;
for(int i = 0; i < k; i++){
ans += a[n-i-1];
if(v[i].size())ans += v[i][0];
else ans += a[n-qf], qf++;
}
cout << ans << '\n';
}
}
D. TediousLee :
Invented by DeadlyCritic.
$$$\mathcal Brief \mathcal Solution$$$ :
Realize that a RDB of level $$$i$$$ is consisted of a vertex (the root of the RDB of level $$$i$$$) connected to the roots of two RDBs of level $$$i-2$$$ and a RDB of level $$$i-1$$$.
Run a DP and calculate the answer for each level $$$i$$$ ($$$ 3 \le i \le 2 \cdot 10^6$$$), then $$$dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?4:0)$$$.
v = []
v.append(0)
v.append(0)
v.append(0)
v.append(4)
v.append(4)
mod = int(1e9+7)
for i in range (5, 2000010):
v.append(max(((2*v[i-2])+v[i-1])%mod,((4*v[i-4])+4*v[i-3]+v[i-2]+4)%mod))
t = int(input())
for _ in range(t):
print(v[int(input())])
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = int(1e9+7);
const int MN = int(2e6+7);
int dp[MN];
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
dp[0] = dp[1] = 0;
dp[2] = 4;
for(int i = 3; i < MN; i++){
long long w = dp[i-1];
w += 2*dp[i-2] + (i % 3 == 2)*4;
w %= mod;
dp[i] = w;
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
n--;
cout << dp[n]%mod << '\n';
}
}
Challenge : Try solving problem D for $$$n \le 10^{18}$$$. (no matrix-multiplication)
E. DeadLee :
Invented by DeadlyCritic.
$$$\mathcal Hints$$$ :
Find some greedy approaches. Its guessable that the problem is greedy.
Define $$$s_i$$$ for food $$$i$$$ equal to the number of guys who likes food $$$i$$$. Then find some condition which is enough to be sure that no answer exist.
See the last friend in a suitable permutation. What food will he eat?
Its easy to see that if $$$\forall 1 \le i \le m \Rightarrow s_i > w_i$$$, then no answer exist.
If a food $$$i$$$ exist such that $$$s_i \le w_i$$$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods.
$$$\mathcal Brief\;\mathcal Solution$$$ :
Define $$$s_i$$$ equal to the number of friends who likes food $$$i$$$. If for some $$$i$$$, $$$s_i \le w_i$$$ then place all the friends who likes food $$$i$$$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods
It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!!
import sys
import heapq
inputarray = [int(x) for x in sys.stdin.read().split()]
n, m = inputarray[0], inputarray[1]
s, w = [], []
for i in range(2, n+2):
w.append(inputarray[i])
g, eg, foodm, friendm, x, y = [], [], [], [], [], []
for i in range(n):
s.append(0)
foodm.append(0)
g.append([])
for i in range(m):
friendm.append(0)
x.append(0)
y.append(0)
inppo = n+2
for i in range(m):
x[i], y[i] = inputarray[inppo], inputarray[inppo+1]
inppo = inppo+2
x[i] = x[i]-1
y[i] = y[i]-1
u = x[i]
v = y[i]
s[u] = s[u]+1
s[v] = s[v]+1
g[u].append(i)
g[v].append(i)
eg.append((v, u))
myq = []
ans = []
for i in range(n):
heapq.heappush(myq, (-w[i]+s[i], i))
while len(myq):
u = myq[0]
heapq.heappop(myq)
if u[0] != -w[u[1]]+s[u[1]]:
continue
if(u[0] > 0):
print("DEAD")
sys.exit()
foodm[u[1]] = 1
sw = 1
for i in g[u[1]]:
if friendm[i] == 0:
friendm[i] = 1
if y[i] == u[1]:
x[i], y[i] = y[i], x[i]
s[x[i]] = s[x[i]]-1
s[y[i]] = s[y[i]]-1
heapq.heappush(myq, (-w[y[i]]+s[y[i]], y[i]))
ans.append(i)
if(len(ans) == m):
sw = 0
break;
if(sw == 0):
break
print("ALIVE")
for i in ans[::-1]:
print(i+1, end=" ")
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int MN = 2e5+7;
int x[MN], y[MN], s[MN], w[MN], mark[MN], colmark[MN];
vector<int> v[MN], a;
vector<pii> f;
priority_queue<pii, vector<pii>, greater<pii>> pq;
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)cin >> w[i];
for(int i = 0; i < m; i++){
cin >> x[i] >> y[i];
s[x[i]]++;
s[y[i]]++;
v[x[i]].push_back(i);
v[y[i]].push_back(i);
}
for(int i = 1; i <= n; i++){
if(s[i])pq.push({max(0, s[i]-w[i]), i});
else colmark[i] = 1;
}
while(pq.size()){
auto q = pq.top();
pq.pop();
if(q.fr != max(0, s[q.sc]-w[q.sc]))continue;
if(q.fr > 0){
cout << "DEAD\n";
exit(0);
}
int id = q.sc;
vector<int> wt;
for(auto u : v[id]){
if(mark[u])continue;
a.push_back(u);
if(x[u] == id)
swap(x[u], y[u]);
if(!colmark[x[u]])wt.push_back(x[u]);
mark[u] = 1;
}
sort(all(wt));
for(int i = 0; i < wt.size(); i++){
s[wt[i]]--;
if(i == wt.size()-1 || wt[i+1] != wt[i]){
if(s[wt[i]]){
if(max(0, s[wt[i]]-w[wt[i]]) == 0)colmark[wt[i]] = 1;
pq.push({max(0, s[wt[i]]-w[wt[i]]), wt[i]});
}
}
}
}
cout << "ALIVE\n";
for(int i = 0; i < a.size()/2; i++)swap(a[i], a[a.size()-i-1]);
for(auto u : a){
cout << u+1 << ' ';
}
cout << '\n';
}
F. BareLee :
Invented by DeadlyCritic and AS.82.
$$$\mathcal Brief\; \mathcal Solution$$$ :
Define $$$win_{s,\,e}$$$ ($$$s \le e$$$) equal to $$$1$$$ if Lee can win the game when $$$s$$$ is written on the board, and equal to $$$0$$$ otherwise, also define $$$lose_{s,\,e}$$$ the same way.
Win :
If $$$e$$$ is odd then if $$$s$$$ is odd Lee loses otherwise Lee wins. So if $$$e$$$ is even then :
- if $$$\frac e 2 < s \le e$$$ then if $$$s$$$ is odd then Lee wins, otherwise Lee loses;
- if $$$\frac e 4 < s \le \frac e 2$$$ then Lee wins;
- if $$$s \le \frac e 4$$$ then the answer is equal to $$$win_{s,\, \lfloor \frac e 4 \rfloor}$$$.
Lose :
If $$$e < 2 \cdot s$$$, then Lee can immediately lose, otherwise the answer is equal to $$$\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$$$.
import sys
inpy = [int(x) for x in sys.stdin.read().split()]
def win(s, e) :
if e == s :
return False
if e == s+1 :
return True
if e % 2 == 1 :
if s % 2 == 1 :
return False
return True
q = e//4
if s <= q :
return win(s, q)
q = e//2
if(s > q) :
return (e-s) % 2 == 1
return True
def lose(s, e) :
q = e//2
if(s > q) :
return True
else :
return win(s, q)
t = inpy[0]
start = (True, False)
inpo = 1
v = (True, True)
for tc in range(t):
if(inpo+1 >= len(inpy)) :
print('wtf')
s, e = inpy[inpo], inpy[inpo+1]
inpo = inpo+2
v = ((win(s, e), lose(s, e)))
if start[0] and start[1] :
break
if (not start[0]) and (not start[1]) :
break
if start[1] :
v = (not v[0], not v[1])
start = (v[1], v[0])
if((start[0] != True and start[0] != False) or (start[1] != True and start[1] != False)) :
print('wtf')
sw = 2
if start[1] :
sw = sw-1
print(1, end = ' ')
else :
sw = sw-1
print(0, end = ' ')
if start[0] :
print(1)
sw = sw-1
else :
print(0)
sw = sw-1
if sw :
print(wtf)
#include <iostream>
#include <vector>
#include <string>
#define fr first
#define sc second
#define ll long long
#define int ll
using namespace std;
const int MN = 1e5+7;
pair<int, int> c[MN];
int chk(ll s, ll e){
if(e == s)return 0;
if(e == s+1)return 1;
if(e & 1){
if(s & 1)return 0;
return 1;
}
if(s <= e/4)
return chk(s, e/4);
if(s > (e/4)*2)return ((e-s)&1);
else return 1;
}
int lck(ll s, ll e){
if(s*2 > e)return 1;
int w = e/2 + 3;
while(w*2 > e)w--;
return chk(s, w);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n;
cin >> n;
for(int i = 0; i < n; i++){
ll x, y;
cin >> x >> y;
c[i] = {chk(x, y), lck(x, y)};
}
int f = 1;
int s = 0;
for(int i = 0; i < n; i++){
if(f == 1 && s == 1)break;
if(f == 0 && s == 0)break;
if(s == 1) c[i].fr^=1, c[i].sc^=1;
f = c[i].sc;
s = c[i].fr;
}
cout << s << ' ' << f << '\n';
}
I appreciate your effort, but this contest was very mediocre. Problemsetting might not be the job for you guys. It was basically Geometryforces, and I'm not good at geometry. Please, no more geometry problems.
If you know you're bad at geometry, study up on geometry and stop blaming the author for using too many geometry problems.
As I know the round has minimum possible non-zero geometry.
I'm not good at CP. Please no more CP problems. Only 1+1 problems.
It sounds like "I don't know geometry, dp, binary search so don't make contests with such problems". Moreover, the only task there with geometry is A...
O looks like a circle. All statements have at least 1 occurrence of the letter o in them. That's the most geometryforces round I've ever seen!
faast tutorial..
Is there anyone who can explain me the second problem. I can't understand it properly.
In second one you are given a binary string Carry out the following steps ; .
1.Select a 1 such that there is immediate 0 next to it
2.Delete either 0 or 1
. Repeat the above two steps and continuously reducing the string. There will exist a optimal choices on part 2 such that the string is reduced to smallest length possible and if such lengths strings are many you need to output the lexico wise smallest.
Nice!!! Thanks
Video tutorial for Problem A,B and C Video Link
Video Tutorial for Problem D Link
This is the Video Tutorial for B https://youtu.be/PYPoOCav4Jk
Video solutions to all problems are available at the end of my screencast, for people who are interested.
Please keep doing these videos.. they are really helpful.
One for all!!Now I don't need to watch different video as I get everything in one place!!!
It's really helpful. Thanks.
The quality(explanation) of video forced me to press the bell icon..keep doing this brother .Take love.
Thank you. Please keep doing this.
Really enjoyed the problemset!
In pD: I saw some people use max even under mod 1e9 + 7. Why is that correct.
Because the numbers you take the max of are very close to each other, so if you assume that the dp values are almost random the chance of there being an error in $$$n \leq 2 \cdot 10^6$$$ is pretty small.
In fact the smallest such $$$n$$$ was so so so big, like $$$10^9$$$.
challenge for D: 84826892
Exactly, nice job.
@can you give a further explanation of this solution ?
I found it using generating functions. but once you guess it you can prove it by simple induction.
Can you explain how you derive it?
See my comment
Problem D can be solved in $$$O(log(n))$$$
My Approach in blog: Here
It seems like there is no $$$n \le 2 \cdot 10^6$$$ such that $$$dp[n][0] \equiv 10^9 + 6 \mod (10^9 + 7)$$$, since otherwise the answer for $$$n = 2 \cdot 10^6$$$ will be different
Will you please elaborate what are you talking about? Because i solved D and did not have any such doubt but i want to know?
max(9,11)%10=11%10=1 , but max(9%10, 11%10)%10=9. That's why it "looks" possible that if you always keep the answer mod-ed, taking the max might create problems. That's what people tried to prove/disrove above. I hope it helps.
Thanks!
And I was so afraid to do that!! Wasted an hour and then ended up doing the same thing. Lowkey felt it was going to fail systest.
Can someone help in knowing why B was so hard for me? I didn't struggle on C as much as I did in B. Please help me realize what's wrong in my practice and thought process.
You should first work out a sound algorithm for every question and then you can code! I hope you use pen and paper to help visualize stuff?
D can be solved with matrix exponential as well. And one can make the constraint to be n <= 1e9 to force using fast matrix power.
I am unable to understand this point. Could you pls share some resource to digest your point
https://www.geeksforgeeks.org/matrix-exponentiation/
This should help.
It's a combination of matrix multiplication as transition + fast power for speeding up.
how will you handle the case if i%3==0 then dp[i]++
You can take vector $$$a_k = [x_{3k}, x_{3k+1}, x_{3k+2}, 1]$$$ and derive formula for $$$a_{k + 1}$$$ in terms of $$$a_k$$$
Is this method same as what is used for finding Fibonacci numbers ??
I think it can be done only if we have the relation:
dp[i] = dp[i-2]*2 + dp[i-1]
But we also have additional constraint:
for every i divisible by 3, dp[i]+=4
The best I could get is a $$$10\times 10$$$ matrix (84825762), which might TLE on $$$n\leq 10^{9}$$$ and probably TLE on $$$n\leq 10^{18}$$$, with $$$10^4$$$ testcases. Can it be done with a smaller matrix?
A $$$4 \times 4$$$ matrix should work, but matrices doesn't help with solving the challenge, the intended solution works in $$$O(1)$$$ for each test case. (considering $$$x^y$$$ to be calculated in $$$O(1)$$$)
3*3 can do (in the comment)
Sure, I can't count, my matrix was $$$3 \times 3$$$ as well.
Yeah it's not for solving the challenge; I just need to work on my matrix expo skills lol
Can you do it with a 5x5? You need just a linear combination of dp[n-1], dp[n-2], n%3==0, n%3==1, and n%3==2, in order to determine dp[n], right?
Your method seems cool too!
Oh, so you cycle the extra addition instead of the whole equation. That's neat! Edit: implemented this here 84829787
Can you explain what does the matrix represent? How does the values of matrix a are filled?
https://cp-algorithms.com/algebra/fibonacci-numbers.html Scroll down to matrix form on that page. The recurrence in the DP is very similar to fibonacci.
Can you explain how do you use the (i%3) condition in your linear relation?
Sorry if it's a trivial question.
If you write out the matrix on paper, you'll see that each time you multiply some initial vector by the matrix, the last 3 entries will shift cyclically. You can use that to add a value every 3rd step.
T =
0 1 0 dp[i-1]
2 1 0 dp[i]
0 0 1 1
T3 =
0 1 0 dp[i-1]
2 1 1 dp[i]
0 0 1 1
T3 * T * T
Hope this is clear enough :)
maxwill Using your relation, I came up with a formula for when n%3==0,1,2 respectively, but there seems some mistake which I'm not able to figure out.
The above applies when n%3==0, and similarly I've worked out other two cases, but idk why this starts giving wrong output from 9 onwards. Is there some mistake in this relation? How do I correct it. I've spent hours.
(ABC)^n != A^n B^n C^n. And your T is ambiguous.
T_n
is the nth term.T
andT3
are the matrices{{0,1,0},{2,1,0},{0,0,1}}
and{{0,1,0},{2,1,1},{0,0,1}}
Final answer of any n will be n*4. I haven't made any mistake in calculating power of the matrix, I've checked that function. I don't know what am I missing xUPD: I was doing a blunder in multiplication. Therefore, changed the matrix. Now, rather than using multiple 3X3 matrices, I am using one 4X4 matrix and finally got AC. 84893815.
I still wonder, how do we solve it using two 3X3 matrices.__
Your program is doing TTT*...*T3T3T3*x
While the answer should be T3TT*...*T3TT*x
That is a force online solution, which would've make it a bit much more harder :)
I don't think so. Whoever can come up the recurrence AND knows matrix exponentiation will definitely be able to implement it quite quickly. In fact, I tried the mat expo first, only to notice later that it wasn't necessary. A little harder, yes. But still, well within the range, I believe.
Maybe, but I messed up with recurrence (mod 3) part and didn't think about matrix expo.
WOW!! the editorial came fast!!
a great contest!
what's wrong with my solution?
DIV 2/C
solution link : https://codeforces.net/contest/1369/submission/84811103
Check output for:
1
5 2
7 3 2 1 1
3 2
Lee
It's a lie, Lee -> Me.
Another Lee
How the fuck is the editorial blog uploaded 5 hours ago when the contest started 2.5 hours ago !!?
it was private
ohh...i didn't know about private blogs LOL.
It was written at that time but was hidden
it was magic
Did you really expect the contestant to prove C during the contest, or just do a Proof By AC? I mean I got 3 WA trying different greedy algos without proving them and I knew that almost everyone submitted without being completely sure of the proof.
Lol is there something to prove? It was obvious for me
I did proof it in $$$2$$$ minutes, but my English sucks so It became so long.
I think the proof is quite intuitive. The author's explanation is too wordy.
Notice that
We can break down the problem into finding the $$$\sum_i MAX(friend_i) + \sum_i MIN(friend_i)$$$
For some large $$$a_i$$$, it is easy to use it to maximize the $$$\sum_i MAX(friend_i)$$$ by giving it to a person with no gifts. This suggests for each person's initial gift, we should be handing out one gifts to each person in decreasing order
In order to maximize $$$\sum_i MIN(friend_i)$$$ as well, we notice that $$$MIN(friend_i) == MAX(friend_i)$$$ if $$$w_i = 1$$$. So, we reorder our gifts so people with $$$w_i = 1$$$ get the largest gifts.
Because of the way the MIN function works, it' doesn't make sense to give someone many gifts with high $$$a_i$$$, then one gift with low $$$a_i$$$. Similar to last point, it's more efficient to give the better gifts to friends with smaller $$$w_i$$$. This way, we burn less of the good gifts on people. This suggests that we should use a greedy solution to fill the remaining $$$w_i$$$ for each friend and we should fill the friends with smaller $$$w_i$$$ first, with the largest unused $$$a_i$$$.
This is a garbage proof.
The purpose of a proof is to convince someone that a solution is correct.
Can I spend 10 more minutes to come up with a more rigorous proof? Probably. Do I want to spend 10 more minutes to do it during a contest? Probably not.
And since we're being evaluated on our ability to code and not on our ability to prove our solutions, using non-rigorous proofs is the correct way to go as long as the proofs can convince OURSELVES that a solution is correct.
This is not an unrigorous proof because it is not anything resembling a proof.
But don't reply now, I have got no patience.
In almost every wrong greedy you can come up with something to convince yourself. The purpose of the proof is NOT to convince, the purpose of the proof is to give 100% confidence. Convince seems a weaker word to me, I am usually convinced by every other wrong solution.
I don't feel good about your proof. For example, why try to maximize MAX for each friend first? Can increasing MINs at the cost of some MAXs be better? Of course, the answer is NO. Simply, because here, the algorithm is indeed correct. But your proof is a bit too handwavy to address many of the critical issues.
Ok, how about this proof? First, you sort your integer Array from largest to smallest and start distributing to friends from the front. also you sort your friends from smallest to biggest by w.
the first priority friend is the friend with w = 1. because if you give to that friend, the happiness is boosted twice. After giving the integers to that friends with w=1, the second priority is maxing the MAX of the leftover friends. that way, you dont waste your big numbers between MAX and MIN of the friends. you distribute your numbers one by one to your friends and max their MAXes.
then you need to start wasting your numbers, the way to do it is starting with friends with small w so you dont waste as much numbers.
end?
This is an excellent proof
The first bullet point in your proof was the main thing I needed to realize to solve this problem.
Stucked at B for a while? Thinking what should i remove 1 or 0 in the middle part? Can someone gimme idea?
The key intuition here is that you cannot change the leading 0s or trailing 1s. Anything in between, however, can be converted into a 0 in some way, so you don't need to remove anything. All you have to do is keep the leading 0s and trailing 1s, and if elements remain in the middle, add a 0 in between.
the 0 is added is the 0 right before the trailing 1s in original string
There were just certain observations that
1.You can't change leading zeros and trailing 1s
2.Anything in between can be transformed to 1 or 0
Like *****110010**** — ****10010**** — ****1010**** — ****110**** — ****10**** — ****1**** or — ****0****
3.But since we need lexico wise smallest we'll take 0
4. Hence our answer becomes (leading 0s) + 0 + (trailing 1s)
An ideal contest with ideal timing and ideal problems! Liked it!
Fastest system testing I have ever seen.
The problems were LoveLee!
HonestLee!
Wow. What an editorial. I honestly felt like I made some problems harder for myself than they actually were LOL
I will add implementations soon.
unrated
unrated
how unrated become expert??
the_secret DivQ contest
WoW
amazing...
unrated is rated
yui_chan
O(N + M)
solution for E. We need to make the observation that as long as the degree of a node is not greater than the value of the node, it is always optimal to remove it as late as possible. Then we can run a process similar to topological sort to check if we can remove all edges.Link: https://codeforces.net/contest/1369/submission/84803734
Nice. :)
this is clean
Thanks for the solution. I have a doubt though. instead of checking !rem[nxt.s] why can't we just use !vis[nxt.f]. I tried it didn't work but couldn't understand why.
Hopefully you see why with this case:
Edit: Sorry, this case does not disprove your point due to the weird way I checked the
vis
array. However, you must realize that edges should still be removed even if both nodes it connects are visited :)I got the case See the 5th test case. The logic that we need not remove an edge if both nodes are visited is perfectly alright. But what is happening is if we check only that we will be repeating operations for the same edges because queue may contain multiple entries of the same node. suppose you have three nodes between 1 and 2. Then if you start from 1, you will push 2 into the queue 3 times. Now when you iterate for 2 if you don't check the edges then you will loop 3 times for each edge. Hence you get an error. Btw, thanks for looking into it.
Precisely. The duplicate entries are caused by the abnormal placement of the
vis[cur] = 1
line, which in turn causes the error you mentioned. Please see the more accurate implementation here, where the case I mentioned would effectively break if you checked for!vis[nxt.s]
instead.I guess the lesson to be learned here is to always implement as precisely as possible, otherwise debugging may become a lot harder :D
Thanks for the great quality questions! I really enjoyed solving it :) The difficulty gradient was so good for me ;)
Extremely well written tutorial,super easy to get
Special thanks for hints in problem E, actualLee they are better than the complete solution.
B. TLE on test case 9. How to optimise it?
Try using StringBuilder instead of += for making large strings.
Also, use an object new BufferedReader(new InputStreamReader(System.in)) to read the input instead of Scanner if there's lots of it. Also, use new PrintWriter(System.out) if outputing a lot of data.
Can someone please tell me why am i getting WA on pretest 2 in C : Link to code
Because it is not optimal solution to give backpacks in line. Give first k maximal elements to every friend and then try to maximize the minimum elements for every friend as explained in editorial.
nice contest.
You need to multiply (i % 3 == 0 ? 1 : 0) part in D's brief solution by 4
Can anybody explain how we form the graph in problem D? I read the problem statement multiple times but couldn't figure out how they made the Level 4 graph. :(
So,3rd level graph is given int the question
Nodes with no children -> 3,5,4 Add 1 child to these(8,10,9 respectively) , Nodes with 1 child -> 2 Add 2 children to it(7,6) ,
No need to add children to 1 as it already has more than 2 children
Man. Div. 2 A's are getting harder and harder these days. Most people will probably intuit the right answer, but I usually prove before submitting, and some recent Div. 2 A's have very non-trivial proofs.
It has quite a straightforward proof. We know that in an n sided polygon, each internal angle is (n-2)*180/n. To get this value, we basically divided the polygon into triangles, and there n-2 triangles in a polygon, and every triangle has 180 degrees, so there are (n-2)*180 degrees. Now, let's choose a point and think about every triangle originating from that point. Then, every angle from that point will be equal to (n-2)*180/(n*(n-2)) => 180/n. Now, for one side to be parallel to x axis and one side to y axis, a right angled triangle needs to exist. This means that there has to exist a pair of points such that the angle between them is 45degrees. So, we can basically form an equation like this: (180/n)*x = 45, where x is the distance between these two points. The x and to be an integer, so solving for x we get => (1/4)*n. This means, that n has to be a multiple of for an integer solution to exists. I know, proof is very messy, but hope this makes sense!
I solved D using normal 2D dp,
dp[i][1] = dp[i-1][0] + dp[i-1][0] + dp[i-1][1]
anddp[i][0] = max(dp[i-1][0],dp[i-1][1]) + max(dp[i-1][0],dp[i-1][1]) + max(dp[i-2][0],dp[i-2][1])
I created a DS to store quotient and remainder to compare modulo values
My solution: Link
satvik_sharma what is your dp states?
in first equation 2 i-1 should be placed by i-2 and in second 1 i-1 should be replaced by i-2
get it
Wow, I made solution to problem D that is different from editorial https://codeforces.net/contest/1369/submission/84820772 I used cnt[i] — count of added vertices in i level, and lol[i] — answer for i level
Very Good Contest and Fast Editorial
Here's an easier analysis for A. The exterior angle (diagram below) of a regular polygon of n sides is 360/n
In order for one side to align to the vertical and another side to the horizontal, the sum of the exterior angles of some k consecutive sides must equal 90.
We must have
(360/n) * k = 90
k = 90*n/360 = n/4
So n must be a multiple of 4 for such an integer k to exist.
I came up with the same proof, but it was harder for me to write it in English. Thanks for doing it instead of me. :D
My pleasure. I wish coming up with solutions quickly was easier for me than writing proofs :D
https://codeforces.net/contest/1369/submission/84793979
could someone help me with this submission.dont know why is this wrong, i guess its the same approach as in editorial
Try
Should it matter if $$$w = [1, 3]$$$ or $$$w = [3, 1]$$$ ?
thanks bro, found my mistake
Great contest with perfect Timing and as well as excellent problem set.
Is there a greedy solution for D.TediousLee
I have done the exact same thing , why am i getting wrong ans verdict on c qn https://codeforces.net/contest/1369/submission/84794143
add condition z<n in while loop
such a silly mistake,thanks
Feeling Very Sad,this is the first time i have solved 3 problems in div 2. But could not submit C because of the power supply went off for about 30 minutes.
DeadlyCritic In problem E, the last sample test case:
Suppose, following is the ordering in which Lee's friends eat
[u -> v means (u-th friend eats v-th food)]
:My answer:
Why is this ordering wrong?Please help!
when friend i goes to kitchen, he tries to eat x_i AND y_i, even the x_i is exists
so, the 9-th friend eats not just 3, but 1 too
Oh, Okay! So, if both favourite foods of the friend exist, he/she will eat both of them? You mean this, right?
It was clearly explained in the statements =(.
I am sorry but I thought the same too ... Except for that it was a great problemset, looking forward to more contests by you
We were expecting some people to thing like this, so we spent quite a long time to write the statements as clear as possible, I'm sorry that it was not as good as I expected.
i really don't see how the proof for problem D says that we should use i % 3 and that magic while computing the answer?
Let the answer for RDB of level $$$i$$$ be $$$dp_i$$$ . Also an RDB of level i is connected to two RDB of level $$$i-2$$$ and one RDB of level $$$i-1$$$.
Note that it is beneficial to ignore the root vertex of RDB of level $$$i$$$ if $$$dp_{i-2}$$$ requires the root to be included. Because, at the cost of adding one claw of $$$i-1$$$, we'll lose two claws, one for each RDB of level $$$i-2$$$.
For $$$dp_{i-1}$$$, it doesn't matter whether we include the root or not because either way no extra claw gets added or removed.
Also if both $$$dp_{i-1}$$$ and $$$dp_{i-2}$$$ doesn't require their root to be included to get their respective values, we'll add root of RDB of level $$$i$$$.
Point 3 gives an idea on whether to include root or not in point 2. That it is if including the root doesn't matter in getting $$$dp_i$$$, we'll always not include it. Because in doing so, we may get a better answer for $$$dp_{i+2}$$$. Say we'll include root for $$$i$$$, then we can't (or rather shouldn't) include root for $$$i+1$$$ and $$$i+2$$$, but this implies we'll include root for $$$i+3$$$. In the question, we have to include root for $$$i = 3$$$, so we have to include root for $$$i=6,9,12,..$$$ as well. That is where that $$$i$$$ % $$$3$$$ comes into play.
Great explanation, thank you, idk how didn't that cross my mind.
Is there any way to see full test case, my code failed system testing in B but I can't figure out on which test case: https://codeforces.net/contest/1369/submission/84767454
Resubmit it, then you'll be able to see.
change your first loop FOR(i,N-1) to FOR(i,N).
Thanks Newton, that's what I did wrong
Try this video solution : Problem B
Why this doesn't work for D? I find for every level how many more(new) vertices with 3 children were added from previous level and then do dp[i]=dp[i]+dp[i-2]. Solution: https://codeforces.net/contest/1369/submission/84822790
You are saying you count new vertices but you are doing dp[i][2] = dp[i-1][2]+dp[i-1][1]. So it is getting added cumulatively.Also for ith layer you need to do dpp[i] = dp[i][2]+dpp[i-3]. You can see this after drawing some trees.
Yea dp is adding cumulatively but dpp stores the added vertices as they come only from dp[i-1][1].
https://codeforces.net/contest/1369/submission/84819647 Can anyone tell me whats wrong with my C solution. First I sorted the interger lee has in descending order.Then I sorted w array in ascending order. Then I took the case for when w[i]=1. I gave them maximum value.Then I disitributed interger to W[i] one by one. It will be a great help if anyone call tell me my mistake
Try this video solution : Problem C it covers case where w[i] = 1
What's wrong with my solution ? Question B ; My solution : https://codeforces.net/contest/1369/submission/84814815
try this video solution : Problem B
Why there are not the codes for the solutions in the editorial?
I'm working on it, I have a very bad headache right now so I'm pretty slow.
In D can someone explain why is 1 added if i is divisible by 3
Because that gives an AC !
Gotcha, thanks a lot!
Because when i%3 u can use the top claw (1;2;3;4)
Oh damn, can you also explain how did you reach to this in the contest? What was your approach to the question?
Thank you!
Suppose you used the root for some x. Now, x will be a child of both x+1, and x+2 so, in either of them, you can't use the top claw (because it's child is x and it's root has been used already). Now, for x+3, it's children will be x+1, and x+2 whose roots are free and you can use the top claw in this case. It's a period of 3, just check where it starts.
nice explanation
Here's my thought process in this problem:
If you look at the case n=4 closely, you'll see that the tree RDB(4) is actually composed of a root node linking to 2 instances of RDB(2) and an instance of RDB(3).
Now, because of this, we might start to think that a[i]=a[i-1]+2*a[i-2]. This formula holds true for n=5, but doesn't for n=6 if you check by hand. Why is this? It turns out that, again, checking by hand, in the case n=6 we can use the top claw.
Again, we think about when it is possible to use the top claw. Clearly, when n=4 and n=5 we couldn't use the top claw because we did that when n=3. However, when n=6, we can use the top claw as we did not when n=4 and n=5.
We see that we can use the top claw in the case n when we didn't in the case n-1 and n-2. Seeing as 3 is the first n to allow this, we conclude that we can use the top claw if n is divisible by 3.
Therefore we have the above formula: a[i]=a[i-1]+2*a[i-2]+4*(i%3==0).
This was very helpful. Thanks a lot!
question B sucked my whole contest.
B. Accuratelee Explanation Video >>> https://www.youtube.com/watch?v=EoJetsWa9k0 Hope it helps :)
thank you brother, for your care and support.
hi guys try these video solutions ->
Problem A
Problem B
Problem C
Problem D Tried to explain graphically how DP is working :)
Hope it Helps.. :)
I accidentally used Ideone on public settings and someone copied and submitted the same code int this contest and now i received a system email regarding the penalty for this. Can someone guide me as to what should i do. This is the link of my submissions https://ideone.com/qDpu3b
Nice way of writing editorial...!!! DeadlyCritic
Implementations are out, sorry Python solution for D is missing yet.
Just volunteering:)
For pB I tried to use a "more greedy" approach, which consisted on going backwards on the string and once I had a zero I would starting deleting ones until the last one. Then I looped again though the string, starting from the first One and deleting all zeros that followed, except for the last, which was kept and the One deleted. It ended up being pretty messy, but it worked, even tough I didn't had time to submit it during the contest because of some stupid bugs. Here is my solution, you won't have a good time looking at code(it is pretty messy as I said), but here it is: 84823891
https://codeforces.net/contest/1369/submission/84825830 is there anyone who can tell me why I am getting Memory limit exceeded on test 2
for problem D,someone please tell me why this dp relation is wrong,i made two cases if we color root and if not, v[i]=max(((2*v[i-2])+v[i-1]),((4*v[i-4])+4*v[i-3]+v[i-2]+4))
Even after giving so many contests, I can't solve div2 C problems. I can solve them in upsolving but I can't solve them during contests. Can anyone please help me to overcome my this problem, please even single advice will help me. Btw here is the link to my upsolved div 2 C problem. I am expecting help from the community. Help me.
What's wrong with my solution? 84826635
I use a 3d dp to keep a count of vertices with 0, 1 and 3(the outer ones, as they will only contribute to the next state) children. Then I say that:
I fill the
dp
tilli = 2000002
using the above relation. And finally output(dp[3][n]*4)%MOD
There is some mistake in this logic. But I'm not able to figure out where and how to fix it?
you can't take all claw. In n'th level if you have total m claw then you can take less then m claw. Because some claw's overlap with another claw. see my solution.
Can you elucidate it a bit, please? I don't understand what is the use of calculating dp[i][3], in your solution? And how exactly are you working out states in sol[]?
okay.in my solution here,
dp[i][0] is the number of nodes which has 0 child in i'th level, dp[i][1] is the number of nodes which has 1 child in i'th level, dp[i][3] is the number of nodes which has 3 child in i'th level, at the same time dp[i][3] denotes total number of claws.
in sol[] array I calculate the solution for n'th level in sol[n].
in my solution,
sol[n]= sol[n-3] + number of new claw added in n'th level * 4 .
** claws which were added newly in n-1 and n-2 th claw are overlapped.So i didn't count them.
Can you provide a test case where this method would fail..?
I can't understand problem F. Why in this sample case
The output is
?
I thought, these scenarios is possible:
1 -> Lee 2 -> Ice Bear 4 -> Lee 8 -> Ice Bear 16 (Lose) -> Next Round 4 -> Ice Bear 5 -> Lee 6 or 10 (Lose)
1 -> Lee 2 -> Ice Bear 4 -> Lee 8 -> Ice Bear 9 -> Lee 18 (Lose) -> Next Round 4 -> Lee 5 -> Ice Bear 6 or 10 (Lose)
Hence Lee can win and can lose too.
Where did I go wrong? Or maybe, what does it mean by "can be the winner independent of Ice Bear's moves or not" and "can be the loser"?
Here "can be the winner" means that Lee has a strategy where he will definitely win and Ice Bear can't prevent this. Similarly for "can be the loser".
Indeed, the problem statement is a bit ambiguous.
How to solve D for n <= 10^18 without matrix multiplication?
See my comment
https://codeforces.net/contest/1369/submission/84784718 O(N + M) solution for E. It's basically finding an ordering such that if you use that order to direct the edges, out_degree[i] <= a[i]. So you can code it in almost the same way as you would code finding a topological ordering.
hello sir, the editorial is awesome and one more thing you provided all code in python too. Thanks a lot sir
E question can be solved using data structures
Editorial with complete proof is good. It helps me with my poor math......
I have a better solution for D(which is close to phrasing the question in another way),
you can think of nodes in 3 — levels
level1 — it is just one node without any children (when it moves to level 2 it gives rise to 1 another node)
level2 — it is node with one child (when it moves to level3 it gives rise to 2 other nodes)
level3 — this node will be our matter of interest which won't give rise to any other node but it signifies atleast one claw(4 nodes)
you can compute level1 ,level2 ,level3 nodes for height-MAX_n using simple dp
level3[i] = (level3[i-1]+level2[i-1])%MOD
level2[i] = level1[i-1]
level1[i] = (level1[i-1] + level2[i-1]*2)%MOD
now precompute all answers for 1 <= i <= 2* 10^6,
which is easy to compute using simple observation, for some i , ans[i] = (ans[i-3] + level3[i] — level3[i-1])%MOD
which means the, if you include claws which changed from level2 to level3 during transition of height i-1 to i , you cannot include nodes which became level3 at height i-1 but you can add nodes which became level3 at height i-2 but not at i-3 ...so on (which is just ans[i-3])
now output ans[height]*4
FrostGod Shouldn't it be
ans[i] = (ans[i-3] + level3[i] — level3[i-1])%MOD
?I am sorry that was a typo , thanks for noticing it
[user:freemancs]Shouldn't it be at height i-3 but not at i-2?
Can you attach the solution for this algo. Thanks!!.
it is in my submissions you can check it out
[video editorial for third question] — (https://www.youtube.com/watch?v=5V-RiprjfJQ)
In the announcement of the Contest, Author should have written in the name of Lee as its heading.Lol!
For question C, can anyone please tell me why this solution is giving wrong answer and why the other one is being accepted. They both are doing the exact same thing.
Wrong Solution — https://codeforces.net/contest/1369/submission/84832565 Right Solution — https://codeforces.net/contest/1369/submission/84832850
Thank You!!
Video Solutions for A B C Hope u guys like it :)
Problem A:
Problem B:
Problem C:
Nice explanation for solution B.
In problem E, I still can't figure out why the situation where si>wi for all i has no solution after I read Complete Solution, could someone explain it in more detail?
The easiest way to look at it is that in this situation you won't be able to fix the last friend in the permutation. Suppose we fix some friend as the last one in the permutation with food choices as (x,y) , now there will be 0 x left and 0 y left when it is his/her turn because sx-1 times people have eaten X before him and as sx>wx , hence we will have 0 'x' left and same argument for 'y' , so there cannot exist any last friend which implies there is not solution.
Thank you so much.
Video tutorial for problem B
@DeadlyCritic Apparently the naive n^2 AC's in java for B: 84798072
I guess the moral of the story is make n 3e5 in the future :(
This is not n^2. It's linear.
ArrayList.remove() is O(n) and that is called O(n) times, so it is n^2.
Yes but it depends from which index we are removing. We say it's O(n) because we need to shift the elements after the index of removal. But here we can clearly see that this person is removing either the last element of the list or 2nd last. So in the worst case time taken will be O(2n) not O(n^2). :)
That's not true. If the string is 100000... then they are removing the second element each time, so it is n^2. You see this by running it locally on a 1 followed by 10^6-1 0s and it will take forever.
Yes you test case is right. It will give TLE. Sorry!. but this is true best complexity for removal is O(1) when we remove from the last index. You can see this
Yeah, I know, I'm a java main. My point is that this code is the n^2 and AC's anyway even though it shouldn't because the max n is too small.
Interesting, thanks for letting me know.
Could you please in Problem F, elaborate how did you conclude that
Because whoever wins that game gets to play in (e / 4, e / 2], thus wins.
For problem D, consider the following dp: let a[n] be the answer if we color the root, and b[n] be the answer if we do NOT color the root. They obey the recurrence given in the code below. Then the solution is max(a[n], b[n]). But this does not coincide with the results using the code from the editorial. What am I missing?
Because you are thinking $$$unrooted_n = rooted_{n-1} + 2*rooted_{n-2}$$$. This is not correct. $$$unrooted_{n-2}$$$ might be better than $$$rooted_{n-2}$$$. In other words, for $$$unrooted_n$$$, you have the capability to take the children rooted, but it is not mandatory. You are making it mandatory. This wrongful enforcing causes the problem.
Can anyone explain the reason behind adding (i%3==0) in problem D?
The explanation seemed a bit less explanatory! (and without any pictures)
I almost figured out the solution during the contest except this part :\
Here
Can anyone please explain me the approach of problem D? Thanks :)
If you start constructing the tree, you will find a pattern.
The tree of level "i" will have a subtree of level "i-1" in the middle and 2 subtrees of level "i-2" on the 2 sides. The structure will be exactly the same as obtained for levels "i-1" and "i-2".
Thus, dp[i] = dp[i-1] + 2*dp[i-2] + (i%3==0)
The last part comes from the fact that after every 3 steps, the root claw becomes available to use.
Credits for the explanation of the last step: anshumankr001
Video Link for D: Tedious Lee
Small improvement of tutorial's C code. If you want to sort array in descending order, instead of sort and reverse (also you could write std::reverse), you can use sort(v.rbegin(), v.rend()) for vectors or sort(a, a+n, greater) for arrays
I solved problem D by keeping count of nodes with 0,1,3 children. The claws (nodes with 3 children) at level
n-3
do not overlap with the bottom most claws at leveln
and can simply be added to the answer of leveln
. The bottom most claws will contribute 4 yellow nodes each. If we keep track of how many claws there are at leveln
we can find our answer.For every
n
counts are updated as -84837417
Four methods for Problem D:
Method 0. using dp as the Editorial given: $$$a_i = a_{i-1} + 2 \cdot a_{i-2} + (i \% 3 == 0?4:0)$$$ (use $$$a_i$$$ instead of $$$dp_i$$$ for short) Code: 84808226
Expand the above recurrence formula we have
with $$$a_0 = a_1 = a_2 = 0$$$, and $$$A$$$ indicate the coefficient matrix.
Method 1. using fast matrix power we can get $$$a_{3 \lfloor \frac{n}{3} \rfloor + 2}, a_{3 \lfloor \frac{n}{3} \rfloor + 1},a_{3 \lfloor \frac{n}{3} \rfloor}$$$, and $$$a_{3 \lfloor \frac{n}{3} \rfloor + n \% 3}$$$ is the answer
Method 2. It is well known that If you know the characteristic polynomial of matrix, then you can use polynomial multiplication instead of matrix product to get $$$(a_{3n+2},a_{3n+1},a_{3n},1)^T$$$ which is faster that Method 1, especially when the size of $$$A$$$ becomes bigger. Best method in general as I know (can't use NFT, since neither size of A is big nor 1,000,000,007 is NFT-friendly.)
Method 3. Note that the special $$$A$$$ can be diagonalized, thus there exist an invetible matrix $$$X$$$ such that
thus we have
We can calculate $$$X$$$ above by hand or using following SageMath Code:
Actually we can calculate $$$A^n$$$ with only 3-lines SageMath Code:
and the last column of $$$A^n$$$ is
Code: 84843466
By using another approach based on the ideas in this blog, thinking of the +4 as impulses in the recurrence f(x+2) = f(x+1) + 2*f(x) we can end in a nicer formula using geometric sums: $$$\frac{4(\frac {1 - 8^{floor(N/3)}} {1-8} \cdot 2^{N mod 3 + 1} - \frac {1 - (-1)^{floor(N/3)}} {1-(-1)} \cdot (-1)^{N mod 3 + 1})}{3}$$$
Code
That's the intended solution, nice!
Thanks! I understand how you get the geometric sums, by calculating generating function. Really much nicer!
tfg how did you add the impulse in the recurrence relation and get a closed formula for the generating function
jianglyFans How did you come up with this matrix. can you please elaborate the steps. If the (i % 3 == 0) condition is not present than it is easy because we can have a 2*2 matrix. But when this condition comes into play how to construct that matrix? I struggle coming up with matrices for linear recurrence, is there a good resource to learn from?
and then write in matrix form
Well done! nice problemsetting.
Video Tutorial for Problem D Link
Problem E...If every time one friend can choose one favorite food to eat.How can solve it?
That becomes a max flow problem. Source -> virtual vertex for edge -> actual vertices -> sink, edges in (vertices -> sink) have capacity a[i], there's a valid answer iff max flow is M.
Though it would be interesting if someone found a faster solution, since if a[i] = 1 we can solve this variation of bipartite matching using a dsu.
Oh,i know.Thanks.
But if we need to find the order,is this problem solveable?
In your version of the problem, the order doesn't matter. To find which food each one eats just check which edge in (virtual vertex for edge -> actual vertices) edges.
I am a little bit confused about the flow graph.
Do you mean I can construct a flow gragh. Sources->foods->persons->sink.
It's fully connected between sources and foods, the flow between them is the number of each food type, I mean w[i] in 1369E - DeadLee.
The link between the foods and persons depends on the person's preferences, each link's flow is 1.
The last, it also fully connected between persons and sink, which flow is also 1.
And now, we can check the maximum flow in at the sink, if
max_flow
<the number of person
, it's invalid.Am I right? Thanks in Advance.
Yes, your graph is the reverse of mine so it looks correct. I didn't remember the story in the problem so "edge" is person and "vertex" is food.
Not sure if it's commented before, problem E can be solved in O(n+m) by bfs. The key is thinking the process in reversed order, though I came up with it after the contest :(. 84843536
Hi! Can somebody explain how to connect all of the individual answers in problem F?
If I can choose to play firstly or secondly in one round,we consider the next round:
if there exists one wining strategy,now I can win the game directly;
otherwise I can leave the situation to the other player and I can win also.
Obviously I can also choose to lose the game.
If I can only play firstly or secondly,now I should update the f/s in one round and go on.
Sorry for my bad English:)
Thanks!
Can problem E be solved using multiple instance bipartite maximum matching? If anyone solved it using this way please share.
2 2 1 1 1 2 1 2 Why does this sample have no solution for problem E?
Can anybody explain me why am i getting run time error in my solution for problem C — https://codeforces.net/contest/1369/submission/84814630
Yes! In your
comp
function, changea>=b
toa>b
. I tried your code with this modification and it is working fine. A better alternative is to usesort(a, a+n, greater<int>())
. You won't have to writecomp
function again.Yes it helped and solution got accepted.I wish I could have noticed it during the contest. Thank you so much. Although I wonder why was I getting run time error because of this. I mean how does it matter.
Even I have no clue. I don't see any reason for different outputs. Can somebody please explain?
C++ sort requires the comparison function to have strict weak ordering (https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings) — if comp(a,b) is true then it means a has to be placed before b. If it finds a situation where comp(a,b) is true and comp(b,a) is true it throws an exception as it can't find a valid way to handle that.
If your comparison function does return equal values as true then it will often work for some values as not every values is compared.
Can you give an example? I tried with an array
{1,2,2,3,4,5,6,6,7}
and it didn't throw an exception.It looks like I was slightly misremembering and there isn't an exception. It's just undefined behaviour and different compilers handle it differently. On the versions I've got locally the code below triggers an invalid comparator assert on MSVC and segmentation faults on g++ / clang++.
Oh! Now I understand. Thanks a lot :)
Hi guys try this video solution of Problem D Here I have tried to Explain how DP is actually being applied graphically to this .. Hope it Help :)
problem D: I am not clear why will be add 1 when i%3==0 . Can anyone pls help.
pls can someone tell me the editorial of accuratelee in a easy way i m not able to understand it
Question no. 1
int main() {
} **** Can some explain where I m getting wrong?
Each exterior angle of a polygon is 360/n, where n is number of sides. Thus (360/n)*x = 90 must be satisfied, which gives the relation x=n/4. Hence if n is divisible by 4 answer will be YES else NO
ll z = y rounds y down (at least for positive y), so if it's close to an integer, but due to rounding errors is slightly below, then z and y will differ roughly by 1 To check if a floating point is close to integer you can use abs(floor(x) — x) <= some epsilon (but of course you don't need it in this problem)
Thanks for the rounding value stuff. Now it got accepted.
I meant llround, not floor. If you use floor we have the same problem as with just casting ld to ll.
About D's analysis, I think the natural way is to enum the root's color and get $$$dp_i = max(dp_{i-1}+2*dp_{i-2},dp_{i-2}+4*dp_{i-3}+4*dp_{i-4}+4)$$$, so how to come up with the tutorial naturally?
Video explanation for problem D
In C can't we just sort in ascending order then give one max element and rest min elements to every friend(except those which need only one element in which case we give him just one max element)? What am i missing?
Pfff... lots of useless comments, newbies and pupils have made this comment section shit.
You are only 108 rating above the upper bound of pupil so don't consider yourself to be isolated from them, You are also among them in some manner
But atleast i give my effort, some guys are asking questions without even reading the editorial and also there are video tutorials available to these problems, why not just watch those videos before posting something like ""Can anyone explain problem A in simple word please?""
Shut up u lil piece of shit
I'll see you after few months
no.
Video for D: Tedious Lee
Hi, Problem D, the expression (i % 3 == 2) is used in tutorial to add 4 new nodes to the answer. But how can we know this is the levels that should included in optimal solution? Could be another remainder, not? For example, (i % 3 == 1), or (i%3==0). Thank you.
It is possible to add one more claw containing root if an only if for $$$i - 1$$$ and $$$i - 2$$$ it is not possible.
Now we only need to directly check, that for $$$1$$$ and $$$2$$$ it's impossible and then use basic mathematical induction.
Brief Solution is really a good idea.
don't try to be an extra-ordinary by posting video solution of problems when solution is already posted by others(seniors)
If anyone need Detail Explanation(not Video Tutorial) For D Here
Your explanation is absolutely amazing.
Can someone please explain, how to solve E using graphs?
In ques E editorial Saying for all i, si>wi will lead to lee death is invalid test case- 3 3 1 1 1 1 3 1 2 2 3 here 1st friend can get 1st dish , 2nd can get 2nd and 3rd can get 3rd . But according to editorial lee will be dead. can anyone clarify this? thanks in advance
DeadlyCritic, is the given python solution for problem D correct ? the max of mods is being taken rather than the values..
Read this comment.
https://codeforces.net/contest/1369/submission/85417639 could someone tell me what is wrong in the code I am not able to figure it out why it is coming that on test 7 alive is not printed
You are using
ios_base::sync_with_stdio(false);
so you should not usescanf
andprintf
, I replaced them withcout
, here is your code getting AC.O(n + m) solution for D https://codeforces.net/contest/1369/submission/85417877
O(n) solution for 1369E — DeadLee 85817429
DIV2 C was a good greedy
My Solution :
We sort a in descending order and w in ascending order. The logic is we have to maximize Max+Min for every friend,so we first give the maximum elements for each friend.Now every friend got one integer and that is his maximum integer.We will remove all these integers from array "a".Now we have to give each person a minimum integer.
We have to maximize the minimum integer given to each friend.Now say a friend requires y more integers,and the minimum is say x,then there should be atleast y-1 integers greater than or equal to x in a.So we given each friend the yth greatest available integer.
The reason for sorting w is, say one friend requires y elements and another requires z elements, we give the yth greatest integer for the first friend and y+zth greatest for second friend, a[y]+a[y+z],say y>z,then sum will be a[z]+a[z+y],the farther the integer is lesser it will be,so we have to satisfy the friend with lesser w.
My solution : 87000341
DeadlyCritic In problem E , you have told that if $$$s_i<=w_i$$$ , then we need to keep that person in end , but what to do in other case ? We can't simply print that person , order does matter , so how to determine that order.For example in sample input 4 , there are more than 1 people for whom $$$s_i>w_i$$$ holds for both plates they want , so what to do in that case ?
Are you asking this : "how to find a good order for foods"?, so we use a priority queue, and we check if the food with minimum $$$w[i]-s[i]$$$ is fine.
Here's an alternate solution for problem D: ` Let us define $$$dp_1[i]$$$ = maximum possible nodes we can colour yellow for an RBD of level i if the root node must also be coloured yellow and $$$dp_2[i]$$$ = maximum possible nodes we can colour yellow for an RBD of level $$$i$$$ if the root node must not be coloured yellow. Then, after making the observation that an RBD of level $$$i$$$ consists of a node connected to the roots of two RBD's of level $$$i - 2$$$ and one RBD of level $$$i - 1$$$, we get the following recursion relations : $$$dp_1[i] = 2dp_2[i - 2] + dp_2[i - 1]$$$ and $$$dp_2[i] = 2max(dp_1[i - 2], dp_2[i - 2]) + max(dp_1[i - 1], dp_2[i - 1])$$$. Then, the answer to each query is simply $$$max(dp_1[n], dp_2[n])$$$.
Here's my submission: 93394017
lets say x = 1e9 + 8 , y = 1e9 + 6 then when you compare x%MOD and y%MOD (where MOD == 1e9+7) . it will give wrong ans , how come you are still getting correct answer ??
Know this is late, but I was able to get the dp transition for problem D by simplifying the graph. I realized that we only care about the claws, so I replaced the graph with a more compressed graph where each node is a claw, and an edge connects 2 nodes iff the claws shared an adjacent edge in the original graph. Then it's a lot easier to get the transition and find the pattern. I filled out 3 whole pages for this problem XD.
best editorial i have ever seen . i appreaciate for ur efforts. Thanks a lot