Vladosiya's blog

By Vladosiya, history, 6 days ago, translation, In English

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

Idea: Vladosiya

Tutorial
Solution

1624G - MinOr Tree

Idea: Vladosiya

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 days ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is submask? give some example please

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone done C with graph matchings like the tag mentioned, if yes, kindly share your code

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Would D be solveable if I binary searched on the answer and tried to construct k palindromes using the counts for each character?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its okay, i did it in this way

    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

»
6 days ago, # |
  Vote: I like it -14 Vote: I do not like it

omg i thought G is xor and got stucked... so any idea if we need to minimize the xor sum?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What does interacdive (problem f) mean?

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

A greedy solution for C works as well.

  1. Sort the input array.
  2. Iterate from backward and try forming the largest element not yet formed <= n with it.
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no need to sort the array.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah it's just for convenience of implementation. You could simply find the largest unvisited element and do the same.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
6 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Can somebody please give proof of the problem C solution?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
6 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

Submission : https://codeforces.cc/contest/1624/submission/142329187

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

After a long, long time, the editorial of this round was published!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Participant Jury Interaction
    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Did you find the code segment that was causing the error? Or is the answer wrong as a whole?

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

1624G — MinOr Tree https://codeforces.cc/contest/1624/submission/142429144 Why it is giving TLE?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why the greedy solution for problem C always works?

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
6 days ago, # |
  Vote: I like it +2 Vote: I do not like it

If you are looking for video solutions, you can find them Here (All Problems)

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem G. MinOr Tree https://codeforces.cc/contest/1624/submission/142442799 . Why this java solution is giving TLE?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am also stuck with this, java solution is giving tle whereas the same logic runs in cpp

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C Can anybody tell me where i'am doing wrong (Getting WA at 4628th token) 142461170

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comment
    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code is giving the right output..i:e YES.. can u please look it again

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For the tutorial written for problem C, 'This can be done if there are at least k characters left' how so?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

1624G — MinOr Tree https://codeforces.cc/contest/1624/submission/142528765 Why it is giving TLE?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone pls explain the sort fn problem c soloution "sort(a.begin(), a.end(), [] (int a, int b) { return a > b; });"

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this solution 142543258 for E is giving TLE where this one 142542275 that I came across not giving tle.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the approach of problem B !

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)/2

    now 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 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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)/c

      Now for example a = 10 ,b = 5 ,c = 30 , m values gets as -2 , 4 , 0 So what will be the answer , yes or no ?

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You showed that we can make it an A.P. by multiplying b by 4 so the will be yes

        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it ! , Thank you for explaining !

        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 !

          • »
            »
            »
            »
            »
            »
            4 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Show your code?

            • »
              »
              »
              »
              »
              »
              »
              4 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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; }

              • »
                »
                »
                »
                »
                »
                »
                »
                4 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Read the question again, it says m should be a positive INTEGER. you have to also check if m is an integer

»
5 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Amazing round! Any tips on how to get better?

»
5 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why am I getting Memory Limit Exceeded in this ?: (problem E)

»
4 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Was bit confused in B but it's clear now that's why removing comment.

»
42 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

sort(a.begin(), a.end(), [] (int a, int b) { return a > b; }); can someone help he undestand this code ?

  • »
    »
    42 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the thirs argument of sort function is not undestandable to me , is it some kind of inline funciton ?

    • »
      »
      »
      48 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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++

»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please give proof or more detailed explain of the problem D solution?

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one help me with this G-MinOr Tree?