Dormi's blog

By Dormi, history, 7 months ago, In English

1534A - Colour the Flag

Author: crackersamdjam

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1534B - Histogram Ugliness

Author: Dormi

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1534C - Little Alawn's Puzzle

Author: Ninjaclasher

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534D - Lost Tree

Author: Plasmatic

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534E - Lost Array

Author: Plasmatic

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534F1 - Falling Sand (Easy Version)

Author: Dormi

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534F2 - Falling Sand (Hard Version)

Author: Dormi

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Solution

1534G - A New Beginning

Author: Aaeria

Tutorial
Solution

1534H - Lost Nodes

Author: Ninjaclasher

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

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

Thanks for quick editorial.

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

This is hard :(

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

B solution: should it be $$$a_i > a_{i-1}$$$?

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

Why I am getting WA on test case 4 in problem C. 119395523 . I used dfs and printed 2^(connected comp).

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

in question B editorial it is mentioned that

"observe that decreasing a column will never affect whether it is optimal to decrease any other column, so we can treat the operations as independent."

Why they are independent, Why it will never affect other columns?

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

    Initially consider just column i, all the columns in the range [1,i-2] and [i+2, N] won't be affected (since anything you do to column i doesn't change the outline of these columns).

    Since height of i column would be greater than the i-1 column (for any updation to height of i based on the algorithm), right outline of i-1 column won't change (left outline also doesn't change, by induction i.e. use i-1 as the central column). You could similarly argue for the i+1 column.

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

I tried a different approach for D, which I am not able to prove. So it would be great if someone can have a look and either prove or disprove it.

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

    This approach is same as given in tutorial. As you start from level 2, at this level you will get parent of all nodes at level3 so you would never query about nodes at level3 and go to level4 and will continue in similar fashion

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

      No, I may go to level 3 as well. I am querying those vertices whose parents I don't know currently. If there exists a sibling for a node, I will calculate the parent of sibling as well. Now, I will not query this sibling node as its parent is known and it may have children which will be in level 3. So when I reach level 3, I will query for the children.

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

    How you calculated the number of queries required for your implementation?

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

    You are basically querying on all the even level vertices. Which is a form of bipartite graph. But it might get hacked. Say the total number of nodes present on even levels is more than n/2. How are you tackling this? I queried on even/odd nodes whichever set is smaller.

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

    Yes I also used the Same Approach . The Correctness of this method can be proved by simply Saying that for any edge in the tree this approach will ask for max 1 node as a query (0 in case of that edge which connects it's parent and Sibling ) . Thus the maximum Number of Queries asked in the process will definitely <= ceil(n/2) and upper limit will be reached when no node has any sibling , straight structure like 1->2->3->4->5

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

    even i did it with the similar approach i tried on three four examples ans its working fine. This seems intuitive to me as for non leaf nodes we are querying only one time for finding parent and in this query only we also get info of one children also so we basically covered two nodes at least in one query it can be even more if node has siblings so that's why number of queries will always be less than ceil(n/2). Also if any particular depth has only single node than we don't require any query to find parent for all the nodes at depth+1 as there is only one option for parent at previous depth.

    my submission - https://codeforces.com/contest/1534/submission/119432261

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

    hey, we got a similar approach. I tried to prove it here.

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

Implementation forces.

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

Nice problemset. "Lost Problemset"

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

जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।

Nice questionset.

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

So interactive :D

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

Can anyone provide few intermediate level interactive problems.

I found one easy in google kickstart (guess the number). All the other interactive problems I could find seem to be too advanced.

Is there any resource where I could find many interactive problems to practice as a beginner?

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

119391919 Can someone please tell me why I'm getting TLE in problem C?

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

    You're creating array of size 400005 for every test case. There can be a lot of test cases so you're basically trying to create 4*10^9 integers which will take too long.

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

liked the beauty of problem D, great job!

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

For E, I think we can also do greedy:

First, if $$$n$$$ is odd and $$$k$$$ is even, we can never win.

Notice that two moves always results in even number of bits flipped. So if $$$n$$$ is odd and $$$k$$$ is odd, then we will have odd number of moves, so start by turning on some $$$k$$$.

Now we are left with turning on even number of $$$0$$$ bits.

Let's denote $$$action1$$$ as turning on some $$$k$$$ bits using one move, and $$$action2$$$ as using two moves to turn on $$$x$$$ bits, where $$$x$$$ is even, and $$$2\le x\le min(2k, 2(n-k))$$$.

If $$$action2$$$ is unavailable(there are no possible values for $$$x$$$), and our current number of zeros is not divided by $$$k$$$, we lose.

Otherwise, if $$$k$$$ is odd we can just do action2 greedily, and if $$$k$$$ is even, before the greedy, we might need to do a single $$$action1$$$ (this is easy to check).

Code: 119401441

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

Kinda different solution to E. I'm sad, tired, and hopelessly hardstuck, so this is the short ver

The answer is NO iff $$$n$$$ is odd and $$$k$$$ is even. The if part is true because we can't distinguish between any two arrays $$$a$$$ and $$$b$$$ such that for all $$$i$$$, $$$a_i \oplus b_i = 111111...$$$.

Let's show that it's possible otherwise. The case where $$$k$$$ divides $$$n$$$ is trivial.

Consider all other cases except for ($$$k$$$ is odd, $$$n$$$ is even, $$$2k$$$ > $$$n$$$). We can greedily form segments of length $$$k$$$ until there is an even number (let this number be $$$r$$$) of elements remaining such that $$$r < 2k$$$. It takes $$$2$$$ more queries to solve the problem. We can show that this is optimal via a parity condition.

In the case ($$$k$$$ is odd, $$$n$$$ is even, $$$2k$$$ > $$$n$$$), we can set $$$k = n - k$$$ and solve the problem as in the former case, except that we query the complement of things. Pretty sure this is provable (the problem becomes strictly harder if you're given the complement xor, and you can solve it in the optimal number of moves in the equivalent easier version), but my head is foggy :/

I think solving it this way is very impractical tho, the bfs solution should be the "correct" one to think of during contest

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

Can someone explain why my O(N^2) solution give TLE in problem D? My Submission

My Approach

I am not sure if the my approach itself is accurate, but still O(N^2) solution must not be giving TLE.?

Thanks.

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

Please, someone, explain 2nd problem, Thanks :|

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

    Basically, for a given array ugliness is sum of abs(arr[i]- arr[i+1]) (insert 0 at front and back of the array). We can perform an operation which is decreasing arr[i] to arr[i]-1 provided arr[i]>0. ugliness in increased by 1 on each operation
    We need to minimize the ugliness of the array by performing the operations >=0 times or 0<=i<=n.

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

Benq orz.

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

I really enjoyed the round, I think it was well balanced.

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

For D, is n/2 queries tight? (i.e., there isn't any other algorithm that can do it in fewer queries) If so, how to prove?

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

I wonder why so many contestants including me got WA on F1. And my solution is similar to toturial's (using strongly connected components) . That confuses me. (Ahh...I spend more than an hour during the contest on debugging my F1 code!!!)

Here is my submission

Can somebody provide some details to be careful on F1? Or some special test cases?

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

    Hi Dormi, What I have done is that I created a directed graph as mentioned and then choose a vertex with in-degree 0 and started DFS, and marked all reachable vertices as done, Then choose another vertex with in-degree zero and so on, My answer is the number of times I start DFS. Why would this solution give Wrong answer? Why do we need to find SCC instead of doing DFS on the fly?

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

      I start with 0 indegree vertices but try to visit all of them, here is my submission. Please help.

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

        Consider two rows in distance 2, each completly filled with sands.

        Both rows each build a circle of dependencies (an SCC), the above row triggers the below row, and there is no vertex with indegree 0.

        To see that the whole construct is triggered with only one operation we need to somehow see that the triggereing must start in the top row. That is, a SCC with indegree 0.

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

          Yes, but in this case, my code reports correctly because since there are no vertices with in_degree = 0, it tries to visit unvisited vertices starting from vertices with greater height.

          The case where my code will fail is when an SCC at a lower height triggers two or more SCC's at a height above it.

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

            Greater hight is not a good criteria, as seen in example 2. We can construct grids where we must not start from greatest height.

            Something like this:

            x....
            x..xx
            x....
            xxxx.
            
            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes for your example my code doesn't work. Thank you.

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

        You could use topological sort here, instead of going with the indegre==0 idea

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

          Are you suggesting that instead of shrining SCC into one node and then counting vertices with zero in degree, we can just do a topological sort and find the number of in-degree 0 vertices?

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

            We don't exactly need to find nodes with indegree==0 as a starting node. Just topological sort it and then start from reverse. This will make sure you are using the least number of nodes as a starting point.

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

is it possible to get different verdict in pretest and submission?

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

Can anyone please tell why i am getting wrong answer on pretest 2? 119361708

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

    There can be no 'R' or 'W'. Your code fails on test cases when all characters are '.'

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

      Now, the same code got accepted, does that mean the testcase with only '.' is not there ? Here it is 119409968

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

        Emmm, last time I use a 3*3 grid only has '.' on your code 119361708 , and it outputs wrong answer. But now your code 119409968 can output right answer.

        So it must have been changed something... (doge

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

          Thanks, i got it now. i forgot, i had changed a line, which handled the '.' case with default initializing with 'W'. i need to be more careful with such edge cases.

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

Please can anyone tell me what does "set" mean in "bipartite set" in problem D?

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

I could only pass the pretest 1 in problem problem A.....this is my .119393289 I would appreciate if someone could help to check it.

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

what are the Algorithms i need to learn so that i can consistently solve A and B problems Ps: newbie:)

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

    none. That's the good part.

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

    You don't need to learn many algorithms, A, B problems are mostly ad-hoc, just solve Div2 A, B, C problems from previous contests and you'll be good.

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

      Thankyou ☺️ [user:DontLookBack][user:RNR]

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

Why is getting wrong answer on this 119391694 because it gives correct answer on local compiler i simply do the 2^(connected components) ,please help thanks:)

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

In problem E does d, the maximum no. of queries also varies with n and k? I thought we just have to make it within 500 queries irrespective of n or k. T_T

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

Can someone help ? I overcomplicated the solution to problem A and got wrong answer . Can someone tell me why ? I used graph theory.

Your code here...
ll n , m;
vector<ll> dx = {-1 , 0 , 1 , 0};
vector<ll> dy = {0, -1 , 0 , 1};

bool dfs(ll i , ll j , vector<vector<char>> &arr ,vector<vector<ll>> &vis){
    vis[i][j] = 1;
    for(ll itr = 0 ; itr < 4 ; ++itr){
        ll X = i + dx[itr];
        ll Y = j + dy[itr];
        if(X >= 0 && Y >= 0 && X < n && Y < m){
            if(arr[i][j] == arr[X][Y]) return false;
            if(arr[i][j] == 'R'){
                arr[X][Y] = 'W';
            }else if(arr[i][j] == 'W'){
                arr[X][Y] = 'R';
            }
            if(!vis[X][Y] && !dfs(X , Y , arr , vis)){
                return false;
            }
        }
    }    
    return true;
}


int main(){
    ll t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        vector<vector<char>> arr(n ,vector<char> (m));
        ll cnt = 0;
        for(ll i = 0 ; i < n ; ++i){
            for(ll j = 0 ; j < m ; ++j){
                cin >> arr[i][j];
                if(arr[i][j] != '.'){
                    cnt++;
                }
            }
        }

        if(cnt == 0){
            ll flag = 1;
            for(ll i = 0 ; i < n ; ++i){
                if(flag){
                    arr[i][0] = 'R';
                }else{
                    arr[i][0] = 'W';
                }
                cout << arr[i][0];
                for(ll j = 1 ; j < m ; ++j){
                    if(arr[i][j-1] == 'R'){
                        arr[i][j] = 'W';
                    }else{
                        arr[i][j] = 'R';
                    }
                    cout << arr[i][j];
                }
                flag ^= 1;
                cout << endl;
            }
            continue;
        }

        bool fine = true;
        bool done = false;

        vector<vector<ll>> vis(n , vector<ll> (m , 0));

        for(ll i = 0 ; i < n ; ++i){
            for(ll j = 0 ; j < m ; ++j){
                if(arr[i][j] != '.'){
                    fine = dfs(i , j, arr , vis);
                    done = true;
                    break;
                }
            }
            if(done){
                break;
            }
        }
        if(!fine){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        for(ll i = 0 ; i < n; ++i){
            for(ll j = 0 ; j < m ; ++j){
                cout << arr[i][j];
            }
            cout << endl;
        }
    }
}
»
7 months ago, # |
  Vote: I like it +15 Vote: I do not like it

One of the best Editorial for Problem E. Lost Array, I could find on the net is this one by MagentaCobra, Solution for Lost Array (E).

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

In problem D, sample test case 2. How can we tell for sure after just one query? It's given the tree is

? 5 gives 2 2 1 1 0. So can the tree be not like this?

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

    Yes really confusing. It is just authors example, they can know the solution without even attempting:))

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

    Testcases in interactive problems doesn't make any sense. They are there just for helping understand interaction protocol, without giving hint to solution.

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

Update: Got the wrong case:

What's wrong in my code 119358197 ? got Wrong Answer test case 4. my logic was exactly same as editorial .

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

Did anyone solve problem C using maths, like a single formula or something?

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

    Try this 1 2 2 R..R It's correct but your code says no :)

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

      No my code showing me 1 2 2 R..R

      YES RW WR

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

        Change your input to Char str[a][b]; and take input as matrix with double loops And check this testcase too should print no 1 2 3 ..RR..

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

Can anyone explain intuition behind hint 4 for problem D

The min(number of black, number of white) nodes is ≤⌈n/2⌉.

why can't it be <=floor(n/2) symbol? any counter example? UPD: problem solved, the editorial is updated.

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

    number of black and white can obviously be same if n is even.

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

      Sorry for asking wrongly, I am confused with the ceil(n/2), why can't it be <= floor(n/2).

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

        It is =ceil(n/2) in case of equal parts

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

          It will be =floor(n/2) in case of almost equal parts. eg n=4 min(2,2)=2 , n=5 min(2,3)=2 <-(<=floor(5/2))

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

    This means there can be equal number of black and while nodes. in this case the equality holds.For example, consider the following tree.1---2---3---4 this has n/2=2 number of nodes of each color.

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

nice editorial!

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

In problem B why it is not optimal to reduce the height of a[i] a[i]>a[i+1] when i==0

consider case n=2 5 1 initally ans = 5+4+1

1 1 now ans = 4+1+1

or I missing something.

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

    It is optimal. You just reduced the ugliness score from 10 to 6 right?

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

      yeah, but why in the editorial this condition is not given if(a[0]>a[1]) a[0]=a[1]

      the condition for optimal ans given in the ediorial is only when (a[i]>a[i-1] and a[i]>a[i+1]) but what about the end points

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

        Yeah it should be a[i]>a[i-1] or a[i]>a[i+1].

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

    I figured it out. It turns out it's because I loop till the bottom of the table for every sand block I have. I found an optimization for this with storing the first block of sand below each block with DP.

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

      A possibly easier way than DP (and I used this in White Pawn from a recent Atcoder contest) was to store the values in a set, and use lower_bound / upper_bound depending on what you want. It's slower to run, being $$$O(\log n)$$$ rather than $$$O(1)$$$ after pre-calculation, but it's faster to implement, and that extra computation time is almost always ok.

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

        Can you please elaborate? Store which values

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

          In my solution, I had $$$top_j$$$ store the values of $$$i$$$ for which there was a block of sand in $$$grid_{i,j}$$$. So I can easily query the next block under $$$(i, j)$$$ with top[i].upper_bound(j) (upper_bound because lower_bound will give $$$i,j$$$)

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

            Oh, I got it. Thanks! But tbh for me DP was easier to implement XD But your solution is definitely useful in many other cases

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

The hints before the solutions are very helpful . I think every editorial should have hints .

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

I think my solution for D seems more creative/easy because you dont need any experience with standard/similar problems, so I am putting it here

So we will root the tree at 1 and evaluate parent for each node.

first we will ask for depths (i.e. distances from 1), and for all nodes with depth 1 we will set 1 as their parent

Now, let's iterate over all nodes in increasing order of depth.

Whenever we encounters a node (let's call it r) without a parent assigned we will make a query with r, and set it as a parent of all nodes with distance 1, except one which already had a parent, let's call it p. Now take r and other nodes which have a dis of 2 with r and same depth as r, set p as their parent.

Proof:

Let's ignore 1st query and node for simplicity

Note, for each node that we made a query with, we skipped at least 1 node (obviously its parent) 
above it...

also notice that each node is covered by at most 1 of its children (analyze the last operation).

So, chosen <= skipped   // ignoring 1st node/query

in the worst case chosen = skipped,
 total_nodes = chosen + skipped + 1 = odd number // added 1 for node 1
 chosen + 1 == ceil(total_nodes/2) // added 1 for 1st query to LHS

code

I only had a blurred picture of it in the contest :(

Please correct me if something was wrong, and also feel to ask.

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

I wasn't able to take this contest, but I just did a virtual and I have to say — These problems were brilliant! They were unique, easy to understand, and not too complicated to implement (even F1, if you just look at the solution, it seems complicated, but it's really not).

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

My solution to E was much more direct than using BFS. The first observation is that each query just gives you a linear equation (mod 2) containing $$$k$$$ of the variables. Then, in order to find the XOR-sum of everything, it's necessary and sufficient to make some queries such that a linear combination of them is the desired XOR-sum. In particular, because we're working mod 2, the coefficient of each equation is either $$$0$$$ or $$$1$$$, and we can just not query the 0's, so we need exactly a set of queries such that the total XOR is the XOR-sum. In other words, we need to query each variable an odd number of times.

Now, the problem is much simpler: first, consider a number of queries $$$d$$$, so that we will make exactly $$$d$$$ queries each with exactly $$$k$$$ distinct variables. Then, if we fix the frequencies of variables, the greedy strategy "always query the $$$k$$$ variables with the greatest remaining frequency" is guaranteed to work unless the max frequency is $$$> d$$$, in which case there is no solution. Thus, we want to minimize the max frequency while keeping all frequencies odd and having sum of $$$dk$$$; this is achieved by making the frequencies as similar as possible, either $$$1+2\lfloor (dk-n)/2/n \rfloor$$$ or $$$1+2\lceil (dk-n)/2/n \rceil$$$. In particular, $$$d$$$ is valid iff $$$dk \ge n$$$, $$$dk \equiv n \pmod{2}$$$, and $$$1 + 2 \lceil (dk-n)/2/n \rceil \le d$$$, so we can find the minimum $$$d$$$ with a simple linear search.

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

    I was thinking of something similar and got all the inequalities for necessary $$$d$$$. But then I got stuck at step of showing that the $$$d$$$ is sufficient (the greedy strategy you mentioned). Can you give some more insight on why it works and how did you think of that? Thanks!

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

      The intuition is just that having smaller groups is better than larger groups because small groups can always be split into separate queries, but large groups can get stuck, so you want to prioritize cleaning up the largest groups. The k=2 case is definitely quite well known: you can form pairs of distinct elements as long as there's no single majority element. You can prove this formally by inspecting the greedy algorithm, or you can use a max-flow-min-cut/Hall's marriage theorem argumrnt.

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

In question D I'm getting an error "wrong output format Unexpected end of file — int32 expected". I don't understand if I used wrong approach because my code works fine on small test cases and counter test cases. If someone could help me resolve it that would be a great help. Thank you. My code: 119541888

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

Okay I got a stupid question.

What does at most [n/2] operations means in problem D ? what does [n/2] in general ? Is it floor or ceil?

TIA

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

Problem B would have been even more interesting and difficult if height of bars could be increased as well. Which sadly how I misinterpreted it.

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

In problem G, $$$dp[x][y] = (\min{dp[a][b]} \forall y-(x-a) \leq b \leq y+(x-a)) + (\sum{\frac{|y-z|}{2}} \forall potatoes (x,z))$$$ all such b's aren't reachable, won't that create any problem? Also what should be our intial function, I think it should be like $$$f(0) = 0,$$$ else $$$\infty$$$. Somebody please help me out.

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

    Many times, you can analyze the version of the problem where positions are allowed to be reals rather than integers, and then prove they have the same result. This problem has that property, because all inflection points are integers, so you might as well only visit integer points.

    Your initial function is correct. It's actually enough to treat it as $$$f(x) = (n+1)|x|$$$.

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

      Thanks a lot!! I understood it now. Actually what I understood is :

      • The answer always occur at one of the given points in the final graph(we need not think that whether we have our calculated minimum achievable or not)

      • Whenever we expand our graph about the center, all the points in domain get their new values from the points which were in domain previously(here I want to say that they are not taking any junk value from the previous states which were not achievable). This can be seen from parity of points and the offset we have. Actually this was the main confusion for me.

      Basically at every transition all the points in domain are correct and we do not care about others, and in the end we will surely be having some point (which was given intially) on the global minimum line.

      Please correct me if I am wrong somewhere.

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

Its mysterious to me. Please point out what is wrong in this easy problem A-solution.

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

    This loop checks only positions with same parity, but should check all positions.

           for(int i=0 ; i<n ; i++){
                for(int j=0 ; j<m ; j++){
                    if((i+j)%2 == tmp && s[i][j] != '.' && s[i][j] != s[p][q])yes = false;
                }
            }
    
»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In F2 we need to mark the minimum number of nodes in a DAG such that a set of "special nodes" can be reached by at least one marked node.

Because any special node can be reached by a contiguous range of other nodes we can solve this problem efficiently in this case.

Is this problem NP-hard in a general graph?

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

For problem F2 to solve the last task like covering every special node via segments we can use easy dp that seems to work in O(size^2) but actually the sum of all segments` length is O(n). Here is my solution https://codeforces.com/contest/1534/submission/120320191

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

I did problem C using DSU 124814179. But I get a wrong answer on test case 2. Is my approach correct? What am I doing wrong?

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

can some one tell me what's wromg in my approach Problem C..i got WA at 3rd testcase. Link for my submission http://codeforces.com/contest/1534/submission/125680024.

let n=5; a[i]={1,2,3,4,5} b[i]={3,5,1,2,4}

I simply checked for pairs like a[i]=1,b[i]=3 and a[j]=3 b[j]=1, counted them and if some unpaired are left they form a another single cycle like a[i]=2 b[i]=5, a[i]=4 b[i]=2 , a[i]=5 b[i]=4. So number of ways we can generate another solved sequence is 2 ^(cnt +1).

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

For the Problem G,if offsetting all values in the left of the min point by −(j−i) and offsetting all values of the min point by (j−i) to get fj from fi,fi shuold be a convex function.but we need add fi to gi,how to prove that fi+gi is a convex function and can support the next operation?

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

    That is to say how to prove that we can get a convex function when we add a convex function onto another convex function.

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

      Ok,I know how to prove that now. Thanks.