By Vladosiya, history, 4 months ago, translation, 1624A - Plus One on the Subset

Idea: MikeMirzayanov

Tutorial
Solution

1624B - Make AP

Idea: SixtyWithoutExam

Tutorial
Solution

1624C - Division by Two and Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1624D - Palindromes Coloring

Idea: SixtyWithoutExam

Tutorial
Solution

1624E - Masha-forgetful

Idea: Aris

Tutorial
Solution

1624F - Interacdive Problem

Tutorial
Solution

1624G - MinOr Tree

Tutorial
Solution Tutorial of Codeforces Round #764 (Div. 3) Comments (86)
 » Amazing round! I can't believe I was stuck on problem D all the time with the exact idea that the tutorial uses, but didn't go through with it!
 » 4 months ago, # | ← Rev. 2 →   How is problem G only of 1900 difficulty? It's a really nice problem, but in my opinion it is way harder than problem F.
•  » » 4 months ago, # ^ | ← Rev. 3 →   More people solved G, difficulties are calculated dynamically from the number and ratings of the people who solved it in-contest.I think it's because G is a bit easier if you have a DSU implementation and have solved similar problems before (Kruskal's algorithm), while you have to be very careful when implementing F to ensure the modified binary search is correct, especially as it's harder to locally test interactive problems, generally speaking.Of course, there is some variation/subjectivity in which problems individuals may consider easier or harder.
•  » » » Spheniscine Can you explain why we start with the highest bit first rather than the lowest and then choose the next higher bit to check for it's feasibility in the final answer?
•  » » » » Comparing two numbers is like comparing their bitreps in lexicographic order, higher bits take priority
•  » » » » » Thanks for the reply, I understood the thing you said about the higher bit taking the priority. Since if one number has a bit ON and the some other has that very bit OFF than we don't really care about the bits on the right side. But I am not able to understand that why in this very particular problem we can't go from bit 0 to bit 30. Is it not consistent with the submasking procedure. Or is there something else? Am I missing some fundamental theory knowledge for submasking?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   Because there is a step where you keep only the edges with $k$-th bit $0$ if it won't disconnect the graph. Trying to do that the other way won't work, as then you'd give the lower bits priority over higher ones.
•  » » » » » » I'll try to explain why we cannot go from 0 to 30.Let's say you are going from 0 to 30. Since you need to minimise the ans you try to make the current bit 0. So, let's say you reach a point ??000 where the last 3 bits have been assigned greedily to minimise ans. But, now there can be a possibility that the answer will be 11000. Whereas there is also a possibility that if you choose ??011 when going from 0 to 30, you end up with 00011. So, greedy won't work if we go from 0 to 30.But, let's say that we go from 30 to 0. Now, if greedily, we take 000??, then it doesn't matter what next bits we get. By taking any option other than greedy will never give you better answer. if this is still not clear, let's do some calculations.We took 000?? which means that the first 3 bits are 0. This we took greedily. In worst case, next two digits will be 1. So, answer is 00011. Now, for first three bits, what other choices we had? 001??, 010??, 011??, 100??, 101??, 110??, 111??. Even if you replace all ? with 0 now, they will all be greater than 00011. Hence, greedy works. Note that 2^x > 2^(x-1) + 2^(x-2) + ... 2^1 + 2^0.
•  » » » » » » » Thanks for the detailed explanation. This was very helpful.
•  » » » » Sorry didn't mean to downvote
•  » » The problem G was much easier for those, who tried to solve it. It even required some observation or luck to skip E and F during the contest to go for it! I think that if the problem G was swapped with E, then it would have had even more successful submissions and even lower estimated difficulty.It is also not the first obvious and easily solvable DSU library problem on Codeforces. We already had a similar D. Social Network problem (rated as 1600) during the recent Deltix round.
•  » » » Consider a number A = 1001. A number B is bitwise-OR submask of A if B is 1000, 1001 or 0001, ie, B | A == A.
 » Has anyone done C with graph matchings like the tag mentioned, if yes, kindly share your code
•  » » enjoy 142236492
•  » » » Thank you :)
•  » » My solution with Dinics. Here you go: 142385396
 » Would D be solveable if I binary searched on the answer and tried to construct k palindromes using the counts for each character?
•  » » its okay, i did it in this way
•  » » » 4 months ago, # ^ | ← Rev. 2 →   nice, didn't solve in contest mostly b/c of time but partially b/c of the way the problem statement was written.Edit: Solved it!
 » omg i thought G is xor and got stucked... so any idea if we need to minimize the xor sum?
 » What does interacdive (problem f) mean?
•  » » https://codeforces.com/blog/entry/98759?#comment-876862(FYI, it's "interac-div-e", for the division operation)
 » A greedy solution for C works as well. Sort the input array. Iterate from backward and try forming the largest element not yet formed <= n with it.
•  » » There is no need to sort the array.
•  » » » yeah it's just for convenience of implementation. You could simply find the largest unvisited element and do the same.
•  » » » » For every a[i] (1<= i <=n),you can find largest number that is not yet formed and can be formed by a[i]. You no need to find largest unvisited element . 142229284
•  » » 4 months ago, # ^ | ← Rev. 2 →   I did this too. SubmissionKeep in mind the constraints for this problem are very small, and this solution still almost TLEd. For larger values of n, the editorial solution is better.
 » Can somebody please give proof of the problem C solution?
•  » » let me try to answer your question, as far as possible for me. to understand what I will say next, you must understand how the algorithm described above works. The first thing to notice is that we are sorting the array. now we will prove that this is the most optimal sample option. let's say that at the moment we are at position i. and according to the algorithms we will find the first x where used[x] = false. and we mark that now used[x] = true. why is it correct, you say? because at the moment this is the largest number that can be obtained from a[i]. if this x should have marked another element that is after a[i]. so no problem this same element can mark all currently available for a[i]. which does not affect the result. I hope the question is still relevant and I helped you
 » Complete overkill solution of C using maximum bipartite matching:Create a graph with $2n$ vertices. First $n$ of these vertices represent the permutation points and the next $n$ represent the array elements. Draw an edge to all permutation points reachable from all elements of the array ($O(n \log A)$ such edges). Now run maximum matching on this graph. Answer is yes if the number of edges in the matching is $n$ and no otherwise.
 » After a long, long time, the editorial of this round was published!
 » Can somebody help me with F please. I tried to bruteforce all the numbers in the range [1,n] in O(n). I added the same number to the array elements that I queried the judge. After receiving the query, I just marked all the numbers which didn't match the query value. I agree the approach isn't good because I ended up with more than one number in some cases. I still think it isn't totally wrong. Can somebody help me in either correcting my solution or proving that I cannot get an AC with this approach? 142283459 As always, I will be grateful. Thanks in advance.
•  » » » Thanks. Did you find the code segment that was causing the error? Or is the answer wrong as a whole?
 » 1624G — MinOr Tree https://codeforces.com/contest/1624/submission/142429144 Why it is giving TLE?
•  » » Your solution works in O(m * 100 * 49), which is quite slow for m <= 2e5. I don't know why you check so many bits (the numbers in the input have up to 30 bits), so changing that would probably make it barely pass, also your check function can be written in O(1) by changing the bit array to a single integer which has 1 bits on positions where edges should have 0. Now, an edge is valid if weight & bits == 0 (all necessary bits are off in the weight). Just remember to flip the bits in the end.
•  » » » ohhhkk, Done Thank you
 » Can someone explain why the greedy solution for problem C always works?
•  » » 4 months ago, # ^ | ← Rev. 2 →   Can u please describe what exactly the greedy solution that you are talking about?. I think it is forming larger numbers in permutation first then looking for smaller numbers.It is mainly because, if you are able to get a number i from x indices and number j from y indices where 1 <= i < j <= n and you get i in the sequence when you are continuously dividing j by 2. Then you can say that x >= y because every index that can produce j can also produce i and some extra indices can produce i but not j. If you use indexes that are able to produce i first then you might left out with indexes that can produce i but not j. then you may not produce j . So it is better to produce j first then i next.
•  » »
 » If you are looking for video solutions, you can find them Here (All Problems)
 » Pls can somebody tell why this solution 142368820 for problem E is not giving TLE and what is its correct time complexity. I think its time complexity is greater than O(n*m*m) (not sure). Any suggestion will be helpful. Thanks.
•  » » I think your code luckily passed testcases . The complexity of your code is o(m *n * m). You have to do some precomputation of storing all possible 2 length or 3 lengths sub-strings possible from given n strings but instead of that you are iterating all the n strings when ever you want to know whether t is possible to make or not , which is adding a factor of o(n*m) which is actually can be done in o(1).
•  » » » Its weird that it passed. Thanks for the help.
 » Problem G. MinOr Tree https://codeforces.com/contest/1624/submission/142442799 . Why this java solution is giving TLE?
•  » » i am also stuck with this, java solution is giving tle whereas the same logic runs in cpp
 » 142441246 Why this code is giving TLE on test 12?The time complexity should be O(nm),as well as the solution.It save d the string that the length is 2 or 3 in order to find them in the finding string.
 » I was thinking what if Problem G asked to find Maximum bitwise OR. I came up with an approach for it and want to know is it right or wrong.The approach is I will always try to make high bits as large as possible. I will iterate from MSB to LSB and for i'th bit position try to take the edge which has 1 at i'th position. If multiple edges satisfies this condition take the edge for which total OR value will be maximum.code
 » 4 months ago, # | ← Rev. 2 →   Problem C Can anybody tell me where i'am doing wrong (Getting WA at 4628th token) 142461170
•  » » Input1 7 4 7 3 6 4 7 5  Expected OutputYES  Your OutputNO  CommentWe already have $[3, 4, 5, 6, 7]$, we just need to create $[1, 2]$ from $[4, 7]$ which can obviously be done.
•  » » » My code is giving the right output..i:e YES.. can u please look it again
•  » » » » Sorry, my bad. Try this simple test case. 1 3 2 2 3 We already have $[2, 3]$ and we can convert $2$ to $1$. However, your code would produce NO.
•  » » » » » ohh..okay..thanks a lot man!!! :)
 » For the tutorial written for problem C, 'This can be done if there are at least k characters left' how so?
 » 1624G — MinOr Tree https://codeforces.com/contest/1624/submission/142528765 Why it is giving TLE?
 » can someone pls explain the sort fn problem c soloution "sort(a.begin(), a.end(), [] (int a, int b) { return a > b; });"
•  » » std::sort accepts a starting pointer, end pointer and a function according to which it will sort it. This function should take two inputs (for example a and b) and return true if a should come before b. [](int a, int b) {return a > b;} is short form for a function(also known as lambda). So basically all the statement does is sort a in descending order
 » For problem C, sorting the array is not required. Following the same procedure without sorting also will solve the problem. Here is my Accepted solution without sorting 142538067
 » Can anyone tell me why this solution 142543258 for E is giving TLE where this one 142542275 that I came across not giving tle.
 » Can someone please explain the approach of problem B !
•  » » We can either multiply a by m, multiply b by m or multiply c by m.Case 1: We multiply a by m since am, b and c are in A.P., b = (am + c)/2now do some algebra to find the value of m. If m is a positive integer, the answer is yes. if not, we need to consider the other cases. Now do a similiar process with the other 2 cases
•  » » » 4 months ago, # ^ | ← Rev. 2 →   Here ,according to your explanation of the case 1 , m will be = (2b — c)/a . Am I right ? And also if I do multiplication of m with each 3 element , I got case 1 : a*m , m = (2b — c)/a ;case 2 : b*m , m = (a + c)/2b;case 3 : c*m , m = (2b — a)/cNow for example a = 10 ,b = 5 ,c = 30 , m values gets as -2 , 4 , 0 So what will be the answer , yes or no ?
•  » » » » You showed that we can make it an A.P. by multiplying b by 4 so the will be yes
•  » » » » » Got it ! , Thank you for explaining !
•  » » » » » I checked whether the m is positive or not for all the given test cases but 3 test cases are giving YES as an answer ,instead of No !
•  » » » » » » Show your code?
• »
»
»
»
»
»
»

# include <bits/stdc++.h>

// #include using namespace std; typedef long long int lli;

int main(){ lli t,a,b,c;

cin>>t;

while(t-->0){
cin>> a >> b >> c;

string ans;

if(((2*b-c)/a) >=0 ){
ans = "yes";
}
else if(((a+c)/(2*b))>=0){
ans = "yes";
}
else if(((2*b-a)/c )>= 0){
ans = "yes";
}
else {
ans = "no";
}

cout<<ans<<"\n";

}

return 0; }

•  » » » » » » » » Read the question again, it says m should be a positive INTEGER. you have to also check if m is an integer
•  » » » » » » » » » i am agree with you
 » Amazing round! Any tips on how to get better?
 » 4 months ago, # | ← Rev. 2 →   Why am I getting Memory Limit Exceeded in this ?: (problem E)
 » 4 months ago, # | ← Rev. 2 →   Was bit confused in B but it's clear now that's why removing comment.
 » sort(a.begin(), a.end(), [] (int a, int b) { return a > b; }); can someone help he undestand this code ?
•  » » the thirs argument of sort function is not undestandable to me , is it some kind of inline funciton ?
•  » » » It is called a lambda expression which is simply an anonymous function it is used to compare the elements of the array being sorted just Search for Lambda expressions in c++
 » Can somebody please give proof or more detailed explain of the problem D solution?
•  » » It took me a long time to understand this problem as well. The coloring and swapping was messing with meYou can see my examples explaining the solution here:https://github.com/neshdev/competitive-prog/blob/main/div3_764/D.py
 » Can some one help me with this G-MinOr Tree?
 » b was pretty tricky
 » What if OR is XOR,then how to solve it?Anyone has some great ideas?
 » For Problem F, why is n-m given as a query and not m ? I am Unable to visualize the solution. can someone help ?
 » 4 months ago, # | ← Rev. 3 →   for problem C what I did is for every element of permutation from 1 to n what we do we store index in array which can be used to create the element of permutation for eg: t = 1 ||||| n = 4 |||||| a = 24 7 16 7for this example element -> list of array indices which can be used to generate this element using operation divide by 2 ||||||| 1 -> 1, 2, 3, 4 |||| 2 -> 3 ||||| 3 -> 1, 2, 4 ||||| 4 -> 3I think this can lead to the solution but I not able to figure it out how Please help just a hint would be a great help
 » I dont understand how can we use binary search in problem D
 » how do i upgrade my level in problem solving plz
•  » » Practice a lot, my friend. منور الدنيا يا صاحبي احلا مسا عليك