ch_egor's blog

By ch_egor, 4 months ago, translation, In English

Thanks for the participation!

1492A - Three swimmers was authored by meshanya and prepared by ch_egor

1492B - Card Deck was authored by Noam527 and prepared by ch_egor, adedalic

1492C - Maximum width was authored and prepared by Jatana

1492D - Genius's Gambit was authored by voidmax and prepared by rip

1492E - Almost Fault-Tolerant Database was authored by wrg0ababd and prepared by Sehnsucht

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +221
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Why was B unusually hard for me?

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

    Actually something greedy works for B and that is quite intuitive from test cases so without knowing the proof many solved the problem.

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

      I kept on overthinking it, for like 1 whole hour, and everything except the simple greedy came to my mind but at last I proved it by taking an input like [3, 2, 1] and [2, 3, 1] and finally got AC.I guess the lesson is to play with the input more instead of just formalizing everything especially for easier problems.

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

        I guess lesson is to use test cases as inspiration or insight.

        Second lesson is that you shouldn't spend too much time finding formal proof, although you should have an idea of proof in mind. You need to find a golden middle between theory and practice.

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

          what would be the answer for 7 8 1 lexicographically greatest possible is 8 1 7. but shouldnt the answer be 7 8 1

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

            Why isn't 8 1 7 the answer?

            You can take $$$2$$$ cards from the top of $$$p$$$ and move it to $$$p'$$$: $$$[8,1]$$$
            And then take $$$1$$$ card from the top and move it to $$$p'$$$: $$$[8,1,7]$$$.

            See, that's it.

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

              we can even take 3 cards from top and make it [7 8 1] whose order is greater than [8,1,7] the reason we are not taking it is because only number less than n are allowed which is the crux of the question

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

      Can you provide the proof? I figured it out partially but not completely

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

        I noticed that you cut the input in segments for example the third test case of the first example 6 4 2 5 3 6 1 if you notice here we have 3 major keys{4,5,6} by keys I mean the each of those keys all the elements after it till the next key is smaller than it 4 > 1 && 4 < 5 so the first segment here is {4.2} you then sort these segments according to there keys key 6's segment then key 5's segment and so on...

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

          what would be the answer for 7 8 1 lexicographically greatest possible is 8 1 7. but shouldnt the answer be 7 8 1

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

            The order of the input here is what matters we do not sort lexographically

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

        It's literally just finding the big number in base $$$n$$$ with given digits.

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

        The answer is the largest number in base $$$n$$$, so the left most number should be the maximum. But along with it you need to pick up the entire suffix from that position, because of the stack nature. Repeat the process.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 4   Vote: I like it +24 Vote: I do not like it

        If u have powers of n

        n^x greater than summation of n^(1->x-1)

        eg. 2^5 (100000 in binary) is larger than 2^0 + 2^1 + 2^2 + 2^3 + 2^4 (11111 in binary)

        so giving it largest coefficient will give largest solution

        A > B & C > D

        A * C > B * D

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

        Given an array $$$[p_1,...p_n]$$$, its order formula is like representing the $$$n$$$-digit "number" $$$p_1...p_n$$$ in base n. This then suggests the strategy of picking the current largest $$$p_i$$$ and the corresponding suffix (from $$$p_i$$$ to the end). Seeing the order as a base-n number also proves the strategy is correct.

        My $$$O(n)$$$ solution just in case.

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

        You can use geometric progression

        take make element as some x and second max element as x $$$-$$$ 1

        take some constant c which the number being used in the polynomial expression

        now compare $$$x * c^{n}$$$ and $$$(x - 1) * (c^{n-1} + c^{n-2} ... c^{0})$$$

        the gp formula will always yield a lesser value than $$$x * c^{n}$$$

        our expression has a lesser value than the gp so I guess the rest is obvious.

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

        you can write order as n^n(P1/n + P2/n^2 + P3/n^3.....Pn/n^n).. now when you choose some element to put into position Pi you will try to maximum element to maximize the sum

        PS:- sorry for not using math syntax I don't know how to use that

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

    The important part to note is the elements in the array are less than equal to n (size of array). Thus we should have proved that the MAX*N^(N-1) will be greater than all possible summations, when MAX is not in the first place of new deck (Same way as 900 is greater than all permutations of {2,6,9} creating a three-digit number when 9 is not in MSB, eg — 629, 692, 296 etc.) Basically treating the input as base-n number creation. Thus lexicographical sense is understandable. I missed this fact completely. If values aren't bound by n, not sure if this would work, need to check.

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

    From test data you could see greedy.

»
4 months ago, # |
  Vote: I like it +76 Vote: I do not like it

What a fst round :(

»
4 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Test case 73!

»
4 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Video editorial for problem C: https://youtu.be/7uXOxPAej7Y

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

fstforces

»
4 months ago, # |
  Vote: I like it +97 Vote: I do not like it

Why downvoting? The problems were great and the editorial is clear. It just has weak pretest. Even so why not to downvote the announcement instead of editorial?

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I know pretests of problem D were weak but otherwise it was a good contest. I don't think it's right to downvote it's editorial.

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

ch_egor, can you translate the name of the problem E to English in the bottom of the editorial? It is in Russian now.

»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

FSTforces。:(

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

My answer to A is $$$\min(a-p\bmod a,b-p\bmod b,c-p\bmod c)$$$. Maybe the idea is easier?
UPD: You need to check that if $$$p\bmod a=0$$$ or $$$p\bmod b=0$$$ or $$$p\bmod c=0$$$.

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

    We need to check if any of p%{a,b,c} is 0, explicitly in this case.

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

      Yeah I know that. I just forget to write it in my comment. thx for pointing it out.

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

    my solution is

    min(a-1-(p-1)%a,b-1-(p-1)%b, c-1-(p-1)%c)
    

    so you can avoid edge cases.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
                  p = kq + r
    
    If the remainder is non-zero, k would be rounded up:
              p + q = (k + 1) q + r
      (k + 1) q - p = q - r
                    = q - p % q
                    = - p % q
    
    If the remainder is zero, k would not be rounded up:
                  p = kq
             kq - p = 0
                    = p % q
                    = -p % q
    
    
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why for 0 1 0 in problem D answer will be No while 1,1 satisfy the given condition

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

Thanks for fast editorial and good problems.

»
4 months ago, # |
Rev. 3   Vote: I like it +47 Vote: I do not like it

my easy answer E

randomly select elements from arrays and test it is real.×100times

https://codeforces.com/contest/1492/submission/108293277

UDT this is very easy to hack, i tried some another way to pass, but maybe random can't

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

    It can be hacked by this.

    Spoiler
»
4 months ago, # |
  Vote: I like it +34 Vote: I do not like it

You wrote special case a = 0 for problem D in editorial but no pretests for this? Seems someone likes to see fst

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

CDE are nice, B is kinda "guess-by-sample" problem, and A just boring.

Great contest overall

»
4 months ago, # |
Rev. 4   Vote: I like it +18 Vote: I do not like it

The system tests of problem E are weak too. Some random solution like https://codeforces.ml/contest/1492/submission/108282677 can be hacked by this test case:

62500 4

1 1 1 1

1 1 1 1

1 1 1 1

...

2 2 2 2

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Problems were really interesting and looks like pretest were really strong as many solution got failed during system testing. Superfast editorial as well .....

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

Although I didn't count how many people failed to pass the system test on some problem, I found that my rank changed from 1238 to 764.

This round was really Fst forces!

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

only if a+b-2==k testcases were included in pretests for D :()

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Everyone's commenting "Fstforces". What does it mean?

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

    FST is equal to "Failed to pass System Tests".

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anybody explains to me how B can be implemented in O(N)?

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

    let pr be n(last element), loop this: 1.find the index of the maximum element in the remaining array , say id 2.push elements from id to pr in the ans array 3.update pr as id-1, break when pr==-1 finding index of largest element in the remaining can be done using a prefix maximum array.

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

      It is $$$\mathcal O(n)$$$.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you have taken pos array of size 'n' and taking its index value up to 'n' since you are doing pos[arr[i]]. can you explain why it's not giving segmentation fault??

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

        Well I am lucky here that compiler repaired it automatically for me, but it doesn't work everytime

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

    here's my submission, i used a stack and each time i reached the max unused card (starting from the right side of the array), i printed and emptied the stack 108442718

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

This gives me RE on pretest 5

RE

whereas this gets AC on pretest

AC

I have changed only this much part of the code and nothing else. Someone please help me out in debugging the error.

UPD: I got the mistake I was doing. Thank you all.

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

    Just a friendly advice, you should post the code as a spoiler or drop-down box.

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

      I tried that but it kept overflowing out of the box in the preview, so I removed it.

      I will see to it why it happens and make sure to put code in spoiler.

      UPD: Now it's not doing the weird behavior. Still don't know why though.

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

    I don't know what causes this, but with the following input:

    5 4
    aabaa
    aaaa
    

    your code prints 576479918390712804 which is clearly wrong.

»
4 months ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

Solve D in ten minute, WA after two hours.

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Editorial of E seems incomplete :(

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

[Deleted]

»
4 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

My performances during the contest

Quite awful. I opened the problem pages, after a couple of minutes, I finally see the statment of A, I think I spent little time solving it, but I forgot to save the code after I have a few changes, and I submit the code without realizing it. So I got a wrong attempt.

The following story is boring, until I try to solve D, at first I think there is only one way to make the answer have digit 11000-0001=0111. Obviously some cases were left behind, so I got WA on pretest #8. I suddenly find the problem, and I deside to recode — that is, to delate the original one and to solve the problem again from zero.

That is proved to be a bad idea, for the method when I recoded havn't been design carefully. So I finally WA in main test #64, and I didn't get in the first 1000.

But if I didn't recoded and chose to mend the code I write first, everything may be changed.

So I got a lesson after the contest: Think twice, code once.

»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Getting FST stimulates me !

»
4 months ago, # |
Rev. 4   Vote: I like it -28 Vote: I do not like it
Spoiler
»
4 months ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

Lots of contestants passed E with a random algorithm like 108293277. There is a hack test:

50000 5
1 1 1 2 2
1 1 2 2 1
1 2 1 1 2
1 2 1 2 1
1 2 2 1 1
2 1 1 1 2
2 1 1 2 1
2 1 2 1 1
2 2 1 1 1
rand() rand() 1 1 1
rand() rand() 1 1 1
...

The answer is 1 1 1 1 1 but if you randomly choose the answer from every sequence, the accuracy is $$$O(\frac{1}{n^2})$$$.

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

Really thank you for the GREAT pretests with Problem D.

Please make pretests STRONG next time.

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

FST Round The pretests of D are too weak :(

»
4 months ago, # |
Rev. 5   Vote: I like it -23 Vote: I do not like it

Let s be codeforcescontest704d and t be fst, the maximum width of p is 7 XD

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it -10 Vote: I do not like it

    UPD: To be frank, I really wonder why you guys tend to downvote me:(


    How did my comment become a downvote attractor? :( The meaning I wanted to explain was similar to the one the guy upstairs(Chinese:楼上, which means the previous comment or its poster, translated literally) referred to. :( One of my classmates used his three accounts or so to downvote me, and now there're so many:(

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

Learning from Problem A especially for JAVA users :

Ceil Value Problem
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    actually this problem is also in C++ . I submitted by using ceil function and converting denominator to floating point by multiplying with 1.0 but it gave WA mostly due to precision issue.

    we can do $$$(num+den-1)/den$$$ for ceil.

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

    Why is this getting downvotes?
    I have faced some problems, so I write it so that many users can correct the same mistake.

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

      Because of two reasons:

      1) In every single contest that requires ceil, there is a ton of comments describing exactly what you just did, it is clear that most people don't really enjoy repetition in comments thus they downvote.

      2) The algorithm you provide to get ceil is not really 'optimal', to be more precise most people use (A+B-1)/B (as the guy above me said) because it requires only one line of code and even is a bit faster because it doesn't use multiplication.

      To sum up, you did not do anything wrong by describing your issues, but people get tired of reading this exact comment every time there is a task that requires a ceil operation.

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

i think my solution to the Problem A was correct,but my submission to it didn't pass the test cases. Could you pls hava look over over it and correct me if i am wrong and where did i go wrong???? https://codeforces.com/contest/1492/submission/108247518

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

    This is because of an integer overflow. Try with long long.

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

How can I optimize my B solution? My solution
Any help would be appreciated.

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

    In your solution, it waste too much time to calc the maxi. Have a look of my code ? :) let M[i] be the largest p after pi.

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

      Thanks a lot for your reply! But I dont understand how you calculate M[i] Could you please explain it again?

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

        Oh, my fault... I meant that M[i] be the largest among {p[1]..p[cur]} (cur has the same meaning of the var 'end' in your code).
        In order to get the array M, we can scan from p[1] to p[n], maintain the largest's id, just like this


        maxid=1;
        for (int i=1; i<=n; i++)
        	M[i]= p[i]>=p[maxid] ? (maxid=i) : maxid;
        

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

For problem A, this was my following code:

from math import ceil
for _ in range(int(input())):

    p,a,b,c = map(int,input().split())
    print(min(ceil(p/a)*a,ceil(p/b)*b,ceil(p/c)*c)-p)

It is giving me WA on pretest 2. What am I missing?

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

Alternative solution for 1492E - Almost Fault-Tolerant Database is following: find any two vertices of diameter, then try all 2^(diffs) variants. Is it wrong? Can someone prove it or hack it? 108299916

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

tests are wonderful!!!!

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

Can somebody please tell why my solution for C failed .. - I have calculated max, min possible indexes for each t[i] keeping my mind p1<p2<p3 .. - where max of every index is smaller than max of i+1 - and min of i is greater than min of i-1. - and calculating the ans as the max of (max[i+1]-min[i]) for valid indexes. - and if we get answer from certain i, we can use max of each indexes >i+1 so that given condition is verified. Here is my submission: https://codeforces.com/contest/1492/submission/108280740

upd: got AC now :)

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

    I have a doubt, if p1<p2<p3... then why isn't the min of i greater than max of i-1.Because if min of i is smaller than max of i-1 then there will be some values of pi which will be smaller than p(i-1).

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

      Yes but i was ONLY looking for answer using min of i and max of i+1(so that I get maximum absolute diff).. so if a pair of(i,i+1) gives me the max width,then all the other indices less than i can be set to their minimums ( which will be less than min of i used ) and all indices greater than i+1 can be set to their maximums similarly

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

When Problem D is doable in O(n), why restrict the limits to $$$2\times 10^5$$$? The editorial doesn't even mention DP or any alternative solution that only works below $$$2\times 10^5$$$.

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

    You have to print $$$2 \times 2 \times 10^5$$$ characters. Longer string may cause I/O bottleneck.

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

Codeforces Round #704 (X)

Hackforces & FSTforces Round #704 (O)

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

why am I getting runtime error in this soln

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

    In calc() what if q1 is empty? (Which is a possibility.)

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

      then the answer will already be in the vector ans

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

      oh no now I realize. What a stupid mistake.

      Thank you

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

      what is wrong with my idea

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

        The solution is not to get increasing subarrays but to have the maximum element at last (otherwise there will be another subarray with higher score). So the first subarray will be the one containing nth element as last element (from the end as seen in testcases). Then recursively solve for n-1, n-2, ..., 1.

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

Good questions and fast editorial.

Personally, leaving some unexpected spaces for hacks is ok.

But it seems like this contest is another lesson for the authors that it's important to keep an eye on the chances for using randoming algorithms (or other tricks like brute force + #pragma)to pass the tests...

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

How to solve problem E's bonus 2? I can only come up with $$$O(nm+k^kn)$$$.

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

    Hint: $$$\sqrt{nm}$$$ and $$$\min{(n, m)}$$$ have something common.

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

      I know it, but I don't know how to deal with the case of $$$n>m$$$. Can you give more hints?

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

Simple solution for D:

Make x as a zeroes and b ones

Make r as k ones and max(a-k, 0) zeroes

Then if x-r >=0 and x-r contains a zeroes and b ones we found answer, otherwise no solution

108313076

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

    How did you find it?Could you please provide any proof or intuition behind it?

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

Bonus1 seems to be the same as the original task.

In Bonus2, intuitively split nm into 2 cases , where n <= 500 or m <= 500 , to reach the sqrt time complexity.... But have no idea how to keep on :(

Hope to get some hints.

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

    May I ask why the time complexity of the original task is $$$O(k^k nm)$$$?

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

      Basically the same.

      we only care about arrays that differes $$$[ k+1, 2k ]$$$ positions , when k = 2 , it becomes $$$[3,4]$$$

      And just to try to make change that meet the condition as far as possible recursively.

      We at most change $$$k$$$ arrays , and for each array , we at most make $$$2k - (k+1) + 1 = k$$$ changes using brute force.

      And each time , we need to use O(nm) to check

      So , that is O(k^kmn)

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

Doubt in problem E editorial :

We can ignore each other array that differ with the first array in no more than 2 positions

Take following input : n=3 m=3 , 1 2 3 , 4 5 6 , 3 3 7

We can see that 3 5 3 will work .

Now if input was : n=4 m=3 , 1 2 3 , 4 5 6 , 3 3 7 , 1 3 7

Then according to editorial 3 5 3 should work as answer because we ignore the 4th array . But then 3 5 3 differs from fourth array at 3 positions.

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

    Then according to editorial 3 5 3 should work as answer because we ignore the 4th array . But then 3 5 3 differs from fourth array at 3 positions.

    "Ignoring" an array doesn't mean that we immediately throw away it from input.

    The solution is to try to consider the first array as an answer, therefore we can skip ("ignore") other arrays which doesn't differ in more than 2 positions.

    If it doesn't work, then we change the first array and check again. In particular, after changing, "ignored" arrays may be differing in more than 2 positions (and therefore stop being "ignored").

    So, although you ignored the 4th array when considering "1 2 3" as a possible answer, you can't ignore the 4th array when considering "3 5 3" as a possible answer.

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

can anybody tell me why am i getting WA after using same logic for question : https://codeforces.com/contest/1492/problem/C my solution : https://codeforces.com/contest/1492/submission/108314097

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

    Test with this input:

    7 3
    oiioiio
    ooo
    

    Your code prints 6. It seems that your code assumes the letter o at the beginning/end of the first string can be reused, which is not true.

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

https://codeforces.com/contest/1492/submission/108277935 This is my solution for problem C.I don't know where I went wrong.I have implemented the same idea as given in tutorial.Please someone check it out.Thanks in advance.

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

test case 64!

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

Why are some editorials in english and some in russian?

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

some people have used randomized solution for problem E . Could someone please explain how to solve problem E using that.

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

Question C detailed solution Video Solution Explanation

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

If anyone is feeling stupid after the contest than let me tell you there are people way more stupid than you.

Failed solution during contest
Passed solution after contest

In case it is not clear the only difference between the two is while calculating the first(left) array I have used m as the exit condition in the inner loop instead of n.

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

I can't understand the meaning of E problem.

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

Did anyone solve C with a DP approach?? Please post it if possible

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

Can someone explain how to approach the problem B if we have random numbers in the array. If we have test cases of random numbers like [9,10,1] then the greedy logic fails

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

    Why it's wrong, the answer sequence is [10,9,1] Edit: sorry [10,1,9]

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

      Nope the answer is [9,10,1] as for [9,10,1] the value of the deck is (9*9 + 10*3 + 1*1) = 112 and for [10,1,9] the value of the deck is (10*9 + 1*3 + 9*1) = 102

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

Thanks in Advance.

I cannot understand why my submission for C got the wrong answer on Pretest 5.Can anyone please provide me a simple test case (for which my program will fail) so that I can understand my error.

Here is my submission : C.Maximum Width

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

Hi, for problem E, can anyone explain a little bit what does the variable cnt mean in the dfs() function of this submission?

https://codeforces.com/contest/1492/submission/108321457

Thanks for help.

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

    cnt is the no. of changes we can make in the first array;

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

In first question, it was all about constrains given in problem 10^18

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

Hi. I would appreciate if anyone tells me why this O(n+m) solution fails test 57 on time. Thanks a lot.

include

include <bits/stdc++.h>

include

using namespace std; int main() {

int n,m; //n >=m

string s, t;
cin >>n >> m >>  s >> t;


int maxi = 0;
int index = 0; char f;
int p[m+1];
p[m] = n;
for(int i = 0; i < m; i++){
    f = t[i];
    while(s[index]!=f)index++;
    p[i] = index;
    index++;
}
int dum;
for(int j = m-1; j >= 1; j--){
    dum = p[j];
    dum++;
    int last =p[j];
    for(dum; dum < p[j+1]; dum++ ){if(s[dum]==s[p[j]] ){last = dum; }}
    p[j] = last;
    maxi = max(p[j]-p[j-1], maxi);
}
cout << maxi << "\n";


return 0;

}

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In the editorial of problem C, I think the answer should be $$$\max_{i=1}^{i=m-1}\textit{right}_{i+1}-\textit{left}_{i}$$$ ($$$n$$$ is replaced by $$$m$$$.)

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

Problem C, 108446832 is getting WA on test 7. Can anyone provide a testcase?

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

Hello, can someone please explain how the solution to E is not 6^2 * (n*m) ^ 2? The way I understand it is like this: We go trough the list o(n * m), for every single guy, if he has more than 2 differences we go into the maximum of 6 ways of completing him (so times 6). For every one of those n * m * 6, we go trough the list a maximum of one more time, to look for another array that has a difference of more than 2 with our current solution array. So n*m*6*n*m. o((n * m) ^ 2 * 6) so far. Now once we find one we have a maximum of 6 ways to change our solution array so o((n * m) ^ 2 * 6 ^ 2) is our final complexity. Where am I misunderstanding?

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

    I implemented the solution in editorial in following way (I will the prove it's complexity) :

    We can notice that we can make atmost two changes to the first array so that it becomes original array and all array differ from it in atmost $$$2$$$ positions.

    Now we compare first array to all other arrays and we find another array such that it differs in more than $$$2$$$ positions then we must modify atleast one position in first array . Number of ways we can modify one position in first array is $$$4$$$ in worst case because as editorial says , the case with more than $$$4$$$ difference will not have answer.

    After the modification in first array , we again compare it with all other arrays and if we find some array differing in more than $$$2$$$ positions we must again modify it in one position. We will consider all possibility and maximum possibilities here will be also $$$4$$$.

    Thus it's like calling compare function recursively after modification , also in particular recursive function , we won't compare further once we found array with difference greater than $$$2$$$.

    Number of times we will call this recursive function is atmost $$$3$$$ because we can make atmost $$$2$$$ changes.

    So suppose in first function call in worst case we found the last array which differs in greater than $$$2$$$ position then number of operations in first function call would be $$$O(n*m)$$$.

    Number of operations related to second function call will be $$$O(4*n*m)$$$ because previous function will call this function atmost $$$4$$$ times.

    Number of operations related to third function call will be $$$O(4*(4*n*m))$$$ because number of times previous function will call this function will $$$16$$$.

    Thus total operations will be $$$O(21*n*m)$$$. The key point which saves time complexity from being $$$O((n*m)^2)$$$ is that in particular instance of function call , we don't compare with further arrays once we find the array which differs in greater than $$$2$$$ positions with first array.

    submission related to above reasoning.

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

I am unable to find out what wrong am I doing here: https://codeforces.com/contest/1492/submission/108491871

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

Hi, guys! May u help, please, find mistake in #C. I use binary search to find left/right indecies in the arrays of indecies of each char. I can't pass test 5. https://codeforces.com/contest/1492/submission/108497604

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

Can anyone tell what is wrong with this method in Problem A 108325761

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

Could anyone show me his Card Deck solution

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

(A+B+C) VIDEO TUTORIAL LINK : https://www.youtube.com/watch?v=q_BKIZe9CoA

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

Can someone explain the recursive backtracking solution for Problem E?

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

What is the asymptotic behavior of this solution? O(n*m), or O(n)? https://codeforces.com/contest/1492/submission/108635069

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

It has been almost 1 and half year but i didn't do good in the contest. please some good coder suggest me how i can improve my problem solving?

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

I think tutorial of Problem B is wrong. For testcase 9999 10000 1 2 3 4 5 6

Using card deck rules lexographic maximum permutation will be 10000 1 2 3 4 5 6 9999

But correct answer will be 9999 10000 1 2 3 4 5 6

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

Can somebody help me why I am getting Time Limit Exceeded Error https://codeforces.com/contest/1492/submission/108665110

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

    Consider s and t kind of long, and one letter is used most often.

    Then the line vi e = mp1[c]; basically copies the vector(n) for m times.

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

The editorial for Problem C seems to be unusual. Suppose we have our lefti =10 right(i+1) =100 and have some unique char at i+2 whose position was 28 ,how would the approach of this editorial solve this problem

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

https://codeforces.com/contest/1492/submission/111861146 i got tle on tc 10 but I thought it was only O(N log N ) help me plss....

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

Can somebody point out the mistake in my solution to the problem C? Here's my solution: https://pastebin.com/yE5tDG5s