Educational Codeforces Round 95 Editorial

1418A - Buying Torches

Idea: vovuh

1418B - Negative Prefixes

Idea: BledDest

1418C - Mortal Kombat Tower

Idea: vovuh

1418D - Trash Problem

Idea: vovuh

1418E - Expected Damage

Idea: Roms

1418F - Equal Product

Idea: adedalic

1418G - Three Occurrences

Idea: BledDest and Roms

• 19 months ago, # ^ | really? Is it ?

• 20 months ago, # ^ | could you please explain your solution a bit?

  • 20 months ago, # ^ | ← Rev. 3 →   +30 Spoiler

    • 20 months ago, # ^ | Thanks. Really nice solution.

      • 20 months ago, # ^ | You welcome. XD

    • 20 months ago, # ^ | I think you can model most dynamic programming problems like a graph problem. After all, dynamic programming states are nodes and transitions are directed edges. Together they create a DAG and in this problem you minimize the cost of the transitions.

      • 20 months ago, # ^ | ← Rev. 2 →   0 I think you can model most dynamic programming problems like a graph problem. Agree. This is not my first time solving a DP problem with graphs.

• 20 months ago, # ^ | Or maybe dijkstra is a DP algorithm?

  • 20 months ago, # ^ | Not sure why you're getting downvoted. When running Dijkstra's on a graph, we can consider the graph as being implicitly ordered according to the eventual costs of the nodes, with edges going from low cost to high cost. This graph is acyclic, and the cost of a single node is computed in terms of the nodes which have an edge directed into it, which is literally just DP. The only thing that makes it different from a "normal" DP algorithm is that we compute the topological ordering of the nodes on the fly, rather than knowing it beforehand.

    • 20 months ago, # ^ | Maybe they don't get the idea (in a funny way), since we all know of Dijkstra as a algorithm to find shortest path in non-negative weight graph.

• 20 months ago, # ^ | One segment tree is enough. Consider which numbers change their segments when you proceed from some right border rr to r+1r+1. Easy to see that it's only ar+1ar+1. So we can actually clear the segments it contributed to and add the ones it contributes to now.

  • 20 months ago, # ^ | ← Rev. 2 →   +7 Thanks for explaining , just one query remaining. How do we update the regions when moving from r to r + 1, I mean a subarray can be bad not just because it doesn't has exactly 3 numbers of ar+1ar+1 but may be it doesn't have exactly three numbers of some other number . We can convert a good subarray to bad when moving from r to r + 1 , but how do we convert from bad to good. How do we know what numbers are making this a bad subarray .

    • 20 months ago, # ^ | ← Rev. 2 →   +5 You don't exactly store if the position is bad or good in the segtree. Each position only knows the number of bad segments it's covered by. For each bad segment [l;r][l;r] you add 1 on positions [l;r][l;r] in a segtree to maintain these values correct. And a position is good if the number of bad segments covering it is zero. Thus, adding a bad segment is adding 1 on a segment and removing a bad segment is subtracting 1 from a segment.

      • 20 months ago, # ^ | Got it . Thank you.

• 20 months ago, # ^ | Well, this xor hashing thingy is quite a common topic. I knew it because I encountered it multiple times. Initially the problem was to count the segments with 0 or 2 occurrences, so the usual xor worked perfectly. Thus, for me the transition was only from bitwise to tritwise. BledDest suggested that idea and I found it pretty cool, props to him. Couldn't really come up with it myself.

  • 18 months ago, # ^ | Sir, I want to know one thing. Experience is a very important thing in competitive programming. But How to develop the power of innovating solutions to such problems? Like someone solved problem C with Djikstra....Everything cannot be covered by experience ..how are you able to think of new solutions to new problems???

• 20 months ago, # ^ | ← Rev. 2 →   0 The aniervs's solution was harder to interpret ( and I am still not able to understand it fully), but it would be great if an alternate solution of problem D is added to the editorial based on his idea just like you guys did for problem G(hashing and segment tree). It will help people like me in knowing different ways to tackle the problem. Also thanks for both unofficial editorial and this editorial... Learnt a lot!!

• 20 months ago, # ^ | Idk if aniervs's solution is right, ternary search is quite hard to prove there. The function is surely convex but possibly not strictly convex which might break ternary search. Other than that I doubt it gets easier than such solution.

• 20 months ago, # ^ | We (adedalic, if I am not mistaken) once set a similar problem about bringing some boxes to the same point, and we thought it was possible to solve it with ternary search. But, unfortunately, the function f(x)=minimum number of actions required to bring all items to position xf(x)=minimum number of actions required to bring all items to position x is not strictly convex because if there are two items in positions xx and x+1x+1, then f(x)=f(x+1)f(x)=f(x+1), but it is not necessarily the local minimum. Though there might be some way to handle it.

dp[i][0] //denotes min coins spent if I kill the last boss 
dp[i][1] // denotes min coins spent if my friend kill the last boss .

int ans(int i ,int j){
        if(i<0)
            return 1e9 + 7 ; 

        if(i==0)
        {
                return a[i]; // since my friend's turn is the first one 
        }
        if(i==1)
        {
            if(j==0)
                return min(ans(0,0),ans(0,1)) ; 
            else
                return  a[i] + min(ans(0,0), ans(0,1));
        }

        int& res = dp[i][j] ; 
        if(res!=-1)
            return res ; 
        if(j==0)
            res = min(ans(i-1,1) , ans(i-2,1)) ; 
        else if(j==1)
            res = min(ans(i-1,0) + a[i], ans(i-1,0) + a[i-1] + a[i]) ; 
        return res ; 
    }

• 20 months ago, # ^ | ` else if(j==1)` ` res = min(ans(i-1,0) + a[i], ans(i-1,0) + a[i-1] + a[i]) ;` ` return res ;` It should have been :- Your code here... res=min(ans(i-1,0)+a[i],ans(i-2,0)+a[i]+a[i-1]);

  • 20 months ago, # ^ | Yes , thank you ! It was a stupid mistake

• 20 months ago, # ^ | There is a mistake in the line: if(i==0) ** {** ** return a[i]; // since my friend's turn is the first one** ** }** so when you are calling ans(0,0) and ans(0,1) then you will get the same result as a[0] which shouldn't be. And really telling you only have to change only if(i==1) { if(j==0) return ans(i-1, 1); else return a[i] + ans(i-1,1); //as the first boss is only killed by the friend. } And you can write more simpler version of it like these two : 1) https://codeforces.com/contest/1418/submission/92964444 2) https://codeforces.com/contest/1418/submission/92964444

  • 11 months ago, # ^ | Hello, can you please explain me what the lines for calculating first,second and min means?

• 20 months ago, # ^ | NVM I found the error, I was inserting to the multiset a value which was not initialized. This is the final submission. 92971068

• 20 months ago, # ^ | It's more simpler if you use higher and lower methods instead of ceiling and floor.

  • 20 months ago, # ^ | what is difference between both???

    • 20 months ago, # ^ | floor will return the greatest element less than or equal to that number while lower will return a strictly lower element. Similarly for ceiling and upper .

• 20 months ago, # ^ | Python has low recursion limit. Either do it iteratively or using another lang.

  • 20 months ago, # ^ | okk thanku.

Let k be the maximum j (1≤j≤n) such that pj <0. If there are no j such that pj<0, then k=0.

Your goal is to rearrange the values in such a way that k is minimum possible.

• 19 months ago, # ^ | ← Rev. 2 →   0 Ok so this is what it means. Lets have this prefix sum array [-1,-4,-5,-6,7,8,9]. Here, k = 4. This is because k is the index of the "right most negative element". Another example: prefix sum array = [1,-3,4,-5,-1,2,3] Here, k = 5. The "right most negative element" is -1, and so its index is 5. You can have positive in between the negatives, it doesn't matter. What the problem is asking is you want k to be as small as possible. So you want to arrange the array such that its prefix sum array will have the smallest k, when compared to other arrangements. I hope this helps!

  • 19 months ago, # ^ | Yeah , thanks bro..

• 11 months ago, # ^ | That is because every trade we need to give away one stick to take x sticks hence it is x-1 like u give ur 1 stick to get x sticks , out of x u give away 1 stick

  • 11 months ago, # ^ | Thanks for your explanation i understood now.