Hey Shayan, nice work. I had a doubt in problem F, we are iterating and inserting elements into the set at the same time, but why does it not cause any issue?
Can someone guide me out like i took 40 minutes for Problem B how can one have a good grasp on such questions like what would make think faster than this
You should focus on problem-specific practice. Start with basic data structures like arrays and maps. Then, move on to harder problems and algorithms. This approach will help you recognize patterns when you encounter problems, enabling you to identify the appropriate strategies quickly. For example, Problem B is a basic greedy problem. Consider this approach: -Think about what you can do with just two numbers. -Then, consider what changes if you add a third number. -Identify the operation that will effectively reduce the number of elements in the array. In this case, that operation involves making one of the numbers equal to 1 (as there’s no other way to remove a number). The optimal strategy is to make the smaller number 1, as it requires fewer operations. Now, if you add more numbers, you can continue by combining the smallest number with the largest, reducing the problem back to two numbers.
I took 7 minutes, which I'm not happy with because I should have solved it a lot faster. The key here was to realise that you can pick any of the pieces to add all the others onto, but the optimal way to do it was to pick the one with maximal length.
Basically practice, you will develop intuition then. In my case, I knew it was a greedy problem and have been solving greedy problems. I knew we had to basically keep the bigger intact, convert all the smaller ones to 1 and then add them all. Once you know the algorithm, it's pretty easy to code it
there's no need to use dp when the problem doesn't require it. In this case, the greedy solution is best. I solved it by realising that: 1. if you're on land and the next step is also land, it's optimal to just walk. 2. if you're on land and the next step is not land, it's optimal to jump to the furthest land that is less than or equal to m away, and if there is no land, then jump to the furthest water 3. if you're on water, you have just one option, move forwards and decrement k. if k==0, output "NO" 4. if you're on a crocodile, just print "NO" because there is obviously nothing you could have done NOT to hit the crocodile. and you can make the problem easier by adding a piece of land at the beginning and end, and adding 2 to N. this handles the case where you're jumping from land over a bunch of crocodiles/water.
@@asdfasdf-s7m 😂😂 Shayan explained the solution pretty well, it’s just when I wrote the code I was getting wrong outputs at last I was able to get correct outputs with the following code import java.util.*; public class Problem1992D { private static final int INF = 1_000_000_007; private static void solve(Scanner sc) { int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); sc.nextLine(); String s = sc.nextLine(); s = "L" + s + "L"; n += 2; int[] dp = new int[n]; Arrays.fill(dp, INF); dp[0] = 0; m++; for (int i = 0; i < n; ++i) { if (dp[i] == INF) continue; if (s.charAt(i) == 'L') { for (int j = i; j < Math.min(n, i + m); ++j) { if (s.charAt(j) != 'C') { dp[j] = Math.min(dp[j], dp[i]); } } } if (i + 1 < n && s.charAt(i + 1) != 'C') { dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1); } } System.out.println(dp[n - 1] 0) { solve(sc); } sc.close(); } }
Can be done without dp. int main() { int t; cin >> t; while (t--) { int n, m, k; cin >> n >> m >> k; string s; cin >> s; int flag = true; int wat = 0; for (int i = 0; i < n; i++){ wat ++; if (s[i] == 'L'){ wat = 0; }
if (wat >= m){ k--; if (s[i] == 'C'){ flag = 0; } } } if (flag && k>=0) { YES; } else { NO; } } return 0; } →Judgement Protocol Test: #1, time: 15 ms., memory: 0 KB, exit code: 0, checker exit code: 0, verdict: OK Input 6 6 2 0 LWLLLW 6 1 1 LWLLLL 6 1 1 LWLLWL 6 2 15 LWLLCC 6 10 0 CCCCCC 6 6 1 WCCCCW Output YES YES NO NO YES YES Checker Log ok 6 token(s): yes count is 4, no count is 2 close
Thank you for your comment. I will try to improve the videos. About text editorial, authors already do that. So I guess it is already available, doesn't that work?
I personally prefer the videos - they're often higher quality explanations. Sometimes the text editorials miss out important details or are simply unintelligible.
![Interview with Product Manager in 2024 [Corporate]](/img/n.gif)
really appreciate your solutions!
Thank you!
Thank you for making this video, i was only able to do Q1 and Q2. now you helped me do rest 🙏
great explanations !!!!. There are other people who explain the problems but your explainations are just so detailed yet breif..
Thank you, bro!
Very happy to hear
Thank you Shayan for the editorial, Helped a lot
great help man awesome solution discussion
Thank you a lot
It will be really good if you can bring a full series on maths, combinatorics and probability
Hey Shayan, nice work. I had a doubt in problem F, we are iterating and inserting elements into the set at the same time, but why does it not cause any issue?
great work brother
in the problem F, shouldn't the answer of 7th test case provided be 2, the segments being 4 4 6 5 1 1 and 2?
In Question f, how to know that gready would work? how did you came up with that!
Sir I think computing n c r again and again will cause time limit exceed in problem g. If not can you explain why?
great channel bro
Thank you so much ❤
great!
problem E your showing code is not work properly ...
can you give me the code ?
noice
Can someone guide me out like i took 40 minutes for Problem B how can one have a good grasp on such questions like what would make think faster than this
more practice is the answer
You should focus on problem-specific practice. Start with basic data structures like arrays and maps. Then, move on to harder problems and algorithms. This approach will help you recognize patterns when you encounter problems, enabling you to identify the appropriate strategies quickly.
For example, Problem B is a basic greedy problem. Consider this approach:
-Think about what you can do with just two numbers.
-Then, consider what changes if you add a third number.
-Identify the operation that will effectively reduce the number of elements in the array.
In this case, that operation involves making one of the numbers equal to 1 (as there’s no other way to remove a number). The optimal strategy is to make the smaller number 1, as it requires fewer operations. Now, if you add more numbers, you can continue by combining the smallest number with the largest, reducing the problem back to two numbers.
I took 7 minutes, which I'm not happy with because I should have solved it a lot faster. The key here was to realise that you can pick any of the pieces to add all the others onto, but the optimal way to do it was to pick the one with maximal length.
Basically practice, you will develop intuition then. In my case, I knew it was a greedy problem and have been solving greedy problems.
I knew we had to basically keep the bigger intact, convert all the smaller ones to 1 and then add them all.
Once you know the algorithm, it's pretty easy to code it
Can anyone tell me the time complexity of problem g
can somebody help me with the dp solution of Problem - D pliz
there's no need to use dp when the problem doesn't require it. In this case, the greedy solution is best.
I solved it by realising that:
1. if you're on land and the next step is also land, it's optimal to just walk.
2. if you're on land and the next step is not land, it's optimal to jump to the furthest land that is less than or equal to m away, and if there is no land, then jump to the furthest water
3. if you're on water, you have just one option, move forwards and decrement k. if k==0, output "NO"
4. if you're on a crocodile, just print "NO" because there is obviously nothing you could have done NOT to hit the crocodile.
and you can make the problem easier by adding a piece of land at the beginning and end, and adding 2 to N. this handles the case where you're jumping from land over a bunch of crocodiles/water.
@@asdfasdf-s7m Thanks for the greedy solution, I understood the greedy solution, but I wanted to try the DP solution as well
@@rlm3227 I don't understand how you would use DP either lol
@@asdfasdf-s7m 😂😂 Shayan explained the solution pretty well, it’s just when I wrote the code I was getting wrong outputs at last I was able to get correct outputs with the following code
import java.util.*;
public class Problem1992D {
private static final int INF = 1_000_000_007;
private static void solve(Scanner sc) {
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
sc.nextLine();
String s = sc.nextLine();
s = "L" + s + "L";
n += 2;
int[] dp = new int[n];
Arrays.fill(dp, INF);
dp[0] = 0;
m++;
for (int i = 0; i < n; ++i) {
if (dp[i] == INF)
continue;
if (s.charAt(i) == 'L') {
for (int j = i; j < Math.min(n, i + m); ++j) {
if (s.charAt(j) != 'C') {
dp[j] = Math.min(dp[j], dp[i]);
}
}
}
if (i + 1 < n && s.charAt(i + 1) != 'C') {
dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
}
}
System.out.println(dp[n - 1] 0) {
solve(sc);
}
sc.close();
}
}
Can be done without dp.
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
int flag = true;
int wat = 0;
for (int i = 0; i < n; i++){
wat ++;
if (s[i] == 'L'){
wat = 0;
}
if (wat >= m){
k--;
if (s[i] == 'C'){
flag = 0;
}
}
}
if (flag && k>=0) {
YES;
} else {
NO;
}
}
return 0;
}
→Judgement Protocol
Test: #1, time: 15 ms., memory: 0 KB, exit code: 0, checker exit code: 0, verdict: OK
Input
6
6 2 0
LWLLLW
6 1 1
LWLLLL
6 1 1
LWLLWL
6 2 15
LWLLCC
6 10 0
CCCCCC
6 6 1
WCCCCW
Output
YES
YES
NO
NO
YES
YES
Checker Log
ok 6 token(s): yes count is 4, no count is 2
close
I request you please do text editorials as well for others who like to read and understand better.
This is his independent editorials. Text editorials are provided by the contest organisers.
mmkmk
text editorials are much better than this.
Thank you for your comment. I will try to improve the videos. About text editorial, authors already do that. So I guess it is already available, doesn't that work?
I personally prefer the videos - they're often higher quality explanations. Sometimes the text editorials miss out important details or are simply unintelligible.