Vladosiya's blog

By Vladosiya, history, 2 weeks ago, translation, In English

1675A - Food for Animals

Idea: MikeMirzayanov

Tutorial
Solution

1675B - Make It Increasing

Idea: MikeMirzayanov

Tutorial
Solution

1675C - Detective Task

Idea: Gol_D

Tutorial
Solution

1675D - Vertical Paths

Idea: MikeMirzayanov

Tutorial
Solution

1675E - Replace With the Previous, Minimize

Idea: myav

Tutorial
Solution

1675F - Vlad and Unfinished Business

Idea: Vladosiya

Tutorial
Solution

1675G - Sorting Pancakes

Idea: Vladosiya

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

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

With respect to the F problem, another (maybe simpler?) explanation:

  1. hang the tree from x (or y, it's equivalent)

  2. iteratively remove all leaves that are not in a or [x, y], we'll end up with only nodes that we'll visit

  3. all edges from the resulting graph need to be traversed twice (back and forth), except the ones connecting x to y

  4. if the graph after step 2 has n edges, the solution is 2 * (n — 1) — depth[y]

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

    Same as what I did. Euler tour of the deleted tree is a good way of thinking about it.

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

    Can you please explain why answer can't be 2*(no of edges) — depth[y].

    Link to My submission : Link

    Sorry If I misunderstood your approach

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

    I used this approach but iam getting wa in second test case. I tried several test cases on my own but i cant find whats wrong. See my sub 156219182

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

      Failing testcase: Ticket 6716

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

        Thank you . I fixed the problem , I was using the wrong data structure, a stack instead of a queue.

        In fact , I come with a new approach and solved the problem twice. The main observation : if a node x has a children that is in A , then x is in A. Then apply recursion.

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

In case someone is interested, I made video Solutions for D-F

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

It feels like C could be made easier like this 156054809

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

    I can provide an explanation for your implementation: Statement C: According to the question, the thieves are independent That means if you say that a particular person is a thief then you should be able to prove that all the other people are not thieves.

    For example, you have a sequence of 0's, 1's and ?'s. You should consider only the last person who said 1. Because, if we take him as a thief i.e; even though the picture is not present, he said that the picture is there => he is a liar => he is a thief. If there is another 1 after that one that leads to contradiction according to statement C. You can have any ?'s after the last 1. Because they can be considered thieves individually. When we encounter the first 0 after the last 1 (Why?). Because if we take 1 as a liar then obviously 0 is a truth-teller according to statement C. If the last 1 person is not a liar then obviously first 0 person after ?'s can be a liar => thief

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

For a top down traversal (2 traversals required) approach to problem D, one could think of a map storing nodes at different depths obtained by a BFS. Then, with a DFS for nodes in order of increasing depths, we could form paths for the unvisited ones till the leaf and stop. Then the same for the next unvisited node at the same depth, or at the next depth from the root if no such vertex is available. Code: 155981592

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

My story for problem C During contest i find problem C harder for me as compared to D,E

Then i start thinking whose idea is it ? I realized these types of detective problem is given by MikeMirzayanov 100%.

I didn't got AC during contest for problem solution ? I got AC for finding the problem Setter XDDD

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

Also, might be an unpopular opinion but E seems easier than C to me. And for the record, I somehow, am able to solve the problems made by MikeMirzayanov much more often than those designed by others in Div 3 rounds!

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

Can somebody provide a detailed explanation for problem C? I was able to solve A,B,D,E in the contest. Sadly, I wasted 40 min on C for getting WA :(

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

    Observe the following things:

    The thief can only be present after the first series of ones, starting from the first one. So if after, the first 1, the next friend reports 0 or ?, they are all doubtful, till the first 0 has been reported. Since after the first 0 gets reported, the ones that report 0 or ? are either being truthful or they are out of suspicion. Now, only cases that have all zeroes, or all ones or all question marks need to be handled cleverly or separately. Also, be careful for the case where the first character is 0 (as initially, the picture is always there).

    See code below for the cleverest implementation. For coming up with such intuitions a state diagram kind of approach might help!

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
         int t;cin >> t;
         while (t--) {
         int ans=0;
         string s;
         cin>>s;
         for(int i=0;i<s.size();i++)
         {
            if(s[i]=='?'){ans++;}
            if(s[i]=='0'){ans++;break;}
            if(s[i]=='1'){ans=1;}
         }
         cout << ans << endl;
         }
         return 0;
    }
    
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After reading the editorial 3 times and going through the implementation: https://codeforces.com/contest/1675/submission/156054809

    I have jotted down my detailed understanding on C implementation and idea here: https://codeforces.com/blog/entry/102550?#comment-909479

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

    If the person at a particular position is a thief then at all positions to his left, you would either have '1' or '?', at all positions to his right, you would either have '?' or '0' (and at that particular position you may have anything)

    Basically, you have to find the number of such positions in the given string.

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

    There are initially n friends. There is only one thief. Everyone will tell truth except the thief. Now let's test every friend one by one.

    Suppose I am suspecting i th friend.

    There are two cases:
    1) i th friend is thief.
    2) i th friend is not thief.

    Case no. 1:
    If the i th friend is thief, all friends who entered earlier than i th friend will tell truth. They will only response "1" or "?" but not "0" because the painting had not been stolen when they were in the room.
    All friends who entered later than i th friend will also tell truth and response "0" or "?" but not "1" because the painting has already been stolen.
    So i th friend can be thief if there is only "1" or "?" in left and "0" or "?" in right. We have to count such friends.
    If it doesn't happen, i th friend is not thief.

    Case no. 2:
    If i th friend is not thief, we will continue suspecting next friend.

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

Following are my submissions for problem B: C++: 156057742 Python: 155968226 Can someone help me point out as to why I am getting TLE for these solutions. Thanks!!

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

    ai<=2*10^9 and you are looping into ai. the solution is not necessarily dependent of ai so you should just tweak it to not focus on single two adjacent number without giving away too much.

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

problem D : why im getting tle ??

https://codeforces.com/contest/1675/submission/156046510

updated : Ac

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Maybe C is simpler if we do

3 Cases:

  1. It is a '?' increment counter

  2. it is a 0, return counter + 1

  3. it is a 1, reset the counter and set it to 1.

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

Can anyone explain what does int lend = min(j, k - a[i]); mean, in problem G?

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

    It's the number of pancakes, we need to take from dishes with bigger index. k — a[i] is how many is missing to get sum = k but we can't need more than j, because all pancakes on previous dishes are placed, so it's min(j, k — a[i]).

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

Question D,why I always got tle if i look for the path from up to bottom?

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

    and also tle with the tutorial's method

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

1675F - Vlad and Unfinished Business is exactly the same as the L3-2 on CCCC-GPLT a few days ago. LOL

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

C is doable with prefix sums ( same idea as the simple solution )

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

My $$$O(n * m^3)$$$ for G almost got TLE. Submission

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

Any resources or similar problems to better understand G? Still confused by just reading editorial.

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

Can anyone explain the solution of the problem G-Sorting Pancakes??

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

    In G, intuitively we see that a dp solution will work. If we want to put some pancakes on the ith dish, we need to have the same or more pancakes on the previous dish. To determine what can be put down later, we need to know how many pancakes we have put down previously. Hence, we need to take note of 1) how many pancakes we put down on the ith dish, and 2) how many pancakes we have put down in total. These will form our state. Hence we can have dp[i][number of pancakes on ith dish][number of pancakes put down in total] to describe our solution. The number of states for dp[n][m][m] is n * m * m which is 250 * 250 * 250 which is small enough.

    To transition to dp[i][j][k], we come from a previous state with fewer total pancakes. But the previous state's number of pancakes must be more. So we have dp[i-1][j2>=j][k-j] -> dp[i][j][k]. So, dp[i][j][k] = min(dp[i][j][k], dp[i-1][j2][k-j] + some transition value) for all j2>=j. The transition value (referred to as "add" in the editorial) is the number of moves required to go from a "pancake configuration" of having k-j pancakes in the first i-1 plates, to the same configuration but with exactly j pancakes on the ith plate. I don't know how people calculate these transition values elegantly. I had a greedy and incredibly messy way to calculate these.

    Finally, the answer is the minimum value for dp[n — 1][j][m], for 0<=j<=m. I hope this helps.

    You may refer to my solution 156195983 but it is in python, with the differences of me reversing a to solve for increasing pancakes, and I switched the definitions for j and k. So my definition is dp[i][prefix sum of pancakes up to i][number of pancakes on i].

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

      can u elaborate why the dp is : dp[i][number of pancakes on ith dish][number of pancakes put down in total] and why not dp[i][number of pancakes put down in total][number of pancakes on ith dish] ? Can we imagine this as a 3D matrix? If so, then what do the row, column and height of this matrix implicate?

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

        Both ways work. I used the latter which is dp[i][number of pancakes put down in total][number of pancakes on ith dish] in my actual solution. But the solution used in the editorial uses the former which is dp[i][number of pancakes on ith dish][number of pancakes put down in total].

        I will also discourage you from visualizing dp matrices spatially because it is very difficult and unnecessary. The important thing for doing dp is to have a firm understanding of the states, their transitions and their edge/boundary cases.

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

Can anyone explain me how does solution code of C problem works? How can the overlapping 1's give us answer to the question?

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

Can someone explain the solution for problem E. Tutorial is somewhat complicated to understand.

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

    I can give an idea , what worked for me . I created a map<char ,char> that initially maps all the character to itself . Like for eg a->a , b->b , c->c . Now suppose for eg we have string "ge" . Main task first would be to reduce g as much as possbile . Suppose we reduce g to b .
    Then i changed mappings and mapped all the char from g to b to 'b'. for eg map['g'] now ='b', map[e]='b' , map[d]='b' and so on till b ; and stored the current char ='g' && answer+=map[g]. Now if we encounter another char 'e' in string "ge" which is smaller than current char ;then we just have to do answer+=m['e'];
    Hence answer 'bb' ; Ofcourse there are 2-3 corner cases to solve.....

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

Can you please explain why in the task g dp transitions are d[i][last][k] = d[i-1][last][k-last] does it means that last = j, instead of last >= j?

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

I solved problem F with dfs, dp, and LCA+binary lifting. A lot more stuff than needed lol

156882408 Warning: Code is quite messy and I haven't commented. Enter at your own peril.

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

Hi, for B i tried a mathemaical aproach using log it runs fine in my IDE but (Here) when I divide log(a[i-1]/a[i])/log(2) it gives wrong values, example log(8/1)/log(2) = 2 is there something wrong with the compiler ?? Here is my code : https://codeforces.com/contest/1675/submission/157855207

Thank you :)