Codeforces Contest 944 Solutions | Let's upsolve at least one | Competitive Programming
Vložit
- čas přidán 22. 05. 2024
- Like, Comment and Subscribe to encourage me to make more educational content.
0:00 Introduction
0:17 Problem A
0:45 Problem B
2:25 Problem C
5:00 Problem D
8:12 Problem E
13:50 Problem F
20:07 Problem G
25:40 Problem H
Mouse I use - shorturl.at/hloAX
Keyboard I use - shorturl.at/elFHX
Microphone I use - shorturl.at/hpT13
Thank you for sharing these so quickly Abhishek, I really like the way you deconstruct problems into simple explanations.
Thanks sir! Will watch tomorrow in local while traveling to college...
I think there is a small correction in explanation of problem E. In the example that you took you multiplied distance with distance instead of time:
explained equation: d * (a[i] - a[i-1) / (b[i] - b[i - 1])
correct equation: d * (b[i] - b[i - 1])/(a[i] - a[i - 1])
Oh Yes, you're right. That's a legit typo.
Thank you vaia💜
Amazing as always!
Can you suggest some resources for bit manipulation. I always feel very underconfident while solving them.
This should be useful cp-algorithms.com/algebra/bit-manipulation.html
For problem 'F'
Let's say we are calculating for x = 6
and i = 6
in that case cnt = 0
here we didn't count any extra points,
then why would we subtract - 1 from the count
You're right but because of what this problem is specifically asking we don't have to worry about these edge cases. They get offsetted by itself. But you can look at this new submission I made - Here I updated it to do make sense according to how you're thinking. codeforces.com/contest/1971/submission/260660321
in problem F we are multiplying by 4 for all the points but why are we not checking if any of our points lie on x or y axis bcz then we should multiply by 2 only
You're right but because of what this problem is specifically asking we don't have to worry about these edge cases. They get offsetted by itself. But you can look at this new submission I made - Here I updated it to do make sense according to how you're thinking. codeforces.com/contest/1971/submission/260660321
In the problem E suppose i declare both the array inside Int main then i get some random output why ??
rest mine logic was same , also i have matched from your submission
random output on cf only in my code editor it gives ouput according to the test case only
#include
using namespace std;
// vector A;
// vector B;
long long A[300010];
long long B[300010];
int main() {
long long tt;
cin >> tt;
while (tt--) {
long long n, k, q;
cin >> n >> k >> q;
for (long long i = 0; i < k; i++) {
cin >> A[i];
}
for (long long i = 0; i < k; i++) {
cin >> B[i];
}
while (q--) {
long long d;
cin >> d;
int idx = lower_bound(A, A+k, d) - A;
long long time =0;
if (A[idx] == d) {
cout
this was my code suppose i declare int main the it give me wrong output on cf
also i have tried it using vector i have not gone the correct output on cf
then how can i replace array with vector
ThankYou
Bhaiya I am not getting this in Problem F
lets say x is 0. then for that x we calculated the max y possible. But this specific x and y combination will contribute in both quadrants. Then how come multiplying it by 4 gives the correct answer
You're right but because of what this problem is specifically asking we don't have to worry about these edge cases. They get offsetted by itself. But you can look at this new submission I made - Here I updated it to do make sense according to how you're thinking. codeforces.com/contest/1971/submission/260660321
@@abhishekcode42 Got it thnxx bhaiya. Thankyou for taking out time from your busy schedule and clearing my doubt
in problem what was the apprroach for optimal solution, it was not clearly understood
Which problem
For Problem C :
Both points of the second arc has to be on the same side of the first arc
If on the same side, then no intersection. One on one side and other on the other side needed for intersection.
Problem E for way more easier than D ,I wasted a lot of time in problem D finding the edges cases
I did binary search,,,,but ended in tle on 7th case ..... don't know why..... because at best, you have to use BS.....
It took me more time to solve E though. I feel problem G was easy...I wasted my time understanding F
@@ce063_gautamlathiya5 I also used binary also on array a , got my solution accepted, but after the contest my solution was hacked 😢😢
i do not get it why cnt(10)+cnt(01)-1 in problem d
Let's go step by step.
Do you get why cnt(10) is added?
In problem 2, I tried to store all the chars in map and if map.size was 1 it was impossible or else it would be possible so I did print the last half and then first half of string which was giving me wrong ...I didn't get why ?
I guess if the string can be converted into some kind of palindrome
If the string had same halves, it would fail like "abcabc", you could simply swap any two distinct characters and it would work.
Yes, simplest example you will issue with is "abab"
I tried to reverse the string if all characters are not same then I got wrong answer but it’s also not possible when string is palindrome. But you explain it very easy way thank you
If string length is one print no
Else
//I shifted every chars by one index
abc --> bca
If they are equal print no else print yes and the new string
int lastElementLessThanD(vector arr, int d) {
auto it = std::lower_bound(arr.begin(), arr.end(), d);
if (it == arr.begin()) {
// If lower_bound returns the beginning of the array,
// it means all elements are greater than or equal to d.
return -1; // Indicating no such index found
} else {
// Return the index of the last element less than d
return std::distance(arr.begin(), --it);
}
}
int32_t main() {
// your code goes here
jaldi_kar_kal_panvel_nikalna_hein
int t = 1;
cin >> t;
while(t--){
int n, k, q;
cin >> n >> k >> q;
vi a(k);
scan(a,k);
vi b(k);
scan(b,k);
while(q--){
int d;
cin >> d;
if(d
Paste copy to pastebin or ideone and share link