pikmike's blog

By pikmike, history, 5 weeks ago, translation, In English,

1380A - Three Indices

Idea: BledDest

Tutorial
Solution (Ne0n25)

1380B - Universal Solution

Idea: adedalic

Tutorial
Solution (adedalic)

1380C - Create The Teams

Idea: Roms

Tutorial
Solution (Roms)

1380D - Berserk And Fireball

Idea: Roms

Tutorial
Solution (Roms)

1380E - Merging Towers

Idea: Roms and BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (pikmike)

1380F - Strange Addition

Idea: Roms

Tutorial
Solution 1 (pikmike)
Solution 2 (Roms)

1380G - Circular Dungeon

Idea: BledDest

Tutorial
Solution (pikmike)
 
 
 
 
  • Vote: I like it
  • +135
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Fastest editorial for an educational round I think.

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Btw, in E merging without “smallest to biggest” optimization somehow passes the tests :)

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

    Nothing surprising. There is even such a heuristic: randomly connecting sets. It works for O(nlog(n)).

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

      Oh, that makes sense, thanks

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

      No it's not $$$O(n \log n)$$$. Let's say we have $$$n$$$ one element sets and in $$$i$$$-th round we merge $$$i+1$$$-st set to su of first $$$i$$$. Then on $$$i$$$-th turn we have $$$\frac 12$$$ probability to do one insert, and $$$\frac 12$$$ to do $$$i$$$ inserts, which means on avearge $$$O(i)$$$ inserts on $$$i$$$-th turn, which adds to aveeage of $$$O(n^2)$$$ inserts.

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

        That's one way to look at the probabilistic formulation. If you have broader probability space, for example, if operations are also chosen randomly, then the probability of big set being in the operation can be small, and I think it won't be O(n^2). I'm not sure how to show it, but my solution passed in the beginning, until they added a counterexample as yours, so if tests were generated using random at first, I think it shows that average complexity is not so bad.

»
5 weeks ago, # |
  Vote: I like it +135 Vote: I do not like it

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

In the solution of problem E, visualising the towers and its merged states as tree is quite impressive. Thanks for the LCA solution.

To me, Small-to-large merge sounds like a greedy approach. It would be helpful if you can elaborate the alternate solution.

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

    If you are looking for dsu solution.... If you always merge smaller set to larger set then it is o(n log(n))... Because a single element will not change it set more than log(n) time..... Let say we have a element 'a' which is in set 1 of size x we merge set 1 to set 2 of size greter than x suppose y.... Than we have atleast 2*x element which get in same set as y>x..whenever we are merging we are atleast doubling the size of. set

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

Statement of problem B was difficult to understand until watching the image at last as didn't know about the game.

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

Can anyone explain to me why greedy works in C? It was kind of intuitive to me, I coded it up and it passed but I still can't figure out that why's it optimal?

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

I don't understand problem-B.Anyone help me to understand..And I don't know about this game.

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Why are submissions low on problems? Were they hard, imo first 3 were pretty easy?

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

    You didn't even gave the round......Better first participate in the live round and then give your wishful verdict on whether the problems were easy or tough and why there are more or less submissions on a particular problemset

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

    Codeforces was down for the first half-hour of the round; by the time it came back up, the round was declared unrated and many competitors left.

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

problem G. 'Let the values be x and y. If they differ by at least 2 (x≤y−2), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.' I could not understand the proof below. I indeed turn a coefficient y into a smaller one (x + 1), but how can I assign every regular chest to the old value, with the changes of this two interval lengths?

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

    Sorry for the misread of the statement. Every chest's position can be changed.

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

https://codeforces.com/contest/1380/submission/86713545

Can anyone explain why i am getting memory limit exceeded error? It is the solution to problem A and is not much different from what explained in editorial

UPD: I have found the problem. Sorry to bother.

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

Can someone explain why the second solution for problem A works?

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

    @spectre_gd I had the same doubt but I have figured it out while I was trying to contradict second solution approach. Go ahead post a test case(if you can find one) where this approach fails.

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

    imagine array as a mountain and we have two situations when traversing 2nd to 2nd last element: 1. we find element lower on left side and element lower on right side (we got answer) 2. we dont get element lower on left side (means our current element is lowest and array is descending upto current element so it cant be the peak), do the same thing on right side

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

    Second solution is based on negation of the problem. We are exploring those cases where answer does not exists and it will be when array is either non-decreasing or non-increasing. So, to break this condition, there must be local maxima i.e. an index j where both (j-1) & (j+1) elements are less. And this index is our answer!

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

Can someone explain in problem B why picking the greedy ci for the most frequent will somehow work for the rest of string?

How does that make sense? Can't there be a value in the string where ci fails?

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

    Your choice string is played agains the given string on every position. This means, all positions of the two Strings are paired once. Or, in other words, it does not matter in which order you put the symbols into the choice string.

    Since the order does not matter, every single position in your string conributes independend of any other position. Finally, for a single position it is obvious that the best choice is based on the frequency of the symbols.

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

    you have to understand that we are comparing each of element of s with c1 BUT we are doing the same thing with c2, c3, c4.... after just rotating the s

    for eg s = RSPRR R is most frequent so we choose P for c1 for most wins Now for c2 we are doing the same comparisons and P will give best result overall again (cause R is most frequest) so its basically the same

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

My Video Solution of B and C where i have tried to explain my thought process and why the solution worked .

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

n = 5, x = 10,

7 11 2 9 5

how can we choose 2 teams from this? shouldn't it be just 1 team cause min = 2 multiplied by 5 members = 10 so only one team?

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

    choose 1 member for one team....this team is formed only 11...bcz 11*1=11 > x... then choose 9 & 7 ..then you get min(9,7)*2=14>x... another way to choose is (11,9) & (7,5)

»
5 weeks ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it
hi,
problem D:
how to select a segment?
like for k=3,x=1,y=100,n=9
a=1,2,2,3,3,3,3,3,4
b=1,3,4
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is given that elements are distinct

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

      If the elements are distinct just suppose, then how we can solve it?

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

        I suppose it can be done in many ways. Store the index of each element occurring in a. Let's call it apos. Also make a copy of array a. Let's call it astrip (I know the naming is bad). Now while iterating with b, mark all positions in strip where this number occurred. astrip[apos[b[i]]] = some_identifier. Because all elements are unique, this'll work. Now just iterate through array astrip and figure out the segments. Along with this you also need to make sure apos[b[i]] > apos[b[i - 1]] because you want b to be a subsequence of a.

        86693530

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

      Elements are pairwise distinct. Doesn't that mean something like 1,2,1,2,1,2 could be a possible test case?

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

      my bad.... thanks all for responding.....

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

in question E merge towers: for the given test case [[5,1],[2],[7,4,3],[6]] are the towers before any query on merging tower 1 and 3 according to me it should be done like: from tower [5,1] ,1 goes to tower 3-> [5],[7,4,3,1] -> 1st operation from tower [7,4,3,1] , 1,3 and 4 goes to tower 1 -> [5,4,3,1],[7] -> 2nd operation from tower [5,4,3,1], 5,4,1 and 3 goes to 3rd tower -> [],[7,5,4,3,1] -> 3rd operation it can be done in three operation but it shows 5 as a result . Where am i wrong?

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

    Put some clothes on and format the question ;)

    The result must be one tower [7,6,5,4,3,2,1]. Somehow you are loosing the 2 and 6.

    The rule for merging is fairly simple: Take the top segment from the tower where the 1 is, and put the whole segment onto the tower where it fits. The moved segments in the example would be:

    [1]
    [1,2]
    [1,2,3,4]
    [1,2,3,4,5]
    [1,2,3,4,5,6]
    

    The last move creates the complete tower.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

We can also solve F by matrix-DP .. First we calculate the matrix for every dp transition .. then we just need the product of these matrices .. (To simplify append 0 at the begining and 9 at the end ) and build segTree in [0,n] and then remains only two point updates at index(x) and index(x-1) .. (Make sure to have dp[n+1]=1 (even if its nine ))

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Can someone explain C more elaborately?

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

.

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

In D problem, if the elements are not distinct then how we can solve it??

according to me.i think complexity will be >=qudratic

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

There's another solution O(n) for A.

  • As per the given condition, we can see that the element with value n will definitely satisfy this condition as middle element and the ends of the array as first and last element. (Because n will be bigger than anything and that's what we want here).
  • If n is at the ends of the array, then n can't be the answer. We ignore that element, update ends of the array and do the same thing again. The highest element in the array is now n - 1 and if it's somewhere in the middle, that should be the answer.
  • We'll keep trying the same for all elements and we'll know if the answer exists at all.

86668426

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

can anyone please explain what is this line doing in problem D solution res += (len - k) * y + x; . this line will be executed when we cannot perform berserk because one of the elements in segment is greater than both l and r and cost of berserk is lesser than fireball to delete everything. i thought this should have been res+=len/k*x so that we delete everything remaining using fireball. Thank you!!

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

    The tutorial does the operations in irritating order. However, if the biggest monster is bigger than l and r we need to use Fire at least once. And independend of anything else, we need to use Berserk on at least len%k elements. The order of these two operations or the others operations does not matter.

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

      thank you so much !! understood now

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

In problem C, I calculated minimum number of programmers required starting from programmer at position 'i'. This is will basically give me n (or less) segments. I then run an algorithm same as activity selection problem on this array of segements, to find the maximum number of teams. https://codeforces.com/contest/1380/submission/86686449 This comes out as wrong on test case 8. My answer is higher than the correct answer. I am not able to figure out why is this method wrong. Some help?

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

In problem G why can we ignore the initial order of chests and sort? I was thinking on a case like 4 40 400 400 600 and k=1. Where can I put the mimic so that the answer gives 330 (as it does with the editorial solution)?

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

    You misread the problem: "Print n integers — the k -th value should be equal to the minimum possible expected value of players earnings if the chests are placed into the rooms in some order and exactly k of the chests are mimics."

    "the chests are placed into the rooms in some order and exactly k of the chests are mimics." so you can choose any order.

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

In B ,what if there is an extra constraint that "You will lose point if the bot's choice is superior",So doing the same thing which we actually did for the original problem,would it be still optimal ?

For Ex :"RRSP" ,and output "PPPP",
Win(1),Win(2),Win(3),Win(4)= (+1)+(+1)+(-1)+(0) = 1;
Avg = 1
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is still the case that every position is played against any other position. So the order of the symbols in the choosen string does not matter. Since the order does not matter it is still optimal to use one symbol for the whole string. As a pragmatic solution, just try all three possibilities and choose the best.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Anyone please explain the update part in problem F .
how we are doing updates ?

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

Just curious:

Does there exist some kind of dp solution for D?

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

    Constraints are too high for a DP solution for problem C(assuming you mean by DP is to brute force and use dynamic programming to decrease number of total operations made).

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

    Disclaimer: It is a little messy because I tried to code as fast I could and submit it during contest.

    Here you go! 87810909

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

problem C is enjoyable

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

86766761 Can someone help me identify what did I do wrongly here on problem C?

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

    I didn't understand your code completely...

    You can see this one might be helpful 86676269

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

      I first consider all those with skill >= x because they can form independent group of size 1.

      I then have an array, say A, for the rest of those whose skillsets are strictly less than x, which means they need to team up with others to use the length of their team to compensante for x. I sorted this array A and loop it from the smallest value to the greatest.

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

      (continue from above) Within each iteration in my array A, I calculate the corresponding length that I need such that I can form a team by taking the ceiling quotient num = x/a (where a represents the element of A and num represents the required team length)

      # Example: Array A = [1,1,2,3,4], given x = 5

      In my first loop, num = ceil(5/1) = 5 (which is reasonable, given that I would need a team of length 5 to fit the team formation requirement)

      # So, if in my iteration I find that my array A has the length greater than or equal to "num", then my group count will += 1 and I will delete the partition of my array from the original.

      If in my iteration I realize that given the element, it is impossible to form such a team from my original array A, then I remove the element from my original array A.

      Now that I think of this logic again, I feel like in certain cases it might undercount. But for now the failing case that I have is that the solution is 0 and my code gives 1, which is an overcount

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

        I have applied part of your logic here 86781167

        But without using the ceil part, which is not needed.

        And if you think of it carefully you will realize that there is no need for deleting elements from array A, since you are iterating throw elements...

        Note that ceil won't be useful if it is used with integers, and it can sometimes cause some troubles if not used properly, so avoid using it as you can.

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

          Thank you, but I would be more enlightened if you could help me find what went wrong with my implementation or my thinking process

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

    If you start small, you are guilty of waste. M = 8, for example,,2,7,7,7,7,7,7 [1]; Instead of [7.7][7.7][7.7] [7.7] As for the answer greater than correct, if m=10,[4,4]; You only need 10/4=2, but (10/4)*2=8 does not equal 10

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

In C I miss read the question and was thinking that each team should have a product at least x. can anyone tell how to solve if this was the question ??

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

    In this case also, just sort the array and keep two variables. One containing the product of the present array and one containg the count of number of arrays. The code will look something like this: https://pastebin.com/zL2pxcfZ

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

      I don't think it's that easy. here is the testcase

      6 12
      2 2 2 10 10 10  
      

      answer : 3 your code output: 2

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

        Ya, it's not easy. Sorry for the wrong explanation. Need a better approach for this.

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

        I think the correct answer would be: 1. Because only the minimum element of the group and the size of the group matters. if I'm wrong I would be happy if u correct me.

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

Can anybody help me with Problem D Berserk and Fireball I am facing some implementation issues? My submission — 86799781 Thanks

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Do you really expect a meaningful answer to such a vague question?

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

      Can you help me with my submission?

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

        You noticed the diagnostics at the end of testcase 7?

        Diagnostics
        ...runtime error: addition of unsigned offset to 0x13201820 overflowed to 0x13201818...
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Haa But I couldn't make out the error like what does it mean?

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

            I cannot spot the bug either. But I see some ways to greatly simplify your code.

            Do not use a set for index. The values you are inserting are distinct and sorted, just use vector.

            Additionally put a -1 as first element into that vector, and a n as last. So you can delete the copy of the main loops body.

            The first loop where you collect index is unnice. Still not sure if there is an off by one somehow. You better loop over a[i] and check every index if a[i]==b[j]. If yes insert i and increment j.

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

how's solution of 1380A-Three Indices correct w O(n), as we don't know that those three will be the consecutive no.s.

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

    If there exists a solution then it is guaranteed that three consecutive numbers are definitely a solution otherwise, the solution doesn't exist. e.g.-> Consider array --> [3,1,4,2,5] one solution is i=1, j=3, k=4 but instead, to make the algorithm O(n) we are more interested in i=2, j=3, k=4

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

upd:done

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

pikmike can you explain what 0,1,2,3 represent in the solution of problem F. Thank you.

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

    0 = 00 — neither is taken
    1 = 01 — leftmost isn't taken, rightmost is taken
    2 = 10 — leftmost is taken, rightmost isn't taken
    3 = 11 — both taken

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

@pikmike Can you please explain me the problem -e test case when we merge the 3 and 1 tower how the ans coming out to be 4 instead of 3 . Ok I can tell you how i got 3.

1st tower contain — 5 1 and 3rd tower contain — 7 4 3

1st move — you shift (1) from tower 1 to tower 3 now 3rd tower contain — 7 4 3 1 and 1st tower conatin — 5

2nd move — you shift (4 3 1) from tower 3 to tower 1 now tower 3 contain -7 and tower 1 conatin — 5 4 3 1

3rd move — now you shift (5 4 3 1) from tower 1 to tower 3 now tower 3 contain — 7 5 4 3 1 and tower 1 conatin nothing .So my answer coming out to be 3 instead of 4 . I know i am missing something could you please point out.Thankyou.

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

    Reread the problem statement carefully.

    We are not calculating the number of operations needed to merge the towers in the query. Instead, after each query, we want to calculate the number of operations required to merge all current towers into one.

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

why I'm getting Time Limit Error at test set 6 ? https://codeforces.com/contest/1380/submission/86946265 can anybody explain? thanks in advance

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

I think, there is a mistake in editorial of the problem 'C'. There should be 'Non-increasing' instead of 'non-decreasing'.

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

In problem E it is not at all clear how to achieve these answers.

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

I have tried to make editorial for questions A-E . please have a look. Language :- Hindi

https://www.youtube.com/playlist?list=PLrT256hfFv5UUIBTJBUL7ZlZVHaWWEmGB

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

Was F inspired by this meme?