MohammadParsaElahimanesh's blog

By MohammadParsaElahimanesh, 2 years ago, In English

Hi Codeforces,

I've tried my best to make a different editorial, I wish you enjoy it ...

1746A - Maxmina

problem author: MohammadParsaElahimanesh, AmirrzwM

step by step solution
solution

1746B - Rebellion

problem author: MohammadParsaElahimanesh

step by step solution
solution

1746C - Permutation Operations

problem author: napstablook

step by step solution
solution

1746D - Paths on the Tree

problem author: AquaMoon, Cirno_9baka, mejiamejia, ChthollyNotaSeniorious, SSerxhs, TomiokapEace

single step solution
solution

1746E1 - Joking (Easy Version)

problem author: MohammadParsaElahimanesh

step by step solution
solution

1746E2 - Joking (Hard Version)

problem author: MohammadParsaElahimanesh, AmirrzwM

step by step solution
solution

1746F - Kazaee

problem author: MohammadParsaElahimanesh

step by step solution
solution

1746G - Olympiad Training

problem idea: SirShokoladina

problem development: SomethingNew, pakhomovee, SirShokoladina

single step solution
solution
| Write comment?
»
2 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Nice Editorial!

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

    Can someone please explain what is meant by balls passing through the subtree of node u in D Editorial

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

      each path can be assumed as unique balls. Initially we start with k balls(paths) from the root, then at every instant we proceed to some child with a path, that is same as giving that ball to the child.

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

Can someone explain problem c in a different way? I don't understand what to do after computing the difference array.

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

    suppose that i-th number is x. so now if I add x to all the numbers to the right of x ,then all the numbers on right of x will become greater than x,so inversion due to x will remain in this new array; If I do it with every element of the array then there will be no inversions left.

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

    We will Divide the array into continues sub segment where every sub segment is increasing and we aim to make the array increasing because in this way we will have 0 inversion e.g. 1 6 2 5 3 4 We will Divide to 1 6 2 5 3 4 Now because its add so the order doesn't matter How to make it increasing if we add 6 after 6 we will guarantee that every number after 6 is greater than 6 and go to the next sub segment and add 5 after 5 and so on So the answer will be 1 1 1 1 5 3 For suffix ones I don't care because it will keep the order the same That its my solution i think it is intuitive

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

    An observation that could be made in any array is that if I try to remove/solve an inversion, it cannot affect the other inversions present in the array. eg. take array as 2 3 4 7 8 6 5 1. we have a(8,6) b(6,5) and c(5,1) as inversions.

    1. Let us first solve inversion b. So we don't touch 6 and add (1+2) to suffix at position 7.

    2. Now since we didn't touch 6, the difference b/w 8 and 6 remains the same.

    3. Also since we are applying operation to the whole suffix, the same amount will be added to both 5 and 1 . So the difference b/w them also remains the same.

    Hence we can greedily pick inversions which have smaller difference which can help us to solve the maximum of them.

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

      can you explain how you add (1+2) to suffix at position 7?

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

        For each inversion we can store the difference and the index of the second element upon which we work. We sort this array and then for each inversion initialize the increment(x) as 0. till we reach x>diff we keep on adding ith value for ith operation and push the stored index in the array into our answer.

                ll n;
                cin>>n;
                vector<ll> arr(n);
                a(i,0,n) cin>>arr[i];
                vector<pair<ll,ll>> unfit;
                a(i,0,n-1){
                    if(arr[i]>=arr[i+1]) unfit.push_back({arr[i]-arr[i+1],i+2});
                }
                sort(unfit.begin(),unfit.end());
                queue<ll> q;
                a(i,1,n+1) q.push(i);
                vector<ll> ans;
                ll it = 0;
                for(auto pr: unfit){
                    ll x = 0;
                    while(x<=pr.first && !q.empty()){
                        ans.push_back(pr.second);
                        x+= q.front();
                        q.pop();
                    }
                }
                while(ans.size()<n) ans.push_back(1);
                for(auto x: ans) cout<<x<<" ";
                cout<<endl;
        
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    I used the following explanation to convince myself that the intended solution works:

    In a permutation of 1 to n, 1 is the smallest number. It is the worst victim of inversion because it is the smallest. It needs our help the most. Now we have n chances to help this victim. What should we do? Of course we should give it the biggest help. How to give the number 1 the biggest help? It is obvious to place it (its position) at the end of our answer array. This is because in our answer array, we add i to the element and its suffix.

    So, the number 1 needs the biggest help. The number 2 needs the second biggest help. The number n needs the least help.

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

    The easiest approach on problem C

    int n; 
    cin >> n;
    vector<int> ans(n);
    for(int i = 0; i < n; i ++){
    	int x; cin >> x;
    	ans[n - x] = i + 1;
    }
    for(auto u : ans) cout << u << ' ';
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I’m surprised this wasn’t the official solution. It guarantees that you are left with the array [n + 1] * n + d where d is some strictly non decreasing array.

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

      how and why please

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

    If you applied operation at index j, all differences will still the same except at the position j — 1 because: 1. all what after this position will increase with the same value 2. all what before this position will still the same

    Note that if you have n items in a, you will have n — 1 differences

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

Can anyone explain me why my solution for D is wrong. I gave stored max score of path starting from each node. Then I gave ceil(k/no of child) to first (k%no of child) greatest node and floor(k%no of child) to other nodes. My codehere

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

    With the input

    1
    5 3
    1 2 2 1
    1 1 1 100 10
    

    your code gives 116 when the correct answer is 124.

    The problem is that the maximum score of a path through vertex 2 is 102 (path 1-2-4), but once you have already sent a path that way, the next path is forced to go through vertex 3 instead of 4, so it has score 3. Instead, on the other branch, every path has cost 11.

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

I think there is a typo in solution of step 4 for problem C. It should be $$${a_{i + 1} > 0}$$$

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

    fixed, thanks

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, I think Problem B just need count the number 1 less than indices which is first non-zero element's indices in the sorted array.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        there are many answers, but if I want to be honest I choose this because it was easy to proof! thanks

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

The code of D isn't clear enough to be understood, can anyone provide clean code?

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

Thank you for this contest and interesting problems.

However, please proof-read the statements in the verdict as well.

For E1, the wrong answer prints this statement: "you can't guess the answer in 2 chance!" And this led me to assume that I'm not allowed to guess the answer in 2nd chance.

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

When I thought about doing DP for D, it looked that for each vertex with n children and p paths to distribute, we had an exponential number of ways to choose n%p ones from the n children.

So one key observation is that larger number of paths always produce larger scores, so we can use greedy as shown in the editorial.

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

For Problem D, it turns out that if I always calculate DP(child[v][i], k/cnt_child+1) no matter whether k%cnt_child or not, then I might get TLE (I'm using C++ std::map to represent the second dimension of the dp array). So it looks that this optimization is necessary?

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

    Yes, consider a chain.

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

    I came up with an example: if k = 5,6 and cnt = 3, then if we compute both k/cnt and k/cnt + 1 then the result will be 1, 2, 3 which will result in an exponential number of states.

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

    Can somebody elaborate more on why this is happening? I mean at-most, we are calculating 2n states, why TLE then?

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

      That's because the number of states may not be 2n.

      When k%cnt == 0, $$${\lfloor k/cnt\rfloor, \lceil k/cnt\rceil, \lfloor (k+1)/cnt\rfloor, \lceil (k+1)/cnt\rceil}$$$ contains 2 numbers, but k/cnt, k/cnt+1, (k+1)/cnt, (k+1)/cnt+1 could contain more than 2 numbers, which results in a chain of exponential numbers of states.

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I just recieved a message about coincidence with solutions and i admit that everything is my fault, i saw a solution on ideone.com and copied to sumbit.

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

Hi MohammadParsaElahimanesh, I think you should explain why many solutions got FST on C, many of them would be unable to figure it out why it's wrong.

Thanks

»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

One of my worst rounds ever... but good job guys.

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

In solution for D, the fourth paragraph, should $$$\lceil (x/num)\rceil$$$ be $$$\lceil (x+1)/num\rceil$$$?

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

Can G be solved with simulate cost flow?

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

I solved problem D purely recursively (it's still DP, but simple enough to not need a separate array for each node), in a similar manner as described in the editorial, but with a twist.

  • All children will have the same amount of paths.
  • If there's a remainder $$$r$$$ from the division, then you'll be able to choose $$$r$$$ children, with a path going through each of them (on top of the ones that you know from the division, that you have to take).
  • To maximize my score, I want to have the best path that goes through each children. This way, I may be able to pick the $$$r$$$ best ones for my score.
  • But if I do that, I cannot use these paths again. If I were to, the condition would no longer hold, because the difference of $$$c_i$$$ would be bigger than 1.
  • So recursively, I can return the sum of the scores each descendant calculated, but also add all the $$$r$$$ best paths that my children reported were the best available ones. That is to say, if I have $$$m$$$ children, with the list of the best $$$m$$$ paths returned by each of them in the recursion, I take the $$$r$$$ best ones for the sum.
  • After that, I'll return both the acquired sum, and "the best path that goes through the current node", which in reality is the best one remaining in the best path list, after taking $$$r$$$ of them, with the current node's score added in. This way, I'll be telling my parent the best path that goes through the node, that's available to take for any of my ancestors. And note that I'll always have a path remaining in the list, because $$$r < m$$$, as the division was done by splitting between $$$m$$$ nodes in the first place.

Here's my code: 176372281

I have declared an array called "maxToHere", but I didn't need to use it after all. and forgot to remove it in contest.

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

    Can you tell me what's wrong in my approach. For choosing which k%child children will get +1 extra path, I was finding X = (max score sum path starting from child and ending at any leaf node), then I gave +1 extra path to k%child children having largest value of X.

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

      Look at this WA I had during contest: 176361876

      Compare the differences between this code and the one that gives AC I linked above. That may help you understand what I mean with available path.

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

    dp doesn't mean having some array. what you do is still dp, and it calculates same states.

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

      I mean, I know almost any kind of memoization tends to be DP. For example, you could say that prefix sum is indeed DP, but it's as simple as just using a for loop.

      What I meant to say is that you could skip checking multiple states for each node, with this sort of "greedy" approach, and avoid using a "dp" array altogether. The states are simple enough to make it recursive, but I understand your point.

      In this case then, states are for each node are $$$(sum, maxpath)$$$, where:

      • $$$sum$$$ is the sum of $$$c_i s_i$$$ known for all descendants (and itself).
      • $$$maxpath$$$ is the max sum of $$$s_i$$$ for an "available" path starting in the current node to a certain leaf. An available path is one such that if it's chosen for the multiset, the condition still holds with all decisions already done for all descendants.

      It's a matter of something that you would surely call "DP on tree", becomes more like just "divide and conquer". The states explained like that may seem more clear to understand (or maybe not), but in this case I prefer to think of the process you go through to get to the solution approach. Nevertheless, I guess I will remove the parentheses in the previous comment to avoid confusion.

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

I get wrong answer on test 3 for problem F because I use rand() instead of mt19937. TAT

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

the probability will be less than $$$\frac{1}{2^{30}}$$$ which is reasonable for problem constrains

Is it?

For such an argument the constraints should include the number of test cases. As it was not public during the contest, I felt this was not reasonable. $$$(1 - 300000 \times 2^{-30})^m$$$ is about $$$0.97$$$ for $$$m = 100$$$ cases or $$$0.76$$$ for $$$m = 1000$$$ cases. I won't be happy to lose a whole score with this uncertainty.

In general — I always think that for problems with intended solutions being randomized, an upper bound on the number of test cases should be disclosed, or there should be no system tests (and no hacks). And since this can suggest the crucial idea of randomized solutions, it might be a good way to have a rule about global upper bound on the number of test cases. (... or does it exist somewhere I don't know?)

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

    you are correct, but I think there is a limit on m naturally(but rules must contain it), I never saw problem with m more than 300 anyway and also consider all of (300000) queries are not on type 2(also in many queries probability is 1/k30 and k >= 3).

    at end you could use 35 instead of 30, I myself use 50 in main solution(because it is model solution)

    I'm sorry, you were unlucky

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

    Like 998244353 problems lol

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

For E, when you're down to three candidates, you can eliminate one with only 3 queries:

  • First query $$$a$$$.
    • If the answer is NO, then query $$$a$$$ again. If it's still a NO, then eliminate $$$a$$$ and we're done.
  • When we get YES for $$$a$$$, then query $$$b$$$ immediately after that.
    • If the answer is also YES, then eliminate $$$c$$$.
    • If the answer is NO, then eliminate $$$b$$$.
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Finally noticed this in Problem C after being dumbfounded yesterday:

"...all of its elements by 1 i"

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

    I notice this after reading your comment

    I fill terrible

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

    wasted 30 mins on this! :) Got a sweet FST!

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

    In the explanation of test sample 1, there is this line:

    The final array [11,12,13,14] contains 0 inversions.
    

    We must be adding i, not 1, for each operation in order to reach these numbers.

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

Is it just me, or editorials in codeforces are actually very bad?

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

    It's not just you. It's at least two of us.

    I think the reason is simple. There is some quality control for problems but there is none for editorials. Global rounds usually still have better editorials than ordinary ones though

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

    Still usually much better than in atcoder

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

Can anyone say about the second question. I am not able to understand it

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

    Yes if someone would explain it in simple sentences it would be much appreciated!

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

      I have no idea what is described in the editorial. Here is my solution.

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

For Problem B-

I simply counted the number of 1s in the array, and all those elements should be at the right of the array, and the max element can be only 1 to AC your solution. Suppose n=10, and C(1)=5. Then all these one should be at the end of the array(i.e. index 6-10). So we directly have to count the number of 0s from the index n-c to n, and that's the answer.

Solution

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

In problem D, can anyone explain the difference between ⌈x/num⌉ and ⌈(x/num)⌉?

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

    There is no difference... is that written somewhere in the editorial? I suppose it may have been edited afterwards.

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

In question E1 what if one is YES and other is NO . Any one of them can be a lie , In step 4 they have only mentioned the cases where both are either YES or NO.

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

    Did you mean step 3? In any case, what's important here is that they cannot both be lies. If you have sets $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$, you can query $$$A \cup B$$$ and then query $$$A \cup C$$$. There are four possibilities:

    • both NO: Target is not in A
    • first NO, second YES: Target is not in B
    • first YES, second NO: Target is not in C
    • both YES: Target is not in D

    In all cases, we can eliminate one of the four sets.

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

      I could easily understand (NO,NO), (YES,YES), but had difficulty in (NO,YES) and (YES,NO) cases.

      For this, we can think along the following lines -

      • In AUB and AUC, if it says (NO,NO) we can definitely tell that one of them is correct and since A is common to both, the number definitely won't be in A.

      • Some stuff in logic (1) AUBUCUD = Universe (2) if S is YES, then (Universe — S) is NO.

        using (1) and (2), we can have AUB is YES => (Universe — AUB) is NO => CUD is NO

      Now, we can determine for all cases. For example, when there is (YES,NO)

      AUB is YES => CUD is NO
                    AUC is NO
       -------------------------
                    C is common. Thus, definitely not in C
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

1746D - Paths on the Tree editorial is awful. You should at least mention that we solve it by dp over subtrees. Then, give an idea how to calculate value, and why it works. I would also mention why all balls should reach leafs. Also I would like to see proof of claim about floors and ceils.

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

    I would like to see the proof on the floors/ceils as well. The suggested solution was the first thing that came to my mind, but I didn't know how many different choices I'd need to consider for each node. I was only able to observe that there are at most two values when $$$num = 2$$$ through considerable case analysis, and didn't know how the result would extend to larger divisors, and didn't feel comfortable with coding it when this number was unknown, as it would have significantly affected how the DP is set up (and I was worried there would be too many to pass the time limit).

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

Why is D: 176443434 TLEing

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

    If dp[node][k] is 0, you cannot check if it was searched before correctly.

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

      In my solution, I had used dp.count({node,k}) to check if a state had been visited before and it still gave TLE. Are there any problems caused by count function too? 176444934

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

        If ch is a divisor of k, do not search dfs(it, x + 1).

        Because it will make 2 states to 3 states, and it will have an exponential growth.

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

Problem D-->1746D - Paths on the Tree,I spent several hours trying to find the problem in my code, but it didn't work. Who can tell me what the error is in my code, and I still can't pass the second text case-->176451251

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

I want to share my alternative solution to 1746E1 - Joking (Easy Version)

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

    abBB, aBbB, AbBa, ABba — here is easy to show that in some cases should be definitely a = b, or definitely a != b.

    I think the first two here should be abBA and aBbA?

    Anyway, this is a very interesting approach! I don't think we need to actually build a graph; we can, for example, set the first bit as a base and then ask questions in a chain like abbaccaddaeea... to determine other bits exactly or at least their relation to the base bit. When we determine the value of the base bit (Case 2), we update the previous bits that depended on it, set a new bit as the base bit, and start a new chain with it. Even if we cover 17 bits without determining whether the latest base bit is 0 or 1, we have two guesses to try both options.

    I considered whether this can be adapted to solve E2, but I think the worst-case would be if we keep hitting Case 2 and reset the base, requiring $$$4 * 16 = 64$$$ questions. We don't need to determine the remaining one, since we have two guesses. However, this kind of "base reset" does not take advantage of the last element of the chain, e.g., if we get abBa, we might be able to utilize the last a somehow to keep the chain connected when we change the base. It might be possible somehow to avoid disconnecting the chain, allowing for 3 additional queries per bit (plus 1 to start the first one), resulting in 49 queries (suffices for E2).

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

      We don't know about bits inside graph, only their relation. This is why we also need to check 17-th bit, because we either will know its value or relation. We do two guesses to try both possibilities for some node in graph. If you have proof of work in 49 queries I would like to look at it.

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

Problem B easier

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

    OMG, I haven't ever seen code in Perl, it looks like you wrote random symbols from your keyboard. Could you write a pseudocode in English?

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

For D,how to strictly prove that the number of states is O(n)?

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

GOT IT!!!

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

Here is an interesting problem that I initially misread C to be — instead of increasing the all elements of the suffix by $$$i$$$, we increase them by $$$1$$$ in each operation. I've been thinking about this question and don't seem to be able to come up with a solution. Any ideas?

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

F can also be solved with a slightly different randomized solution. Let's create $$$k$$$ random maps $$$f_1, \ldots, f_k$$$ from the numbers in the array to, say, 32-bit integers. Then, we can check that a subarray satisfies the property for given $$$k$$$ by finding the sum of $$$f_i(a_l) + \cdots + f_i(a_r)$$$ for all $$$i$$$. All these sums have to be divisible by $$$k$$$, and the converse is true with very high probability.

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

    ivan100sic can you please provide some explanation with examples? for eg if a[l..r] is: {1,1,1,2,2,2,3,3,3,3,3,3} for k=3 then for each random maps the sum will be divisible by k, but the answer is "NO". please let me know in case if I miss anything.

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

      You're not summing $$$a_i$$$ but $$$f(a_i)$$$ which are random.

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

I am struggling with problem D for days and my solution didn't accepted till now, can any one figure out what is the problem with my code ? Any help will be appreciated.

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

    understood finally, the optimal is sort according to the differences not the values.

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

I have a confusion. The editorial for problem D says that, for a certain tree structure, a particular node can have ONLY two possible values of cnt which is why we only need to work with a certain node for 2 times and save it in a memory because we might encounter the same state later. So according to the solution provided, for a certain node i, answer[i] is a vector which has size not more than 2. right? If so far what i understood is true, how can i logically prove that there are only two possible values of cnt for a certain node? Is there an intuitive way to prove this?

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

    I add assert(answers[v].size() <= 2) in line 38 176651123 and it works !

    about last question i must say that if all node with height h have at most two numbers, It's easy to prove this condition hold for all nodes with height h+1(see the proof in editorial)

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

    Since x and num is integer and num >= 1, let's observe this sequence of numbers:

    • 0/num, 1/num, 2/num, ..., (num-1)/num,
    • num/num, (num+1)/num, ...
    • (2*num)/num, (2*num+1)/num, ...
    • (3*num)/num, (3*num+1)/num, ...

    for any adjacent elements in this sequence, it is impossible that (x/num) < A and A < (x+1)/num and A is integer ( if you want x/num and (x+1)/num cross some integer A, at least one of them will be integer. ) so $$$\lceil (x+1)/num \rceil - \lfloor x/num \rfloor \le 1$$$.

    below is an illustration when num is 3:

    (I hope this helps, forgive my poor English :)

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

      Thank you so much for your explanation. And your English is good. :D

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

For people who solved E1: how do you reach the $$$abba$$$ construction in E1, or how did you reach your construction for $$$n = 3$$$?

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

    n=3 for me was built on the explanation of the example (using one of the two guesses to either solve it or force a non-joking answer)

    For the main construction I calculated what the possible answers to a pair of queries could mean. For yes yes to reduce the search space you need something not in either query, for no no you need something in both queries and if the responses are different (yes/no, no/yes) you need something unique in the no query which suggests that splitting into 4 would be best.

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

For C, why don't 1 2 3 4 ... n works?? for example if we take a case 3 2 4 1 my answer for this is 1 2 3 4 dry run : i = 1 -> 4 3 5 2 i = 2 -> 4 5 7 4 i = 3 -> 4 5 10 7 i = 4 -> 4 5 10 11

but this logic is giving me wrong answer, what am i missing??

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

MohammadParsaElahimanesh, can you please help in question 1746D - Paths on the Tree. Like understood what is written in the editorial properly but the most confusing thing is how you write dfs I.e. recursive function so clean without any error. Like what I want to ask you is , in my case to understand your dfs implementation part I am going deep into recursion like this function is calling these inner functions and so on and actually it bec0mes very confusing.

So do you just write dfs assuming that the function calling will give me the correct result like in case of DP. And all I have to do is working on the current state without any worry of how all other states will work and they will work correctly. So how do you think sir during writing dfs ??

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

    sorry for poor english in advance, we can calculate answer for some subtree and it does not relate other nodes, because each time we go down in tree and do not repeat some node in one way

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

      Sir, I did not get it what are you trying to say? Can you please help me explain more elaborately/ clearly??

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

      MohammadParsaElahimanesh, sir only last time I will disturb you can you please tell in submission 176328072, what the 2nd last line I.e. dl += ws[rs] is doing??. Very Sorry if I am irritating you by pinging you again and again but I genuinely do not get the point what 2nd last line in dfs function is trying to do ??

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

        dl += ws[rs] means if we call node k one times more, how much score can we reach, so dl = w[k]+ws[rs]

        note we will pick ws 0 1 2 3 4 5 ... rs-1 surely and ws rs if we call some node one times more

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

          But, Why we need to call node k one time more?

          My thought: I think it is because our main objective is not only to calculate the answer in dfs function but we also have to return to the main function its calculated dfs function answer.

          Am I thinking correct sir ??

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

            no, It's not true, please read toturial agin, i calculate dp1 and dp2 but he calculate them together

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

              I think now I am irritating you, but I have read the editorial many times and your code is looking correct to me but in this submission 176328072 I am genuinely not getting why we need to add node k one time more I.e dl= w[k] + ws[rs] ??

              Can you please last time explain MohammadParsaElahimanesh??

              You can look at this submission also if you want , both are written in same way but here also last line did not make sense to me 176439185

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

                no problem, but at least like my massages :)

                consider node v, it has m children and we want to calculate "what is the answer if k balls reach to v" we name it dp v, k. the most important point is if k balls reach node v. k/m+1 balls will reach to k%m children of v and k/m balls will reach m-k%m children of v. or in another word, one more ball reaches to k%m children of v.

                so we can use dfs and it returns a pair {dp[ch][k/m], dp[ch][k/m+1]} where ch is children of v

                sorry for poor english

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

My algorithm to 1746C keeps failing

My Algorithm:

Step 1: Reverse loop the array and increment the element if the difference from the consecutive previous element is negative. Step 2: How to find the increment? Finding an increment is straight forward. Basically, this is an Arithmetic Progression: So, Sum of N elements is:

S = (n / 2) (2 * a + (n - 1) * d)

Hence, there is a quadratic equation that I need to solve.

S = (n / 2) (2 * a + (n - 1) * d)

Step 3: Keep doing it till the array contains elements in non-decreasing sorted order. Step 4: If the array is already sorted, but we still have operations left, then just increase all array elements by that current operation increment. My Submission link which is failing: https://codeforces.net/contest/1746/submission/177280199

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

The editorial for problem D is too simple. It's hard to understand. I'm Chinese. When I participant in some Chinese algorithm contests, say, Nowcoder contests, the editorials are mostly hard to understand even though they're written in Chinese. I don't know why. Maybe I'm a newbie, and the editorial is for those experts to read.

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

    I read the code. I sort of understand. Maybe this is what called "talk is cheap, show me the code". Anyway, thank you.

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

Fun fact: the author's solution of problem D is $$$O(n \log n)$$$ because it sorts the children by the best "extra" path, but it can actually be improved to $$$O(n)$$$ with std::nth_element (which uses the Introselect algorithm). The idea is that we only need to partition the elements according to the $$$j$$$-th largest element for some $$$j$$$, and we don't care about their relative order beyond that.

177698814

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

I know it's very, very far out of my league but I saw flows in the tags for G, I tried to think of a way to setup a min cost max flow network that would solve the problem at all, even if it is not the intended time complexity.

I thought of two ways but they both have issues and I don't know how to (or even if it's possible to) combine them.

First was that to ensure that the numbers of tasks are what I need, I would create three nodes for each type of task and they have capacities $$$a$$$ $$$b$$$ and $$$c$$$ going into the sink

The second was to handle deadlines I create a node for each day, connect it to sink with capacity 1, connect a task to it's deadline and connect each day to the previous one, signifying that you can do a task with a deadline $$$d$$$ on $$$d-1$$$ but not the other way round.

Any help would be really appreciated.

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

I don't get the idea of this statement in problem F: It's not so hard to prove that the probability is equal to 1/2 for k=2. As I understand, instead of checking the number of occurrences of every single number, the intended solution will sum up all the number of occurrences of each number in the set $$$S$$$. However, if $$$|S| = 4$$$ the probability of concluding YES when the actual answer is NO should be $$$\dfrac{7}{8}$$$, and this probability is even higher with a larger $$$|S|$$$. What is wrong with my thinking?

7/8 False Positive
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, step1 -> solution there is a typo stpes

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

For those who are interested.

Problem E1/E2 is similar to https://www.codechef.com/JUNE20A/problems/GUESSG (Editorial).

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

.

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

Can anyone explain me what's the space complexity of this code,I am getting MLE on test case 2. here's my submission: https://codeforces.net/contest/1746/submission/202337720

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

    Hint : resize doesn't do what you think it does. In fact, if you don't use the correct version of resize, then regardless of space complexity, your algorithm would also give WA. Can you see why?

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

      but now my code is giving TLE on test case 25. https://codeforces.net/contest/1746/submission/202518774 I don't think collisions occur in maps and when I saw other people's code,so they have used different method to store the answer than mine. can u give me some idea to optimise this approach or rough time complexity of this code

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

the technique used to solve problem F , is that a renowed trick , are there more problems on that trick.

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

for D, why do we need a base case in DP ? How could it happen that we enter a node twice?

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

In problem E2, number of needed questions seems to be 3*(log2(n)+1).

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

Can someone please explain why the time complexity of problem D is O(n). why number of states in O(n) ? Why cnt can only be two adjacent integer (x,x+1) ?

Thanks in advance