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

Idea: MikeMirzayanov

Tutorial
Solution

1624B - Make AP

Idea: DmitriyOwlet

Tutorial
Solution

1624C - Division by Two and Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1624D - Palindromes Coloring

Idea: DmitriyOwlet

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 (66)
| Write comment?
 » 13 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.
•  » » 13 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?
•  » » » » » » 12 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.
•  » » 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.
 » Has anyone done C with graph matchings like the tag mentioned, if yes, kindly share your code
•  » » enjoy 142236492
•  » » 8 months ago, # ^ | ← Rev. 3 →   ...
•  » » » 8 months ago, # ^ | ← Rev. 2 →   ...
 » 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
•  » » » 13 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!
•  » » » how we check that k palindrome of atleast length n can be made from the string?
 » 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
 » Can somebody please give proof of the problem C solution?
 » 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 you tell me why I get TLE https://codeforces.com/contest/1624/submission/160756528
 » Can someone explain why the greedy solution for problem C always works?
•  » » 13 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).
 » 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
 » 13 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.
 » 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
 » 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
•  » » » 13 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
•  » » » » » 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?
 » 13 months ago, # | ← Rev. 2 →   Why am I getting Memory Limit Exceeded in this ?: (problem E)
 » Can somebody please give proof or more detailed explain of the problem D solution?
•  » » 6 months ago, # ^ | ← Rev. 2 →   Whole problem statement story is unnecessary. What it is saying is: you can order characters into words that are pailindromes HOWEVER you want. You just need to follow rule to split word to k palindromes.
 » Can some one help me with this G-MinOr Tree?
 » 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. منور الدنيا يا صاحبي احلا مسا عليك
 » problem c. actually, There is no need for sorting array. my submission:163358165