awoo's blog

Educational Codeforces Round 137 Editorial
By awoo, history, 2 years ago, translation, In English

1743A - Password

Idea: fcspartakm

Tutorial
Solution 1 (awoo)
Solution 2 (fcspartakm)

1743B - Permutation Value

Idea: BledDest

Tutorial
Solution (BledDest)

1743C - Save the Magazines

Idea: fcspartakm

Tutorial
Solution (awoo)

1743D - Problem with Random Tests

Idea: BledDest

Tutorial
Solution (BledDest)

1743E - FTL

Idea: BledDest

Tutorial
Solution (awoo)

1743F - Intersection and Union

Idea: BledDest

Tutorial
Solution (BledDest)

1743G - Antifibonacci Cut

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +123
  • Vote: I do not like it

Comments Comments (66)
| Write comment?
»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Thanks this round, I'm Master again!!!

Most problems are interesting and educational!!!

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

Great problems and nice editorial!

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

Gready-Bruteforce Solution 176908398

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

There is an easier solution in F. For fixed integer x lets calculate dp[i] as amount of sets that include x formed with first i segments. Transition:

  1. x < l[i] or r[i] < x => dp[i] = dp[i — 1] * 2 (last operation is: union => dp[i — 1], intersection => 0, difference => dp[i — 1])

  2. l[i] <= x <= r[i] => dp[i] = 3 ^ (i — 2) * 2 (last operation is: union => 3 ^ (i — 2), intersection => dp[i — 1], difference => 3 ^ (i — 2) — dp[i — 1])

Let ind[x] be index of the last segment x belongs to. dp[n] for x can be calculated for O(1) as 3 ^ (ind[x] — 1) * 2 ^ (n — ind[x]). ind[x] is calculated for O((n + M)logn) using scanline. My solution: 176763501

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

    I did something similar (after the contest) but didn't use dp at all.

    I iterated through all values up to 3*10^5 keeping track of all currently active sets (sets that go through that point) and then for each point I would, with a heap, find the index of the set with the highest index and apply the same formula as you (3 ^ (ind[x] — 1) * 2 ^ (n — ind[x])).

    My solution: 998244353 *176949836 (oops)

    (The heap implementation isn't the best and also it's a min heap, when I actually needed a max heap, but I was to lazy to get a max heap, so instead I just did some changes in other places of the code so that it worked with a min heap)

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

      When I just saw your submission link I thought "wait is that submission no. really that famous prime number?" and realized its just a link that looks like a submission markdown LOL

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

        Haha, hadn't realized, I copied the wrong number

        → Reply
»
2 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Print the maximum possible value you can get in binary representation without leading zeroes.

BledDest

This is not the answer that your code gives in some tests.

This is same as: "I only want people with similar solution to mine pass and the rest fail".

https://codeforces.net/blog/entry/108148

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

    Does it mean that in any question, I can write a solution which works lets say 0.78657 of time ?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      By saying that, you're undermining the usefulness of any non-deterministic/approximation algorithm.

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

        Yes, Im. But im saying that only in CP. Bcz here if your solutions get unlucky 1 times out of 40 and you print wrong answer, and judge doesnt care about your solution and say "its WA, its completely wrong"

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          You might think scoring on a per-TC factor might be a solution. But trust me, this isn't going to help. I've seen one competition score participants on a per-TC factor, turned out everyone snatched 50/100 score on a problem where the output is a single line of Yes/No.

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

    This is not the answer that your code gives in some tests.

    I'm not sure what you mean by this. The editorial solution (and most, if not all, of the AC solutions, I'm pretty sure) is 100% deterministic and is guaranteed to give the correct answer (which is always unique) 100% of the time. Any solution that finds the correct answer in $$$O(n)$$$ expected runtime would pass, even if the approach is very different from the editorial solution. The output will always be the absolute maximum possible value (in binary, with no leading 0s) no matter what.

    Now, it is possible to get an AC with a solution that doesn't guarantee the correct answer, but (a) that's not what the editorial solution is doing, and (b) it should still be accepted in the context of the problem design. Here is an example of an elegant 5-line solution (not mine) that looks nothing like the editorial solution, but it still definitely deserves its AC with respect to the problem design imo: 176783281

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

    Show me any such test.

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

      By saying that, I meant a solution can get very unlucky, and fail(work too slow, etc (Basically not getting AC)). Like you mentioned in editorial, its rare that 20 ones come repeatedly(as I see your solution depends on this fact), But what if generator gives such a case that your solution works slow.

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

        I am sure that any reasonable implementation of the solution can handle a block of size up to $$$100$$$ ones, not $$$20$$$. The probability of the first block being longer than $$$100$$$ is about $$$2^{-100}$$$. A meteor hitting Earth and imploding CF servers is more probable to make the solution get rejected than this thing.

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

        I think it's more likely that somebody would hack into the Codeforces system undetected and modify the tests to make incorrect solutions pass and/or correct solutions fail. If you want to be intellectually consistent, why don't you start screaming about how we should not have automated testing anymore? Please volunteer to manually scan every character of every test in every submission for this contest to help ensure its absolute integrity.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 4   Vote: I like it -8 Vote: I do not like it

          Please volunteer to manually scan every character of every test in every submission for this contest to help ensure its absolute integrity.

          Nah, the chance that he will misjudge one half of all submissions is absolutely higher than the chance that a reasonable solution will fail the tests on the problem.

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

    The fact that you think this just means you don't understand the point of probabilistic approaches, and more to that point, of CP itself.
    Plus I'm pretty sure your contribution agrees with me

    → Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I spent the entirety of the round trying to solve D with XOR instead of OR -> -108

One of my most embarassing moments ever on a codeforces contest. And here I thought I had already taught myself well enough not to rush through statements. Such a simple problem, had I just read it right :/

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

    Thanks for the comment, for last half an hour I was also thinking of xor. At first i thought you did a typing mistake an replace xor with or lol.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

My approach for B was simply to have 1 and 2 at the two opposite endpoints. Any permutation of size $$$\geq 2$$$ needs both 1 and 2, but now the only way to include both would be to take the entire array.

Problem D is the first time I encountered a Codeforces problem where the runtime analysis depended on input distribution. I like this idea, and would want to see more of this kind, since I think it's quite a refreshing change from the usual scenario of considering only the worst-case, and this expected runtime analysis is also very relevant for practical applications.

I really like Problem E; very simple to understand, no unnecessarily complicated factors in the description, yet creative enough to require an interesting approach (imo) while the natural greedy ideas that would first come to mind end up failing.

I also like that Problem A is actually easy enough to hopefully not invoke ragequits and/or demotivate participants from their struggles with it, unlike some of the other recent contests.

Overall, great contest! Thank you!

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

    In problem D if we have first '0' at 10-5 or 10-6 position so the block of '1's becomes of huge size and we run into O(n^2). How is it possible that the probabiliy that its length is 20 or bigger is about 10−6, so the expected number of prefixes we need to check is also O(1). Thus, the expected runtime of our solution is O(n)

    Please explain

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

      Let's ignore the leading 0s, and consider the first 1. What is the probability that there are no 0s in the next 20 indices? Well, the probability that the next index is non-zero is $$$1/2$$$, and then the probability that the index after that is non-zero is also $$$1/2$$$, and so on. So the probability that these 20 indices in a row are all non-zero is $$$\underbrace{1/2 \times 1/2 \times \cdots \times 1/2}_{20 \text{ terms}} = (1/2)^{20} = 1/1048576 < 10^{-6}$$$

      This is already very unlikely to happen. And even if it does happen, there are still further circumstances that need to arise for a TLE, depending on the algorithm. For example, if you disregard a starting position as soon as you find it to be inferior to the current best starting position, then we'd expect that most of these bit positions would not actually have to visit all 0s, so there is still a decent chance that we'd fall under the time limit.

      We'd need to be incredibly unfortunate to not only have a lot of 1s lined up, but also that actually checking each of these 1s as a starting position ends up having to visit a significant enough portion of the string that the total runtime ends up exceeding the relatively generous 4-second limit. I think the probability of this happening is far lower than the probability that say, your computer dies or your network crashes or some technical glitch leads to a rejected verdict. And so far, I haven't seen anyone post such an unfortunate verdict that arose under such incredibly low odds in an algorithm that would have been expected to pass with such a high probability, and I personally very much doubt this would happen in the next 100 years.

      → Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Ouch I have known everything in the tutorial of prob D, except thinking of tests are generated randomly… Actually I noticed that, but I did not care because I did not think it can be a critical information. I guess over half of participants who did not finish prob D have the same reason to me

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

    Sounds so true!

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

    I hope that teaches you the importance of upsolving. 1729E - Guess the Cycle Size from Codeforces Round 820 (Div. 3) was based on the same idea. Had you solved that question, you could have solved this easily. Cheers :)

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

      Not true, I had solved 1729E during contest, but couldn't solve 1743D :( Here's my submission 1729E

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

    Pro tip: Any constraints or information mentioned about the inputs is important. It depends on the author, sometimes they mix it in right along with everything else, maybe in the hopes of some people missing it, sometimes it's mentioned separately in it's own section and written in bold.
    It could be equally important in both cases but if it's in bold it's definitely important

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

    +1

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

Finally BLUE!

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

Very easy solution for E:

Let dp[h] be a vector with all possible pairs (x1, x2) so that the first gun is ready at the moment x1, and the second — at x2.

Iterate over enemy's hp, for all pairs (x1, x2) for the current hp update the future dp values. There are 3 transitions: shoot the 1st gun, the 2nd gun and both.

The number of pairs (x1, x2) for certain hp may be very large, so notice that we have no interest in (x1, x2) if there exists (y1, y2) and y1 < x1, y2 < x2. Drop bad pairs. Now their number magically becomes very small (no proof) and you get AC in 15 ms.

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

    Can you explain this test case:

    input:

    3 19

    4 29

    11 2

    correct output:

    67

    upd: like what sequence leads to the correct output?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      1. Monocarp waits for the first laser to charge and shoots it -> durability euqals 10 at t = 19
      2. Monocarp waits until both lasers are charged and shoots them at the same time -> durability equals 5 at t = 38 = 19+19
      3. Monocarp repeats step 2 -> durability equals 0 at t = 67 = 38+29

      (A single shot of the first laser deals 1 damage and a double shot deals 5 damage)

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

      at time t = 19 first 1 laser damage = 1 at time t = 38 fire both laser together damage = 1 + 5 = 6 at time t = 67 fire both laser again damage = 6 + 5 = 11

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

    The situation looks quite similar to 1612F - Armor and Weapons. Maybe a similar analysis could be possible?

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

    Nice approach, thanks! I wonder if there's a proof that the number of elements in these filtered (x_i, y_i) sets is small.

    Note: A little mistake in transitions and this solution may be slow again. I see your solution uses e.g. a transition (x1, x2) -> (x1 + t1, max(x1, x2)) which is a bit of a magic... Making it (x1, x2) -> (x1 + t1, x2) will cause TL.

    As far as I see the correct one would be (x1, x2) -> (x1 + t1, x2) only if x1 < x2. And this is the only case we should fire this specific transition. Same logic goes for the transition when only second gun fires. Transition with both guns firing is always allowed. So for each (x_i, x_i) state there are at most two transitions.

    Well, what if (x1, x2) -> (x1 + t1, max(x1, x2)) and x1 > x2. We get into (x1 + t1, x1) but fire only first gun at x1 and we're ready to fire second gun at x1. That is correct, but the fact that we actually must fire it is dropped. Suppose making that transition again -> (x1 + t1 + t1, x1 + t1). It's ok but we only fired first gun and the second was just skipped, but in general it seems like there may be no way to get into that dp state since the problem statement does not allow to fire one gun when both are charged and the second to just wait.

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

Can someone share the DP solution for C. Save the Magazines ?

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

    Define $$$dp_{i,j}$$$ as the maximum number of magazines we can save upto index $$$i$$$, where $$$j=0$$$ if the current box does not have a lid on it, and $$$j=1$$$ if the current box has a lid on it.

    The transitions can be formulated in the following manner:
    - Case 1: $$$s_i=0$$$, which means this box does not have a lid on it. Here, $$$dp_{i,1}=0$$$ because there is no way for us to have a lid on this box, and $$$dp_{i,0}=max(dp_{i-1,0},dp_{i-1,1})$$$, since we can consider either of two cases for the previous box and take the maximum number of magazines saved either way.
    - Case 2: $$$s_i=1$$$, which means this box has a lid on it. Here, $$$dp_{i,1}=max(dp_{i-1,0},dp_{i-1,1})+a_i$$$, since we can consider either of two cases for the previous box, and we are also saving the magazines of the current box. But in case this box were not to have a lid on it, then we must pass on the lid of this box to the previous box. Thus, $$$dp_{i,0}=dp_{i-1,0}+a_{i-1}$$$, since we are considering the case when the previous box does not have a lid on it, and adding the number of magazines of the previous box to our current dp state, since the previous box now does have a lid on it.

    Our answer is $$$max(dp_{n,0},dp_{n,1})$$$.

    C++ code.

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

    I have not standart one, but there it is.

    1. Let's say, $$$dp[i][0]$$$ is the maximum sum when the element $$$i$$$ has $$$0$$$ lids, $$$dp[i][1]$$$ the element $$$i$$$ has $$$1$$$ lid, $$$dp[i][2]$$$ the element $$$i$$$ has $$$2$$$ lids, and the extra $$$dp[i][3]$$$ the element $$$i$$$ has $$$1$$$ lid and we can not move this lid (the case when we move the lid to this element from right).

    2. Now, let's count DP from right to left (from $$$n$$$ to $$$1$$$) if $$$s[i] == 1$$$, we can have $$$1$$$ lid or $$$2$$$ lids on this box, so $$$dp[i][1] = max(dp[i + 1][0], dp[i + 1][1], dp[i + 1][2], dp[i + 1][3]) + a[i]$$$ and $$$dp[i][2] = max(dp[i + 1][1] - a[i + 1], dp[i + 1][2]) + a[i]$$$, why we sub $$$a[i + 1]$$$, beucase $$$i+1$$$-th box had $$$1$$$ lid and we removed it, so we have to minus $$$a[i + 1]$$$.

    3. For $$$s[i] == 0$$$ the situation is almost the same, $$$dp[i][0] = max(dp[i + 1][0], dp[i + 1][1], dp[i + 1][2], dp[i + 1][3])$$$ just get the best value. $$$dp[i][3] = max(dp[i + 1][1] - a[i + 1], dp[i + 1][2] + a[i]$$$.

    4. Answer is $$$max(dp[1][i])$$$ for $$$i\in{0,1,2,3}$$$

    https://codeforces.net/contest/1743/submission/176734080

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

Any idea for problem D considering the worst case, not just random test cases?

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

    You could view it as searching for a longest match to a pattern with single-character wildcards, e.g in second example you want to search for "11?1":

      1110010
     11?1

    For exact matches, there's O(n log n) FFT-based algorithm, basically by expressing matching as a convolution. Here we rather need longest prefix match to it, so you could slap a binary search on top of it to get something like O(n log^2 n).

    Suffix trees could be used for wildcard matching but afaik too slow at O(n * <number of wildcards>)

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

      hey is it possible to use LPS array with some kind of custom compare between current element and prev element to search max prefix match

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

Shorter implementation of D

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    string s = ""; cin >> s;
    string ans = s;
    for(int i=0; i<min(n, 30); i++) {
        string t = s;
        for(int j=0; j<n-i; j++) {
            t[i + j] = max(s[j], s[i + j]);
        }
        ans = max(ans, t);
    }
    int i = 0;
    while(i < n-1 && ans[i] == '0') i += 1;
    cout << ans.substr(i) << "\n";
    return 0;
}
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your logic of D's solution

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

      We can see testcases are generated randomly so probability of k consecutive 1's is 1/2^k, let's say k = 30 in almost impossible scenario. Why is this important? We can brute-force on length of s2 which we will see later.

      Now we want two sub-strings let's say s1 and s2, my hypothesis is choosing s1 = s gives best result always! Why? Because we can always choose s2 in such a way that s1|s2 is the answer.

      How to choose s2 ?

      Let's say s = 1110010, s1 = 1110010, s2 = ?, now we will use sliding window approach.Let's choose s2 of length from n to max(0, n-30)

      So we get

      s1 = 1110010 s2 = 1110010 ans = 1110010
s1 = 1110010 s2 = 1110010 ans = 1110010
s1 = 1110010 s2 = 1110010 ans = 1110010
s1 = 1110010 s2 = 0111001 ans = 1111011
s1 = 1110010 s2 = 0011100 ans = 1111110
s1 = 1110010 s2 = 0001110 ans = 1111110
s1 = 1110010 s2 = 0000111 ans = 1110111
s1 = 1110010 s2 = 0000011 ans = 1110011
s1 = 1110010 s2 = 0000001 ans = 1110011
s1 = 1110010 s2 = 0000000 ans = 1110010

      Here, we can see we are checking all the best options for s2. Thanks :)

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

For problem C because we can move the led once just go from right to left and when we counter 0 add sum — min And reset

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

I did AC C in the contest but then I got TLE test 22 and then I submitted that code and I got AC. My complexity is O(n). my code: https://ideone.com/uYgSAB. Help me!

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

    check how you initialize dp array. you use N value instead of n. and every test case you clear this array. so your time complexity is (t*N)=2*10^9 ops

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

For me, E's solution code is pretty hard to understand. I guess the code

if (ni == h)
	ans = min(ans, dp[i] + j * ts[k]);

is for the case "the last shot before destroying the ship wasn't a double one"?

And for the interpretation of dp[i]: the smallest time needed to destroy i where at the end the shot must be double. So before the last shot anything could happen. Then by analysis we conclude "between two double-shots there is no need to wait except for waiting for the double shot", which intuitively makes sense but I don't have a rigorous proof for this.

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

There is an easier solution for F.For each element x between 0 and 300000,the contribution of the element is only related to the latest position that x is included in the set,no matter how many times x have appeared in previous sets.It can be proved that if the last set which includes x is the ith set,the contribution of x will be pow(3,i-2)*pow(2,n-i+1),except the 1th set which is pow(3,i-1)*pow(2,n-i) (or pow(2,n-1))

So we can simply use a segment tree to implement interval assignment and solve the problem in O(M+nlogM) time.

Solution -> 176975490

Proof:If there exist m ways of the previous k operations that x is inclueded in the current set,if x is included in the next set,there will be pow(3,k) ways that the next operation is and,creating m sets which include x,there will be pow(3,k) ways that the next operation is or,creating pow(3,k) sets which include x,there will also be pow(3,k) ways that the next operation is xor,creating pow(3,k)-m sets which include x,so the total number of sets which include x will be 2*pow(3,k).It is not related to m.

Otherwise,if x is not included in the next set,if the next operation is and,no set will include x,if the next operation is or,m sets will include x,if the next operation is xor,m sets will include x,so the total number of sets which include x will be m*2.

In conclusion,the total contribution of x is only related to the last position x appeared in the set.

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

Why do we need to add extra "0" to the start for C.Save the magazines problem?

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

    By adding an extra "0" to the start, it becomes possible to use the greedy algorithm from the beginning even when the string starts with a "1".

    You could also add all the folders to ans untill you encounter the first "0", but this trick makes the code slightly shorter.

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

I did not understand the proof of why the two strings which are taken have to be prefixes only S = 1111001101 s1 = S let us take s2 = s[2 , 7 ] then s1 | s2 will be maximized as all the 0's will be 1 now in s1

but the prefixes , wont be able to do so .

I am surely missing something .

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

    The corresponding prefix is s2 = s[0,7] which will also give the same s1|s2 value here.

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

      So , will it create a problem if we take suffixes?

      Are these two different things KFPanda

      Sorry for directly asking you as I was also thinking the same as the above guy.

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

        Taking prefixes only makes the number of possible (with unique value) s2's less. Hence you need lesser computation to find the optimal s2, hence better.

        → Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it +18 Vote: I do not like it

Another insight on G that I found experimentally: the string $$$f_i$$$ can only appear up to $$$\frac{n}{\lvert f_{i-1} \rvert}$$$ times in a string of length $$$n$$$.

I found this by checking for which $$$l$$$ the prefix of $$$f_i$$$ of length $$$l$$$ is equal to the suffix of the same length. It seems this is the case iff. $$$l \in [\lvert f_{i-2} \rvert, \lvert f_{i-4} \rvert, \lvert f_{i-6} \rvert, \dots]$$$. Thus, whenever $$$f_i$$$ appears in a string, the next appearance must be at least $$$\lvert f_i \rvert - \lvert f_{i-2} \rvert = \lvert f_{i-1} \rvert$$$ characters further to the right. It might be possible to formally prove this, but my brain is way too fried right now to attempt it.

With this, we can almost implement the basic dp solution mentioned in the editorial. We can use string hashing to quickly check which $$$f_i$$$ end at an index $$$j$$$. To subtract the value of $$$dp_{j - \lvert f_i \rvert}$$$, we can use a different strategy for long and short $$$f_i$$$. If we consider $$$f_i$$$ up to length $$$N$$$ short, we keep a history of $$$N$$$ dp values to find $$$dp_{j - \lvert f_i \rvert}$$$ for short $$$f_i$$$. For longer ones, we know that the total number of their appearances is quite low, and thus also the number of indices $$$j - \lvert f_i \rvert$$$. We can find these indices using preprocessing and then keep their dp value around, for example in a map. See 177351187 for my solution which uses $$$N = 100$$$.

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

    I also used that idea in my solution, but implemented it in an even more straightforward way. Maintain a queue of updates for each fib string. When there is an occurrence of $$$f_k$$$ from some position $$$i$$$ forwards, push an update $$$i + F_k$$$ to tell it to subtract $$$dp_i$$$ from there. There can be at most $$$F_i$$$ updates in the $$$i$$$-th queue, and that idea tells us that there can't be more than $$$\frac{n}{F_{i-1}}$$$ updates there as well. So all queues can't grow too large.

    Also, don't use hash, just compare naively. It'll break quite fast if it's not an occurrence (the same idea helps). The solution itself.

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

Nice contest

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

    bro i can't reply to you, i'm a new user

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

awoo and BledDest can any of you please explain this part of the editorial of the 1743E - FTL:

Spoiler

Can not we calculate the time with like PUSH DP like :

DP[i+damage of 1st laser] = min(DP[i] + reload time of the 1st laser, DP[i+damage of 1st laser]

and similarly other two DP states

What's wrong in this thought process AND IF YOU CAN PLEASE REPLY IT WILL BE VERY HELPFUL sir

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

I have a slightly different (more like, improved) solution for G and it is currently by far the fastest one (77ms), so I want to share my approach. The idea is to compute, for each prefix of the entire concatenated string, the largest Fibonacci string that is its suffix. This uniquely determines all Fibonacci strings that are its suffixes: If $$$f_i$$$ is a suffix, then $$$f_{i-2}$$$ is also a suffix, and $$$f_{i-4}$$$ by induction, and so on. Also, it means that none of $$$f_{i-1}, f_{i-3} \ldots$$$ can be suffixes because they end in a different character ($$$f_i$$$ ends with $$$i \mod 2$$$). All this data can be stored in 3MB. The idea to compute the DP in under 1MB is to create a map $$$Mp$$$ which will keep the DP values for all indices $$$j$$$ such that there is a large Fibonacci string (say, over 100000 characters) starting at $$$j$$$. There cannot be many such indices. We also keep the last $$$2^{17}$$$ DP values in a circular buffer. This information is now enough to compute all DP values sequentially. Time complexity is exactly $$$O(N \log N)$$$ unconditionally. The only thing I didn't prove is that $$$Mp$$$ will have few elements, but it makes sense, as Fibonacci strings can't overlap arbitrarily.

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
for D: I made sol in order(n) that works in any cases in problem test cases or outside test cases... without being aware of cases that don't depends on probability of 1's or 0's or test cases that not in the problem..

the sol depends on the distance between position of zeros in initial string after the first block of 1's

my submission

→ Reply