Vladosiya's blog

By Vladosiya, history, 3 years ago, translation, In English

1624A - Plus One on the Subset

Idea: MikeMirzayanov

Tutorial
Solution

1624B - Make AP

Idea: senjougaharin

Tutorial
Solution

1624C - Division by Two and Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1624D - Palindromes Coloring

Idea: senjougaharin

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
  • +90
  • Vote: I do not like it

| Write comment?
»
3 years 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.

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

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

        Comparing two numbers is like comparing their bitreps in lexicographic order, higher bits take priority

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

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

            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.

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

            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.

  • »
    »
    3 years 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.

»
3 years 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

»
3 years 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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its okay, i did it in this way

    • »
      »
      »
      3 years 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!

»
3 years 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?

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

What does interacdive (problem f) mean?

»
3 years 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.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no need to sort the array.

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can somebody please give proof of the problem C solution?

»
3 years 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.net/contest/1624/submission/142329187

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 years 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Participant Jury Interaction
    • »
      »
      »
      3 years 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?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years 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.

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

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

  • »
    »
    3 years 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.

»
3 years 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)

»
3 years 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.

  • »
    »
    3 years 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).

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years 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

»
3 years 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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comment
    • »
      »
      »
      3 years 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

      • »
        »
        »
        »
        3 years 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.

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

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

»
3 years 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; });"

  • »
    »
    3 years 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

»
3 years 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.

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

Can someone please explain the approach of problem B !

  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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 ?

      • »
        »
        »
        »
        3 years 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

        • »
          »
          »
          »
          »
          3 years 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 !

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Show your code?

            • »
              »
              »
              »
              »
              »
              »
              3 years 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; }

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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

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

Amazing round! Any tips on how to get better?

»
3 years 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)

»
3 years 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?

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

    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.

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

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem G, why is it TLEing on test 42? Submission: 240490794

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

those who are getting WA on test case 2(test case 3648), try this test case

Input
Output
Reason