MrPaul_TUser's blog

By MrPaul_TUser, history, 16 months ago, In English

1593A - Elections

Idea: MikeMirzayanov

Tutorial
Solution

1593B - Make it Divisible by 25

Idea: MikeMirzayanov

Tutorial
Solution

1593C - Save More Mice

Idea: ITMO student team

Tutorial
Solution

1593D1 - All are Same

Idea: MikeMirzayanov

Tutorial
Solution

1593D2 - Half of Same

Idea: MikeMirzayanov

Tutorial
Solution

1593E - Gardener and Tree

Idea: MikeMirzayanov

Tutorial
Solution

1593F - Red-Black Number

Idea: MikeMirzayanov

Tutorial
Solution

1593G - Changing Brackets

Idea: nastya_ka

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

| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to F pls

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

    F is a dynamic programming problem. You can use

    • taken amount

    • red digits count

    • the rem of red number mod a

    • the rem of black numer mod b

    to describe a state.The taken amount is phase of the dp. If you use enumeration method to find all states, the amount of states is $$$2^{40}$$$. But if you use dp to descibe all states, the amount of states is only $$$40^4$$$.

    Here is my code, written in Python3, but it get TLE. https://codeforces.com/contest/1593/submission/132439261

    Here is the same code rewritten by C++, it get AC. https://codeforces.com/contest/1593/submission/132442220

    I think the python code is more clearly than C++ code.

»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

d2 is really intresting.

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

It seems that in the tutorial for A, the answer should be max(0, max(b,c) + 1 — a) (as in the solution code), instead of min(0, max(b,c) + 1 — a).

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

We don't need that extra array to recover answer string. We can store masks in DP and recover the answer from that. Submission with comments : 131983798

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

Your dp is so messy.(F) -__-
Good problemset btw.

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

    Thank you very much, I was having a bug for a long time and I had no idea what it could be (눈‸눈)

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

      Feeling nice to hear that it helped.

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

For the E problem, will the standard graph bfs not work? I pushed all the leaves ( adjacency list size == 1 ) to a queue and assigned them a distance of 1 ( distance = number of times the operation has to be performed to cut off that node ). Then I performed a bfs assigning increasing distance. Answer is simply all the nodes whose distance is greater than k. This is failing though. Please if somebody could help me out. Thanks in advance

https://codeforces.com/contest/1593/submission/132264294

UPD : I changed the visited logic to an in-degree logic while preserving the bfs (AC : 132341078). Hope somebody finds this helpful. Thank you dedsec_29

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

    Once you mark a node visited, your code will never update its distance. But this is incorrect. You have to mark a node visited only when it becomes a leaf. If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree

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

      "If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree."

      Can you justify this with a counter-example please? I tried a lot of manual cases (Sample cases passed too), every time the node gets marked as visited, it is correctly assigned the distance from the closest leaf. Say the distance of the node is 3 from the closest leaf and k=3, so that node will be cut off at the end of all k operations, right? Or am I missing something? Thanks again.

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

        Take this test case for example:

        1
        8 2
        1 2
        2 3
        3 4
        4 5
        5 6
        6 7
        8 3

        Your output: 2
        Correct output: 3
        Your code deletes node 3 as you mark the distance 2 for it, but it will be deleted in the 3rd iteration, so d[3] should be 3, not 2

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

    Thanks man

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

    https://codeforces.com/contest/1593/submission/183828218 Can you please help me figure out what is problem with my code? Initially I am storing all the leaf nodes in the queue and then traversing whole graph by there parents.

»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • Can Someone help with the time complexity of this code: https://codeforces.com/contest/1593/submission/132395142 for problem D2.
  • I have used dp table for calculating the maximum gcd possible when I consider exactly n/2 numbers( because I have to make atleast half elements equal)
  • dp[i][cnt][last] stores set of GCDs that are possible after considering cnt number of elements upto ith position in the array with index of previous selected element as last.
  • It got submitted with 15ms runtime. According to me, the time complexity of this code is O(n^5 * (log(max(Ai)) + log(n))). I want to know whether I am wrong with the time complexity or test cases are not strong enough !
Reason behind asking this question
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone solve F using meet in the middle idea ?

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

    I'm trying to do it here but I need a way to combine the answer faster, I'm doing it in O(2^(n/2)*a*b) but it didn't pass.

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

My idea for E was to look at one diameter of the tree and take a middle point in that diameter. After that i root the tree in this middle point and after that it's easy but unfortunately i got memory limit exceeded. Is this idea works?

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

    yes this idea works, be careful on how you are finding middle point(s) when diameter is even or odd. code

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

CAN F QUESTION DE DONE USING MEET INT THE MIDDLE?

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

    Yes, but you need to write it with very low constant factor. You can check my submission here

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

deleted

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

    Because maximum difference is 1e6 — (-1e6) = 2 * 1e6; not 1e12

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

IN problem c,

The more easy idea is to track the cat's position. and apply greedy ideas i.e, save the mice first that are ahead of others.

Pseudo code:

  1. sort the coordinates array.

  2. assign catPos = 0, i = k, save = 0

  3. while catpos < a[i] and i >= 1:

  • incremented save count
  • increment cat pos by the distance b/w ith mice and hole.
  • decrement i

print the save count.

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

[submission:https://codeforces.com/contest/1593/submission/160406313]

why this code is giving runtime error on CF but is running on my local machine?

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

good contest

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

nice round

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

can problem c be solved using binary search, if it does can someone explain the logic and provide the code.

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

    Problem C using binary search

    #include <bits/stdc++.h>
    using namespace std;
    bool canSave(vector<int> &catPos,vector<int> &moves,int hole,int start){
        int cat=0;
        for(int i=start;i>=0;i--){
            if(catPos[i]<=cat){
                return false;
            } 
            cat+=moves[i];
        }
        return true;
    }
    int savedCats(vector<int> &catPos,vector<int> &moves,int hole){
        int low=0,high=catPos.size()-1,mid=0,ans=0;
        bool saved=false;
        while(low<=high){
            mid=low+(high-low)/2;
            saved=canSave(catPos,moves,hole,mid);
            // cout<<"from "<<mid<<" cat "<<saved<<"\n";
            if(saved){
                ans=mid;
                low=mid+1;
            }else{
                high=mid-1;
            }
        }
        return ans;
    }
    int main()
    {
        int t;cin>>t;
        while(t--){
            int n,k;
            cin>>n>>k;
            vector<int> catPos(k,0);
            vector<int> moves(k,0);
            for(int i=0;i<k;i++){
                cin>>catPos[i];
            }
            sort(catPos.begin(),catPos.end(),greater<int>());
            for(int i=0;i<k;i++){
                moves[i]=n-catPos[i];
            }
            int ans=savedCats(catPos,moves,n);
            cout<<ans+1<<"\n";
        }
        return 0;
    }
    
    
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All solutions of Mike Mirzayanov are so complex!!!