Блог пользователя awoo

Автор awoo, история, 5 лет назад, По-русски

1238A - Prime Subtraction

Идея: BledDest

Разбор
Решение (BledDest)

1238B - Kill `Em All

Идея: Neon

Разбор
Решение (Ne0n25)

1238C - Standard Free2play

Идея: adedalic

Разбор
Решение (adedalic)

1238D - AB-string

Идея: Roms

Разбор
Решение (Roms)

1238E - Keyboard Purchase

Идея: Roms

Разбор
Решение (Roms)

1238F - The Maximum Subtree

Идея: Roms

Разбор
Решение (Roms)

1238G - Adilbek and the Watering System

Идея: Neon

Разбор
Решение (Ne0n25)
  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

typo in D. (n-1)*n/2

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    No that's not typo .Total count of possible substrings is n*(n+1)/2 (including substring of length one)

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -33 Проголосовать: не нравится

      No, god. Please, no. No!!!

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        See , substrings of length 1 are bad , so they will be automatically counted in cntBad .So n(n+1)/2 is count of all substrings and cntBad = number of bad substrings .Hence n(n+1)/2 — cntBad is number of good substrings .For example consider "AAA" , here n(n+1)/2 = 6 and number of bad substrings i.e cntBad = 3 (Three substrings "A" of length 1 ) , thus total number of good substrings is 6 — 3 = 3 i.e the number we get after removing bad substrings from all possible strings .

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится -9 Проголосовать: не нравится

          We ignore them in the beginning, check the author’s solution.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            If we take total substring as n*(n+1)/2 then we have to initialize cntBad = n at first.

            And if we take total substring as n*(n-1)/2 then we have to initialize cntBad = 0. Authors solution took cntBad = 0.

            So both are right.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится -25 Проголосовать: не нравится

Problem A Challenge: Assume, that you can substract a prime from x at most 3 times.

Solution
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I couldn't understand the explanation of problem C. Can someone describe it?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    For explanation I'm using a test case:

    9 8 5 4 3 1

    Do you know what does this mean? Let me explain. It means that the height of the cliff is 9. So initially at 9, there is a platform where the player is standing. At height 8 there is a platform too. But at height 7 and 6 there is no platform by now. And then at height 5 and 4 and 3 there we have platforms at a stretch. Height 2 have no platform. Height 1 has platform.

    At first you are at the highest point means at 9. From here we'll will see three kinds of moves. Let's see those:

    Case 1: Do both of the next two height have platforms? If yes, then we can and should move to the second using 0 crystal.

    Case 2: Do the next height have a platform? if yes, then it is optimal to move to that next height using 1 crystal.

    Case 3: Now it means that there is at least one gap between now and the next platform. It doesn't matter if there is one or multiple gap. You can move to the very last gap using no crystal that means 0 crystal.

    Now solve our test case: 9 8 5 4 3 1.

    We are now at 9. Here we see case 2 because only the next height 8 has a platform. So we move to 8 using 1 crystal.

    So now we are at 8. Here we see case 3 because we have gap at heights 7 and 6. So we move to 6 using 0 crystal.

    So now we are at 6. Here we see case 1 because both of the next two heights 5 and 4 contains platform. so we move to height 4 using 0 crystal.

    So now we are at 4. Here we see case 2. So we move to height 3 using 1 crystal.

    So now we are at 3. Here we see case 3. So we move to height 2 using 0 crystal.

    Now notice one thing. At Ground that means at height 0 we can assume that there is always a platform but it doesn't move at all. Because it's ground :D

    So now we are at 2. Here we see case 1. So we move to ground using 0 crystal. So in total 2 crystal is used.

    We need a crystal only when we meet case 2.

    I hope you understand.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hey MubtasimShahriar! Could you please explain me the output of : 100 1

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Move from 100 to 2 using no crystal at all. From 2 you can move to ground that means to level 0 using 0 crystal. No crystal is used at all.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't understand that why are you going to 8 from 9 and not on 7, I mean we can use a crystal to change the state at height at 7 and then use a normal operation, I UNDERSTAND THAT YOU WROTE IT LONG TIME AGO, BUT PLEASE TRY TO EXPLAIN

»
5 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

In problem D is tagged as DP .Can some one tell the method to solve it using DP ? We can calculate bad strings using 4 different for loops (corresponding to type of bad string) , any other method to do that with less typing ?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

For problem D, how can there be only 4 patterns? For example the string $$$ABBAB$$$ is also a bad string but its pattern is not the same as the 4 given patterns.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraints are really deceiving in E. Could somebody explain an O($$$a*2^a$$$) solution?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The $$$a^2$$$ factor inside the dp is for computing the sums of $$$cnt_{x,y}$$$ for $$$x \in mask$$$ and $$$y \not\in mask$$$. You can improve this with sos dp, for each mask you compute how much should be added to.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The standard dp sos i'm thinking about is $$$a2^a$$$ for each character, which makes it $$$a^{2} 2^a$$$ in total. Could you explain further the recurrence of your dp?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    If you calculate the cost in $$$DP$$$ by using the newly added letter's position:

    Let $$$co[i][j]$$$ be the number of times letters $$$i$$$ and $$$j$$$ appeared next to each other. You can build an array $$$arr$$$ where $$$arr[i][mask]=\sum_{k\in mask} co[i][k]$$$ in $$$O(m*2^m)$$$, by using this trick: $$$arr[i][mask]=arr[i][mask\oplus 2^j] + co[i][j]$$$ for $$$mask>0$$$, where $$$j$$$ is any set bit's position in $$$mask$$$ (can be the lowest significant bit for example).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    We can solve 1238E - Keyboard Purchase in O(m.2^m), too!

    Denote dp[mask] as the minimum cost of arranging x's in mask on the keyboard when all of the y's not in mask are on the first key of the keyboard (all of them!). And denote sum[c][mask] as the number of positions that c and x's in mask are adjacent.

    You can easily see that:

    sum[c][mask] = sum[c][mask-lowbit(mask)] + sum[lowbit(mask)] (But you have to fill sum[c][2^x] before this by counting adjacent c's and x's in string)

    and

    dp[mask] = min(dp[mask-2^c])(for all c's in mask) + sum[x][2^m-mask-1](for all x's in mask).

    Here is my code: 62207715

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You're welcome! :)

        But in my code I just used another for in calculating my dp every time I fix the c, so my code order is O(m^2.2^m), too! but you can easily change it.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Problem D, I'm having trouble counting the number of such substrings. I read a lot of different codes but I don't seem to get it. Can somebody please explain their own method to me? Thanks a lot in advance.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    let our string is AABBAAABAA here we have to find answer for AABB and BBAAA and AAAB and BAA. total of there will be answer for our string . And answer for string AAABB will be 3+2-1. We are subtracting 1 because we are adding the conjution (AB) twice . so answer for string AABBAAABAA will be (2+2-1)+(2+3-1)+(3+1-1)+(1+2-1)=12.

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

A proof for why the greedy algorithm works in $$$C$$$:

First note that for any $$$v>1$$$, you have to stand on at least $$$v$$$ or $$$v-1$$$, because if you didn't stand on both this means that you descended from $$$a>v$$$ to $$$b<v-1$$$, which means you are dead.

You are initially standing at $$$h$$$, assume you will walk without any crystals until you first reach that $$$x>2$$$ where $$$x-1$$$ is moved out and $$$x-2$$$ is hidden. Now you must use at least $$$1$$$ crystal to continue. You can use it either to:

  1. move out the platform at $$$x-2$$$, then descend to it directly.
  2. hide the one at $$$x-1$$$ and move to it, where you will still have the opportunity to continue to $$$x-2$$$ without extra crystals, so this option is better.

The other scenario you can follow starting from $$$h$$$, is that which would end on $$$x-1$$$ (without going to $$$x$$$), and this scenario will cost at least $$$1$$$ crystal. So we deduce that the best option is option $$$2$$$ in the previous scenario. Starting from $$$x-1$$$, you can continue to use the same followed logic starting from $$$h$$$.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem E, when iterating to new character x then how we calculate dp[mask|(1<<x)] ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have tried an O(m^2*2^m) solution for problem E but it is giving TLE.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I cannot understand the solution of problem E. Specially, **" If letter y is already on current keyboard, then we should add to answer cntx,y(posx−posy), and cntx,y(posy−posx) otherwise" **sentence. Why should we consider abount the letter which is not included in the keyboard?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I cannot understand the solution of problem E. Specially, "If letter y is already on current keyboard, then we should add to answer cntx,y(posx−posy), and cntx,y(posy−posx) otherwise" sentence. Why should we consider the letter y which is not included in the keyboard? And on last formula,∑y∈msk(cntx,yposx)−∑y∉msk(cntx,yposx), why there is no posy? Where do they go?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I cannot understand the solution of problem E. Specially, "If letter y is already on current keyboard, then we should add to answer cntx,y(posx−posy), and cntx,y(posy−posx) otherwise" sentence. Why should we consider the letter y which is not included in the keyboard? And on last formula,∑y∈msk(cntx,yposx)−∑y∉msk(cntx,yposx), why there is no posy? Where do they go?

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Can any one explain how to solve D if there are 26 character?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain how to solve D with 'binary search'?

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve D using DP?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Just a side fact: The resultant tree that gets formed in the problem F is also called Caterpillar Tree.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can someone please explain the structure of tree formed in problem F? I didn't get it from editorial completely.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you for your reply! But I am asking can you please explain how we land on this structure?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        One major point here is that an integer can't be contained in three or more segments, since that would correspond to a cycle in the described graph, but we're given a tree, so that's ruled out. With this knowledge, let's construct some intervals so that we can maximise the number of intervals. We'll try to have two segments containing an integer as long as it is possible, since we're trying to maximise the size of the required subgraph.

        So we have a continuous sequence of intersecting intervals, and then for points that are not yet covered by two intervals, we're trying to find as many non-intersecting intervals as possible to cover those points (you may even think of them as degenerate intervals, where l = r, if you want, since we're free to size our intervals as we please). The only thing that limits us is the given tree, where the smaller intervals can only be as many as the count of neighbours except the next interval in the path. I hope you see why this is optimal, and why this would correspond to the caterpillar graph.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is there a "Binary Search" Tag on Problem D? How to solve it using Binary Search?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to understand the meaning of the dp array in E problem?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem fixed.

Sorry for inconvenience.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Read the statement carefully.When you will explosion on x=3 you will get 6 7 7 7

    Then every monster is either killed by explosion or pushed away.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    if you'll fire at c=3 then positions will become 6,7,7,7

»
5 лет назад, # |
Rev. 6   Проголосовать: нравится +5 Проголосовать: не нравится

awoo, in problem E, could you explain how you arrived at the final formula

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can Someone Explain What d[M][N] represents and how we used it to calculate dp[M] in the editorial for problem E?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please share some way to actually count the number of good substrings(not negating bad substrings), just curious!!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Doubt in problem E.

Hi, i have a question about why my code didn't get TLE.

My idea:

Imagine the graph with letters as nodes and weighted edges (the weight of an edge is how many times the node u came right before node v or node v came right before node u in the string).

I used the fact that |a-b| = max( a,b ) — min( a,b ).

So i started selecting the letter (or node) with the position $$$N$$$, the the letter with position $$$N-1$$$ and so on, obviously taking care not using a node twice. And with this in mind a node $$$u$$$ will add (its postion) times (the sum of the edges from that node to the rest of the nodes that have not been selected yet) — (its position) times (the sum of the edges from that node to the rest of the nodes that have been selected ).

I did this but i think that the complexity is m^3 * 2^m which is somethig like 8*10^9 worst case.

Could someone explain me why this solution passed?

My code: 62655475

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem D, what is the role of x in res-=cur-x. For the first iteration of the loop we check for strings that end with AAB or BBA. And for the second iteration we check for strings that start with ABB or BBA. Why subtract x=1 from res ? Got it.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain the intuition behind problem E and can anyone please give some tips to improve bitmasking.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Random solution to problem F gives ACC, is it because test cases are weak? 63616653 I just choose 20 nodes at random plus the center(s) of the tree, and for each of them run the same dfs assuming that answer pass through it. Can someone tell the probability of choosing a vertex and it belongs to an answer? I know it's something like ANSWER / N.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose we have a tree with $$$\sqrt n$$$ branches of length roughly $$$\sqrt n$$$, where two of the branches are a bit longer. Then, the answer contains roughly $$$3\sqrt n$$$ vertices, so the probability of choosing a node that is part of the best subgraph is roughly $$$3 \sqrt n / n \approx 0.005$$$ for $$$n=3\times10^5$$$. If you choose 20 nodes at random, then the probability of failure is roughly $$$0.995^{20} \approx 0.89$$$, so this solution shouldn't pass.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

would someone plz answer my question ??

In problem B, tutorial's time complexity is O(n * logn) in every query. so i think total time complexity of the algorithm is O(q * n * logn).

https://mirror.codeforces.com/contest/1238/submission/64450447 — this is my code. my time complexity is O(n+log n) ~ O(n) in every query. so i think total time complexity of my algorithm is O(q*n).

my question is why the tutorial's code passed but mine couldn't passed?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wait, in problem B if the complexity in each query is O(n log n) then does that mean the whole problem will be O(q*n*logn), how does this still work with q <= 1e5?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Read the constraints. It is clearly written — "It is guaranteed that sum of all n over all queries does not exceed 10^5.". Thus the time complexity is O(q*n*logn) but q*n<=1e5.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why am i getting TLE in B ?
Do read the blog first .
Because the reason behind TLE is strange link to the blog is here...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraints on E is unecessarily too tight, usage of long long gives TLE