Vladosiya's blog

By Vladosiya, history, 9 months ago, In English

1927A - Make it White

Idea: MikeMirzayanov

Tutorial
Solution

1927B - Following the String

Idea: MikeMirzayanov

Tutorial
Solution

1927C - Choose the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927D - Find the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927E - Klever Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1927F - Microcycle

Idea: MikeMirzayanov

Tutorial
Solution

1927G - Paint Charges

Idea: MikeMirzayanov

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

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Nice contest. Thnx, Mike!

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

Good round!

»
9 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

The system testing is going on for last >4 hrs. Is there a way I can submit problems while system testing goes on for contests?

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

loved this round. the problems were so unique but system testing is not ending :'(

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

Good round. I done abcde. We will be waiting for new and interesting rounds from MikeMirzayanov. Thanks for fast editorial.

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

Problems were really nice. Thanks!

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

Please someone tell me, why did I get TLE on problem B with this approach??

int main() { // Code int t; cin >> t;

int total = 0;

while(t--)
{
    int n;
    cin >> n;

    vector<int> arr;

    int temp;

    for(int i = 0; i < n; i++)
    {
        cin >> temp;
        arr.push_back(temp);
    }

    int freq[26] = {0};

    string result = "";

    // trace traversal
    for(int i = 0; i < n; i++)
    {
        // letter frequency traversal 
        for(int j = 0; j < 26; j++)
        {
            if(arr[i] == freq[j])
            {
                freq[j]++; // add the frequecy
                result = result + char(97 + j);
                break;
            }
        }
    }
    cout << result << endl;
}
return 0;

}

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    i think problem in this:

    result = result + char(97 + j);

    you can use this instead:

    result += char(97 + j);

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    result = result + char(97 + j);

    This is a O(n^2) operation.
    use this instead

    result.push_back(char(97+j));

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

      ok thanks :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The time complexity of push_back is how much?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$O(1)$$$ for sure. string = basic_string, and basic_string is just like a extended vector.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but "result = result + char(97 + j)" will have a worse time complexity because it is equivalent to string splicing and it is $$$O(N)$$$.

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

    You're making things unnecessarily complicated. Take a look at my submission: 245110216

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    result = result + char(97 + j); This line gives tle because you are adding result in result this takes o(n^2) time that is why you are getting tle. to avoid this you can create a char array instead of the result string and add single elements to the array. Hope this helps.

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

    s is a std::string, then s+='a' is O(1) but s = s+'a' is O(s.size()).
    ac submission

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time complexity of str=str+str2 is O(2n) as it process both the string so it TLE's almost everytime on the large testcases .Use either str.push_back(str2) or str+=str2.

    Here is a relevant link regarding this :

    https://stackoverflow.com/questions/57132337/difference-between-string-s1-and-string-string-s1

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

fast editorial

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

Can someone tell when rating gets updated.

»
9 months ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

Here is how i explain C:

Same as Mike, i have:

Cnt0 = the number of x that only appear in A

Cnt1 = the number of x that only appear in B

(1<= x <= k )

(Remember, if a number satisfy Cnt1 condition -> both Cnt0 and Cnt1 is increased) Call Cnt0-k/2= y

So imagine that we have an answer array C of size k, then we put all numbers from A to C, and then what we do next is to replace each number in array C that belongs to A by numbers from B (we can choose to put a number in C from A/B if it appears in both arrays) -> Check if y <= Cnt1

When the answer if no? when there is x (1 <= x <= k ) that doesnt appear in both 2 arrays or y<0 (cant have enough k/2 numbers in C from A).

Sorry if my English is bad.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it like this.

    I marked the values till k as 1 if they occurred in a, and same in b as well using two arrays mark_a[10^6+1], mark_b[10^6+1].

    The iterate till k and do the following. mark the no of missing values in a and b.

    if both of them have a missing value i.e mark_a[i] == mark_b[i] == 0 then answer is no, else if any of them have more than k / 2 missing values then answer is no.

    if any of the above conditions aren't true then the answer is yes.

    Here is my submission id 245227353

    You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The last for loop is unnecessary btw you can remove it.

      The solution will still get accepted.

      Thanks For reading,

      sorry if my explanation was bad.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's my first idea, but i set the mark array limit to 2e5... and then i lost 20 mins more to figure out the idea in the tutorial

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

      You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1

      no you cannot create mark_a and mark_b of length k+1, why?
      let say n=2 and m=2 and k=2 you have array elements as {101,102} and {102, 103} then mark_a[k+1] is mark_a[3] where you only have position 0, 1, 2 and so for mark_b[3], now you don't have position 101 102 103 in your mark_a and mark_b where will you assign mark_a[101]=1 or mark_b[101]=1.

      why you declare mark_a and mark_b of size 10^6+1 is because that is the range of array elements 1<=a[i]<=10^6, so now for every possible element you have in array you have position where you will mark 1 if found in mark_a or mark_b.

      //(sorry for bad english)

      i am saying you can't create mark_a or mark_b of length k+1 as per your code which will possibly generate out of bounds error 245227353

      but you can create mark_a and mark_b of length k+1, if you check whether if a[i] or b[i] is <=k and then assign 1 as mark_a[a[i]]=1 or mark_b[b[i]]=1 246066103

»
9 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Another idea for problem F

We can get all the bridges in the graph using Tarjan.

If the edge is a bridge then it's impossible to make a cycle by this edge.

Sort edges by weight and the first edge that is not a bridge surely will make a cycle, then find it by dfs.

submission: https://mirror.codeforces.com/contest/1927/submission/245226535

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice one(

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yess, I also used the same logic

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

    Another idea is to count the number of encountered cycles on the DFS tree and figure out from those counts if an edge sits on some cycle.

    You can do that by tracking the enter time ins. If ins[child]<ins[x], then you know you encountered a cycle. You increase the number of cycles that start with C[child] and the total number of cycles found cycle_count and consider edge {x, child} for the minimum (as it sits on a cycle).

    When you exit the node that starts cycles, you decrease the cycle count cycle_count-=C[x] and C[x]=0.

    If the cycle_count when you exit the node is greater than the cycle count when you entered the node, then the edge from parent to that node is also on a cycle, so you can consider it for the minimum edge.

    Total complexity is $$$O(2\cdot m)$$$.

    https://mirror.codeforces.com/contest/1927/submission/245472637

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey! I am using the exact same approach but getting MLE. Can you please help. code

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Amazing Implementation Skills

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

245202834 why it is wa 2? I'm trying to use two pointers help me please problem C

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

    im not sure but I think that when in case of both you can just increase both variable by one and do nothing else and when you finish the loop just check if c1 and c2 both are less than or equal to k/2 and also check if the remaining space in both c1 and c2 is enough for the both variable

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      245205769 this is correct solution, but I uses maps. I want do the same things using two pointers^ but it as WA

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Another solution for D: Build 2 segment trees on array: for min and max values on range (vertices store min/max value and index). Then we can answer on query: if max(L, R).value == min(L, R).value then answer is -1 -1, else min(L, R).index max(L, R).index

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can be easily handled by building the tree with each node representing the position of the max/min value, not the value itself

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is exactly what I tried to do during the contest (as I've been studying segment trees and I'm in love with them lol)

      I couldn't figure out the implementation details during the contest, but afterwards, I tried it and got TLE. I'm using Python, so maybe that's it, but I would like some help and feedback on my implementation:

      TLE Submission

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry but i dont know much about python (cant even read the syntax). Here is my C++ code:https://mirror.codeforces.com/contest/1927/submission/245178309

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks! It's pretty much the same thing, with some optimizations (I really like how you avoid having two separate trees :). I'm sure the efficiency of C++ really helps as well.

          I'll work on mine, and see if I can optimize it further

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            remember that python is about 4-5x slower than C++ (It's not allowed for national OI in my country lol)

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh wow :_(

              But that's valid, yes. Even with PyPy and all the possible optimisations, it is still really slow.

              I've been trying to learn C++ recently, but I'm not comfortable enough yet to use it in a contest. It's one of my goals for this year though

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can use time.time() to check which parts of code takes much time. It can be input parsing or building tree, taking query or outputing.

        Sometimes python may fail you just because it's slower than c++ (for example, python list acessing is quite slower than c++ native array).

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, the value actually is not required.

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

    I used sparse tables instead, but the idea is the same

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's an overkill, but I did the same lol :P.

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Can anyone share the $$$n^2$$$ solution about G? Thanks a lot.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    My $$$O(n^2)$$$ submission: 245368999

    Let $$$dp[i][j]$$$ be the minimum operations to paint all cells from $$$1$$$ to $$$j$$$ by only using charges before $$$i$$$-th cell.

    Then for each cell $$$i$$$, we try to update the cells that can be reached from $$$i$$$. Make sure to contain the following case, that is, we use charge $$$i$$$ to paint the cells at left side of $$$i$$$, and use another charge (at $$$(i-a_1+1)$$$ ~ $$$(i-1)$$$) to paint the cells at right side of $$$i$$$. (See example testcase 8.)

    This is my first time trying to write a comment, and I'm not good at explaining things ><. See my code for more details.

    Hope y'all have a nice day :).

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow! are you anonymous LGM?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      by the way, i couldn't understand your code even though i looked at it for an hour. forgive me for my stuipidness. if you don't mind, could you explain this part in more detail? : if (j >= l+1 && j <= i-1){int r2 = min(j+v[j]-1, n);dp[i][r2] = min(dp[i][r2], dp[j-1][max(l-1, 0ll)]+2);} i believe this part is the part you mentioned "Make sure to contain the following case, that is, we use charge i to paint the cells at left side of i ," but i really can't understand it.

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

Great round with unique problems, thanks!

»
9 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Problem G

$$$O(N^{2})$$$ time complexity

UPDATED https://mirror.codeforces.com/contest/1927/submission/245921562

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

    uhh, can you explain it ?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 9   Vote: I like it +4 Vote: I do not like it

      dp[i][j] is the rightmost index we can achieve(filling all the prefix..) if we have first i elements of the array and we have used j of them. final answer is minimum j that dp[i][j] >= n in each step we can either pick the i th element and use it to the left either to the right .

      there is one more case when we pick 2 elements(A and B) .....A.....B.....

      and use A to the right and B to the left(other cases to use left and right is not optimal.. I can prove)

      KLEFT[i](you can see the implementation) pair shows the rightmost two k values, if we use the k th element to the left and it covers from i to k segment

      This is my $$$O(N^{3})$$$ solution which easily can be optimized to $$$O(N^{2})$$$ https://mirror.codeforces.com/contest/1927/submission/245217545

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it got WA?

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

D using Segment Tree too.

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

Could you please explain the dry run of the solution of E. Suppose, n=7, k=4 Why, the permutation 1,4,5,7,2,3 6 would not be valid? Why I have to take in this way: 1,8,3,5,2,7,4 ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The differents values of sum ok k elements from left to right are 17, 18, 19, 18, so the difference between minimal and maximun is 2 > 1 so It will not work. The apprroach to resolve E and minimize the answer is going to alternate maximum value and minimum, You can have one number i, and inscrease it each time, for odd indexes give number from left, and for even indexes give it from right.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      1.1+4+5+7=17 2.4+5+7+2=18 3.5+7+2+3=17 4.7+2+3+6=18 So the difference of sum of k value doesn't exceed more than 1.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry I took the case : 1,8,3,5,2,7,4

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

Another idea of problem G:

Because every cell must be colored, I considered greedy.
Enumerate each $$$i$$$ from $$$1$$$ to $$$n$$$, suppose that at this moment, all cells from $$$1$$$ to $$$i-1$$$ are colored.
Thinking greedily, it is definitely necessary to color as many cells as possible in $$$i+1$$$ to $$$n$$$ while coloring the cell $$$i$$$, suppose the number as $$$l$$$.
So preprocess the one with the highest number of stained cells out of all the painting schemes starting with $$$i$$$.
Then it is easy to dynamically maintain the $$$l$$$ for each $$$i$$$.

I am not sure if this algorithm is correct. It is even $$$O(N)$$$.

upd: this algorithm is probably wrong. In the last case of the sample, my implementation will use $$$a_3$$$ twice.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the algorithm won't work on many cases

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you give me an example?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1 1 1 1 1 1 | 0 0 0 0 0 0 0 0 0 0 0

        1-> means colored cell , 0 means not colored

        according to your algorithm in next step this happens

        1 1 1 1 1 1 | 1 1 1 1 1 1| 0 0 0 0 0

        then you start considering from first cell of 3rd part and it can happen they only paint themselves and they require total 5 steps to be painted

        but it could happen that among the unconsidered cells in 2nd part one could paint till the nth cell to the right direction

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I realised this, so I didn't skip the cells that were already coloured, instead considering the contribution of these cells to $$$l$$$.

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But $$$R$$$ could give you better answer right?

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              what is "R"? My $$$l$$$ is clearly defined in the algorithm description.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                why don't you just implement to check whether it really works?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it won't improve the time complexity

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

I got TLE ON problem D with binary search any one have an idea why ? https://mirror.codeforces.com/contest/1927/submission/245354533

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

Thank you for the contest. I finally reached expert.

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

Interesting pset. Thanks!

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

hey , the contest counted as unrated for me and I have solved a problem ?????

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

Can someone explain me why the author’s solution for problem B is not of complexity O(N^2)? I would assume doing s += chr(97 + j) to be of O(N) since strings are immutable and don’t have append in amortized O(1) like lists do

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no its o(1) search on the internet strings are mutable you can append at the back but if you want to append at the beginning then it will be o(n)

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

      @SuperMo I don't understand your answer, strings aren't mutable in Python and the author's solution is in Python

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

Is it possible to detect whether an edge belongs to a cycle by just DFS in linear time?

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

Thanks for the tutorial. I was said that G can be resolved in O(n^2) can someone say me how?

»
9 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Can someone explain G in simple terms

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

can someone please explain the editorial of $$$F$$$ in details?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it
    1. First part: We should find minimal weight edge (u->v) that completes cycle.
    2. Second part: We should find the cycle including edge u->v.
    Detail on F

    My submission with some comments: 245285224

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

Anyone resolved the problem D with Segment Tree?

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

Can anyone tell me why is this giving wrong answer (for problem F). 245356240

My idea here is, find the 2 nodes with minimum edge weight(say n1 & n2) and then do dfs from one of the node(n1) untill you reach another node(n2). In this way you will end up finding a cycle.

What is wrong in this??

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

    There may not always exist a simple cycle including the minimum edge.
    Consider this:
    1
    6 7
    1 3 2
    1 2 4
    2 3 3
    3 4 1
    4 5 5
    4 6 6
    5 6 7
    The lightest edge is "3 4 1". However, no cycle includes it.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain Problem E in an easier way? I thought of switch alternately between largest evens and largest odds but that doesn't seem to work. UPD: I solved it. Used the intuition to increase the values at even indices and decrease at odd indices.

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

Excellent contest.

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

Is a very nice competition.The question is quite thought-provoking.I like it.

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

Can somebody please look into this submission of b and tell why I am getting TLE? Thank you. https://mirror.codeforces.com/contest/1927/submission/245142912

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$\mathcal{O}(n^2)$$$ too bad for B

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

      Thanks for the reply, I actually found out about the error(it was in my declaration of vector v); The complexity is not O(n^2), it has nested loops but it is accessing the indexes only once;

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

I am getting a memory limit exceeded error on test case 27 in code 245453024

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem F, can anyone tell me how to solve it if it also asks to minimize the number of vertices in the found cycle? Thanks.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is unsolvable within the problem constraints, as if you give the same weight to all edges, the problem turns into figuring out the shortest cycle in the graph .This is a well known problem and the fastest solution for it is $$$O(nm)$$$.

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

waiting for a rollback :(

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

Anyone knows how to solve DFS problems in Python? I seem to encounter runtime errors (I assume it's segmentation fault).

For problem F, I found an $$$O(m)$$$ algorithm. 1 DFS to find the minimum edge on a cycle and 1 DFS to get that cycle.

I do sys.setrecursionlimit(10**6) but it will not pass in Python. The same algorithm in C++ passes, but I assume if recursion gets deep enough, even C++ will not be able to do it.

Is it the case that for $$$n > 10^5$$$ I should not use DFS? I'm not sure if there's a pattern to iterative DFS (stackless) but I find it a bit hard to shuffle the moments when I'm leaving the node and which metadata to keep.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a Python user, I have some advice for you. Recursive functions can be inefficient in Python, so it's best to avoid using them whenever possible. If you need to implement depth-first search (DFS), consider using a stack instead of recursion. Alternatively, you can explore other algorithms. For example, in this problem, you could use Union-Find (Disjoint Set Union, DSU) to find the minimum edge and Breadth-First Search (BFS) to detect cycles.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the suggestion. The DFS works fine with CPython 3.10+ (not available on codeforces). I guess if I used union-find I'd have to write an iterative find, right, a recursive one can also break?

      def find(x):
          while x!=P[x]:
              P[x] = x = P[P[x]]
      

      This change in Python made the DFS work: https://docs.python.org/3/whatsnew/3.11.html#inlined-python-function-calls

      Is there an example of a correct way to think about DFS+stack. I think I would have to be careful to not push a node multiple times. If I need to do something when exiting the node (when all of the children are completely processed), then I need to not exit it twice. I also cannot pop immediately the node of the stack.

      If graph is not a tree, then I have to keep track of which nodes are pushed to the stack and not push them again. But I also have to keep track of which nodes I visited.

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 6   Vote: I like it 0 Vote: I do not like it
        1. To impliment path compression of union-find, recursion is enough. Pay attention to the depth of recursions. the depth of the union-find tree is small enough if you perform path compression each time you unite two elements. However, considering dfs on a linear graph, the depth is too large. It causes no problem if the depth is small (like $\le 10^3). In fact, I could get AC with recursive union-find even in Python3 (not PyPy).

        2. Regarding the way of rewriting DFS as DFS+stack, I'll show you two solutions to the problem:

        The dfs part of the cycle construction only differs, but they have the same result. (But rewriting is hard for me at least, I used bfs during the contest.)

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Looking at your stack solution, if you want to support extra processing on node exit (for example, let's say you're calculating number of children), You would have to also keep track if you exited a node already (not to overcount children). I guess I'm on the right path there, but the +/- trick is useful.

          I tried the stack solution for Problem F (with bfs for cycle):

          https://mirror.codeforces.com/contest/1927/submission/245556453

          But it says it takes too much memory.

          Thanks again, I guess it's just memory heavy.

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

I am trying to solve 1927D - Найди различные! using MO's algorithm. But, getting TLE. plz help me!!!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you don't need mo's algo for that. use monotonic stack instead

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

Does anyone know if there are any traps in Test 19 of Problem F? It seems that the sorting of edges requires O(mlogm), and the DFS to find a path requires O(n), but I keep getting TLE. Or am I just too silly to see some stupid bugs 245508630? I would really appreciate some advice!

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

    Found the mistakes. No problem now!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I mistakenly declared an adjacency matrix (n*n elements) instead of an adjacency list (n*0 elements), and therefore got an TLE. I am not familiar with Java, so I'm not sure whether you stumbled upon the same mistake. It seems that Test 19 may have a large n, so maybe you can check whether you declared the graph correctly or made some mistakes that give you an O(n^2) complexity.-

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

My Submission

1927D - Найди различные! 3 test cases have passed completely, 4 test case it is giving me wrong answer. Any suggestion how to fix that?

»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I've recently gained an AC verdict on problem G, and I've decided to share my O($$$n^2$$$) solution. The reason for this is that I found the other explanations (including the editorial) not as deep as I would have liked them to be. So here it goes:

Let $$$dp[i][j]$$$ be the minimum number of charges to use in order to paint all cells up until at least index $$$j$$$, with the restriction that we may only use charges up until index $$$i$$$ (both are inclusive).

As always in DP, let's assume the worst initially, and gradually improve on them later on, so set all values to $$$+\infty$$$. To paint all cells until index 0 ($$$j=0$$$), we don't need to use any charges, so let all $$$dp[i][0]=0$$$.

We will use two loops to fill our DP table: the outer loop will gradually allow the use of more and more charges, while in the inner loop we'll try to paint more and more cells using only the allowed charges, but at the same time, also trying to use the least possible of them.

In each iteration of the outer loop, we're allowing the use of 1 more charge compared to the previous iteration. So the natural thing to do is to try to improve on the previous results. For this, we'll see what we can do with the recently allowed charge at index $$$i$$$. We could either not use this charge at all, use it to the left, or use it to the right.

Not using this charge means $$$dp[i][j]=dp[i-1][j]$$$, using this charge to the left means $$$dp[i][j]=dp[i-1][i-A[i]]+1$$$ and using this charge to the right means $$$dp[i][i+A[i]-1]=dp[i-1][i-1]+1$$$. Don't forget to add the boundaries 0 and N, of course a few of these indices may exceed them! Naturally, it's possible for any of these subproblems that we've already found a more optimal solution, in these cases don't actually set them to these candidate values. Also, the case when we use the charge at index $$$i$$$ to the left isn't valid when $$$j > i$$$. Notice that when we use $$$i$$$ to the right, it has a constant $$$j$$$ value, so we don't need to put that into the inner loop. Also, because of the fact that we've only updated our DP table at edge cases of the possibilities the recently allowed charge offers, it's possible that we have a higher value at a lower $$$j$$$, so let's solve this issue using a loop after the first inner loop that fixes these values. Note that this doesn't increase our O($$$n^2$$$) time complexity.

So why does this work? Because we only use lower $$$i$$$s to compute the optimal solution for higher $$$i$$$s, and these lower $$$i$$$s are guaranteed to already be solved. Why is that? Because we never set a new value for a lower $$$i$$$.

Except I lied to you (I'm sorry), this does NOT work. We can see this solution failing for test case 11 in the example input. There is 1 more case to consider. That is, when we use 2 charges at indices $$$i$$$ and $$$j$$$ such that $$$j<i<j+A[j]$$$ and $$$i-A[i]+1<j$$$. In this case, using charge $$$i$$$ to the left and charge $$$j$$$ to the right may give us the optimal solution, but our algorithm skips these cases. The proof is left as an exercise for the reader. We can solve this by saying $$$dp[i][j+A[j]-1]=dp[j-1][i-A[i]]+2$$$. We aren't setting a lower $$$i$$$ here either, nor are we reading a higher $$$i$$$ solution, since $$$j-1<i$$$ (from the case description). So these requirements are still met.

And with that, we've solved the problem! I hope that this comment was helpful for anyone who wasn't able to come up with a solution for this problem on his/her own. Thanks for reading!

My submission for reference: 245501934

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

A

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

Problem-D can easily be solved by using next greater and next smaller element.

Claim : If in [l,r] we don't have all same elements then we could just pick the lth element and find its next strictly greater element or smaller as well . If that thing exists and is within r , then answer exists otherwise NOT .

TC : O(n) for precomputation and O(1) per query.

Hope it helps.

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

So I want to wonder that why the problem C couldn't accept this code?

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=2e5+5;
int t,n,m,k,a[N],b[N],ta[N],tb[N];
bool solve(){
	n=read(),m=read(),k=read();
	for (int i=1;i<=n;i++){
		a[i]=read();
		if (a[i]<=k) ta[a[i]]++;
	}
	for (int i=1;i<=m;i++){
		b[i]=read();
		if (b[i]<=k) tb[b[i]]++;	
	}
	int ca=0,cb=0;
	for (int i=1;i<=k;i++){
		if (ta[i]>0&&tb[i]<=0) ca++;
		else if (ta[i]<=0&&tb[i]>0) cb++;
		else if (ta[i]<=0&&tb[i]<=0) return 0;
	}
	if (ca>k/2||cb>k/2) return 0;
	return 1;
}
signed main(){
	t=read();
	while (t--){
		if (solve()) puts("YES");
		else puts("NO");
		for (int i=1;i<=k;i++) ta[i]=tb[i]=0;
	}
	return 0;
}
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    k can be as large as 4e5, and ai and bi can be as large as 1e6, so the length of your ta ans tb is too short. You should set N to 1e6+5.

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

F can be solvable using bridges, find the smallest weight edge (u,v) which is not a bridge ,it will be the answer, and for simplicity the required path will be largest path between u,v (can be found using dfs).

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

B.following the string problem is getting tle can anyone get it in python

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Anyone can tell me how can i optimize this code of D problem. It's showing MLE which is obvious but then how alternatively I can solve it with same approach?


def bs(s,e,a,dp): if(s==e): dp[s][e]=[False,s,s] return(False,s,s) if(s+1==e): dp[s][e]=[a[s]!=a[e],s,e] return(a[s]!=a[e],s,e) if(dp[s][e]!=-1): return(dp[s][e]) else: mid=(s+e)//2 x1,y1,z1=bs(s,mid-1,a,dp) x2,y2,z2=bs(mid,e,a,dp) if(x1 or x2): if(x1): dp[s][e]=[True,y1,z1] return([True,y1,z1]) else: dp[s][e]=[True,y2,z2] return([True,y2,z2]) else: if(a[y1]!=a[y2]): dp[s][e]=[True,y1,y2] return([True,y1,y2]) elif(a[y1]!=a[z2]): dp[s][e]=[True,y1,z2] return([True,y1,z2]) elif(a[y2]!=a[z1]): dp[s][e]=[True,y2,z1] return([True,y2,z1]) elif(a[y2]!=a[y1]): dp[s][e]=[True,y2,y1] return([True,y2,y1]) else: dp[s][e]=[False,s,e] return([False,s,e]) for _ in range(int(input())): n=int(input()) a=list(map(int,input().strip().split())) q=int(input()) dp=[] for i in range(n): dp.append([]) for j in range(n): dp[i].append(-1) for i in range(q): l,r=map(int,input().strip().split()) if(a[l-1]!=a[r-1]): print(l,r) else: s,e=l-1,r-1 ans=bs(s,e,a,dp) if(not ans[0]): print(-1,-1) else: ab=ans[1]+1 cd=ans[2]+1 print(min(ab,cd),max(ab,cd))

Thanks in advance !!

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

Can someone please help me find the test case on which my code is failing.
It is failing test case 6 of problem G. code

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

Can anyone explain me the second paragraph of the solution of Problem D?

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

Can someone please explain to me why solution in java 245738199 is giving TLE whereas same solution in c++ (245745549) works

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

Hi all,

I read the tutorial and got accepted on problem F, but I still have one question: What if we just choose the edge with the minimum weight and then find any cycle which contains that edge. Isn't that simpler? Do we still have to use DSU and stuff?

Thanks in advance.

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

Thanks for Python solutions besides the great contest!

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

someone pls explain the solution to G in simple words

difficult to get around for me

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

Can anyone look into my submission for F? It's MLE in TC 7.

https://mirror.codeforces.com/contest/1927/submission/246026044

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

I am trying for the Problem G seems like I am stuck for this test case 1 1 4 1 3 2

t = int(input())
for i in range(t):
    n = int(input())
    lst = input().split()
    for j in range(n):
        lst[j] = int(lst[j])
    dic = {}
    def f(i, last):
        if(i>=len(lst)):
            if(last!=-1):
                return float("inf")
            else:
                return 0
        else:
            if((i, last) in dic):
                return dic[(i, last)]
            notblast = float("inf")
            blastleft = float("inf")
            blastright = float("inf")
            if(last!=-1):
                if(i-lst[i]+1<=last):
                    blastleft = 1 + f(i+1, -1)
                flag = False
                for j in range(i, min(i+lst[i]+1, len(lst))):
                    if(j-lst[j]+1<=last):
                        flag = True
                        break
                if(flag):
                    blastright = 2 + f(i+lst[i], -1)
                notblast = f(i+1, last)
            else:
                blastright = 1+f(i+lst[i], -1)
                notblast= f(i+1, i)
                blastleft = 1+f(i+1, -1)
            dic[(i, last)] = min(notblast, min(blastleft, blastright))
            return dic[(i, last)]
    print("Ans", f(0, -1))

Any Ideas why this gives the output as 2 the correct output is 3 though

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

alternate solution for F first remove all the bridges from the graph now every edge in graph has atleast one cycle so choose the one which has minimum weight and and get the cycle

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

I tried using binary search to find l, r for problem D.

Approach -> - storing start and end indices for all intervals for which values of array are equal. - then for each query using upper bound to check if given interval exists inside any interval with all equal values to return -1, -1 otherwise returning the appropriate indices.

Here is the code:-

My Code

To me issue seems to be where i am creating start_indices and end_indices vectors. If anyone can help it would be great. Thanks.

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

problem E different solution with explanation https://mirror.codeforces.com/contest/1927/submission/248029334

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

My Approach for problem D using the Binary Search and storing the diff points of array earlier in a separate vector , it might be a childish solution but I liked my approach because its easy to understand.

Code:Have a look

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

مش فاهم حاجه يا مايك منك لله

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Unable to understand how problem D will be solved.Can anyone give me a hint