Codeforces Round 943 (Div 3) | Video Solutions - A to G1 | by Viraj Chandra | TLE Eliminators
VloĆŸit
- Äas pĆidĂĄn 1. 05. 2024
- Here are the video solutions in the form of a post-contest discussion for problems A, B, C, D, E, F, G1 of Codeforces Round 943. The live discussion was done with students of TLE Eliminators, this is the recording of the same. We hope this will be useful for you in up-solving this contest.
đąCheck out handpicked problems by Priyansh himself, on our CP-31 sheet: www.tle-eliminators.com/cp-sheet
Solution Codes:
Problem A - codeforces.com/contest/1968/s...
Problem B - codeforces.com/contest/1968/s...
Problem C - codeforces.com/contest/1968/s...
Problem D - codeforces.com/contest/1968/s...
Problem E - codeforces.com/contest/1968/s...
Problem F - codeforces.com/contest/1968/s...
Problem G1 - codeforces.com/contest/1968/s...
Be sure to check out TLE Eliminators.
Website: www.tle-eliminators.com/
Instagram: / tle_eliminators
Linkedin: / tle-eliminators
Twitter: / tle_eliminators
TLE Community Discord Server: / discord
Timestamps:-
0:10 Problem A
8:35 Problem B
18:45 Problem C
35:10 Problem D
1:03:35 Problem E
1:17:20 Problem F
1:46:27 Problem G
Please fill the Feedback form for PCD: forms.gle/oMsWq1sRgMNF2oiYA
Best PCD so farđ„đ„đ«Ą.
He even beat Raghav sir in the clarity of explaination.
Great Explanation skills man. Just keep going please don't leave in middle . I'm looking forward for every contest discussion
Really cool explanation and he dicussed about tc and sc also.
you should continue @TLE_ELiminators yt channel. Your explanations are far better than ankit ghildiyal and even better than raghav goel !! please continue here
Thank you so much for sharing this with us †from New York
Great Explination
D WAS ACTUALLY hard
@TLE_Eliminators please make viraj chandra as permanent editorial video publisher for all contests and pls remove ankit ghidiyal his explanation skills are very bad
True
Be grateful for what u get
@@Dadgdybidiot he is giving feedback
@@Dadgdybdusre acc se ao ankit sir đ , btw you should actually try to improve your explanations
@@Idk-qg7hb đđ Ankit nahi hu bro
Excellent explanation by viraj bhaiya...completely solved my doubt in problem 5
nice
For C my idea was similar but instead of going from the end , I started from index 0 with value 501 and then a[i] = x[i-1] + a[i-1]
That's also a good approach!
bro I used almost the same approach , I took a[0] = x[0] + 1 and for the rest of the elements - a[i] = x[i-1] + a[i-1] in a for loop , I tried running it in java was working fine , but it was getting accepted , can u help me why ?
@@sparshgarg7105 If it was getting accepted then what's the issue?
@@VirajChandra not getting accepted in Codeforces but being accepted on my IntelliJ IDE
@sahil___jakhar i did with same approach but why its not getting accpeted
while(t--){
int n;
cin>>n;
int arr[n-1];
for(int i=0;i>arr[i];
}
int ans[n] = {0};
ans[0] = arr[0]+1;
for(int i=1;i
Hello
Can you please tell me what's the use of hashing in question g1.
Let suppose we find a some value(k) by the help of binary search now basically traverse in the string (by sliding window) and find the total number of string which of size k.
Can someone tell me what's the mistake in my approach
According to me it's sc is n log n(in worst case)
I think I have replied to this comment just below.
My approach was a little bit different I will take the 1st number to it and add it into the array and then run the loop and multiply the number with the last index and add the same last index to get the next number of the new array but it is getting WA any idea what the issue is
For smaller numbers this will not work!
Hello sir, i wanted to know that in the problem d, while taking all the possible outcomes of the path
5 2 7 (K=3)
Why didn't we take a possiblity where bodya remains on value 5 for 2 turns and then moves to 2 at the 3rd turn
i.e 5+5+2 =12??
Please explain this sir??
We did take that, that is why we are running a loop of turns. Try to try run the code on the final loop. We are calculating prefixSum*(k-i) + currentValue, which for your case will be 5*(3-1)+2 = 12
For D easier idea would be one cannot repeat the element else it is the last element he/she would be taking:
int n,k;
cin>>n>>k;
int pb,ps;
cin>>pb>>ps;
pb--;
ps--;
vi p(n);
vi a(n);
for(auto &x : p)cin>>x;
for(auto &x : a)cin>>x;
int ans_b = 0, ans_s = 0;
// we have to see how much will it take to get to that particular element right
int temp_sum = 0;
for (int i = 0; i < n && i < k; i++)
{
ans_b = max(ans_b,temp_sum + a[pb]*(k-i));
temp_sum += a[pb];
pb = p[pb]-1;
}
temp_sum = 0;
for (int i = 0; i < n && i < k; i++)
{
ans_s = max(ans_s,temp_sum + a[ps]*(k-i));
temp_sum += a[ps];
ps = p[ps]-1;
}
if(ans_b>ans_s) cout
Great! I think this is almost the same code as explained in the solution.
@@VirajChandra Oo sorry I didn't see your implementation part đ
No sound
Now corrected.
#include
using namespace std;
#define fastio() ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int main()
{
fastio() int t;
cin >> t;
while (t--)
{
long long n, k, PB, PS;
cin >> n >> k >> PB >> PS;
vector a(n);
vector score(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> score[i];
vector pathB;
vector pathS;
vector vis(n, 0);
vis[PB - 1] = 1;
while (true)
{
pathB.push_back(score[PB - 1]);
PB = a[PB - 1];
if (vis[PB - 1] == 1)
break;
} // O(N)
vis = vector(n, 0);
vis[PS - 1] = 1;
while (true)
{
pathS.push_back(score[PS - 1]);
PS = a[PS - 1];
if (vis[PS - 1] == 1)
break;
} // O(N)
long long bs = 0, ss = 0;
long long preSum = 0;
for (int i = 0; i < pathB.size(); i++) // O(min(pathB.size(),k))
{
if (k < i + 1)
break;
long long currS = preSum + pathB[i] * (k - i);
bs = max(bs, currS);
preSum += pathB[i];
}
preSum = 0;
for (int i = 0; i < pathS.size(); i++) // O(min(pathS.size(),k))
{
if (k < i + 1)
break;
long long currS = preSum + pathS[i] * (k - i);
ss = max(ss, currS);
preSum += pathS[i];
}
if (bs > ss)
cout
Are you sure? I just submitted this code it works!
@@VirajChandra yes,it worked!
Mistake in the title.
Thanks for the correction.
â@@TLE_Eliminators
Hello
Can you please tell me what's the use of hashing in question g1.
Let suppose we find a some value(k) by the help of binary search now basically traverse in the string (by sliding window) and find the total number of string which of size k.
Can someone tell me what's the mistake in my approach
According to me it's sc is n log n(in worst case)
@@Sid-jb6lg Hi! We need to find the size K strings which are same. To check their similarity, you need a hashing algo to improve TC.
@@VirajChandra hey!!
But both complexity same then why we are doing hashing
@@Sid-jb6lg to compare if two strings are same you need a TC of O(N) where n is the size of the string, whereas string hashing does this is O(1) per query for (l,r) pair.