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

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

991A - If at first you don't succeed...

Разбор

Решение1

Решение2

991B - Getting an A

Разбор

Решение

991C - Candies

Разбор

Решение

991D - Bishwock

Разбор

Решение1

Решение2

991E - Bus Number

Разбор

Решение

991F - Concise and clear

Разбор

Решение

Разбор задач Codeforces Round 491 (Div. 2)
  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

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

I like it when you publish solution with code inside! Thanks ashmelev!

Ps: would it be greater if you post pseudocode instead of real source code? So that non-C++ people can appreciate it too. :P (That said your code snippet is clear enough even for people with minimal exposure to C++, I think)

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

Nice , clear & descriptive editorial.

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

can anyone explain what is the difference between k-=k/10 and k-=(int)(0.1*k) where k is an integer

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

    with reference to C problem k must be taken as long long, k/10 will also be long long but you are converting what is supposed to be long long to int creates the problem

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

      i was it in general.in the problem submission i have used long long

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

        i am specifically talking about k-=(int)(0.1*k) this expression even though k is long long this conversion to (int) just kills it

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

          It is worth noting that k -= 0.1*k is also incorrect because it causes a conversion from long long to double and doubles can only represent integers precisely up to 10^16. Since k can be up to 10^18, you will get precision errors when converting k to a double.

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

I m genuinely asking this question.... Does anybody has good material to solve binary search problems???

I have already read about and understood the idea and concept binary search but in many question i have been missing all the answers in a test case by 1 digit and its really frustrating investing time in it during a contest.....

Plz help!!!!!!!!

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

    You can always refer to A2OJ ....Binary Search Problems

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

    Rather post it as a blog post. Might even help as an archive if you post there.

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

      Will do.... Thanks

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

        For integers you can just memorize two workable forms

        int mid = (lo+hi)/2;

        either search(lo, mid) // hi = mid\

        or search(mid+1, hi) // lo = mid+1

        int mid = (lo+hi+1)/2;

        either search(lo, mid-1) // hi = mid-1

        or search(mid, hi) //lo = mid

        which will help you for most problems.

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

    most epic and crystal clear explanation of binary search is following.

    first: notice that any complex binary search task can be transformed into following task: in array of zeroes and ones find border between 0 and 1. for example.

    find last 5:  00000001111
    array:        11335556778
    find first 5: 00001111111
    

    In first case b[i] = 1 is when a[i] > 5, in second case b[i] = 1 when a[i] >= 5.

    Now, how to find border? We will have two indexes: l and r. We will use invariants: l always point to 0, and r always point to 1 (invariants are awesome). Now, if some index c points to 1 then set r to c, else set l to c. Invariants still holds. One invariant missing: to prove that binary search will complete in finite time, you need to reduce r-l each step. So, we need one more invariant: c should be between l and r. And c should not coincide with l or r. Easy to show that formula $$$c = \left\lfloor\frac{l+r}{2}\right\rfloor$$$ has this property. Also it is reducing range into half.

    Now, we know that after seach l is pointing to zero right next to border, and r is pointing to r right next to border.

                        lr
    find last 5:  00000001111
    array:        11335556778
    find first 5: 00001111111
                     lr
    

    So, in first case we should return l, and in second case we should return r. In the end, don't forget to check before running binary search that in the beginning invariants holds. r indeed points to 1 and l indeed points to 0. Otherwise our prove is not legit. And also, you don't need to have this array of zeroes and ones. You can make element of it on the fly.

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

      I didn't get which array is a and which array is b . Could you please explain again thanks in advance :)

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

The recursive solution for E is nicer and simpler.

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

    So could you please explain it to me?

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

      I'm kinda bad at explaining recursion..

      In my solution I recur from 9 to 0 and iterate (from 1 to the number of times that digit appears) = j. To calculate the number of ways to add the digit do the current string with length = m, I do (j + m)! / (j! * m!). Then I continue recursion passing this result.

      I divide by j! because the digit is repeated j times and I divide by m! because I can't change the order of the current string.

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

In problem C, I checked the condition for binary search as if(sum>=(long)(ceil((double)n/2))) return true and it gave WA in system test. Now after changing it to sum*2>=n, it gives correct answer. Why is first one wrong ? @ashmelev

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

    I think it should be floor instead.

    suppose we are checking x>=n/2 if n=5 then x>=3 not x>=2

    ceil(5/2) will give 2 as it is not float value

    https://ideone.com/Yt5Zkh

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

      I think ceil is correct. If sum=8 and n=15. Then sum*2>=n is true as 16>=15. Now if we take floor then 8>=floor(15/2), 8>=7 is false, so its not correct. So ceil will give correct answer.

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

        dude check my code again!!

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

          In my code actually it is sum>=(ceil((double)n/2)). So I have casted it to double before dividing.So its proper.

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

            actually using double creates the problem here. We have to note the capacity range of double..we should use long double for it. So when I did declared n as long double and did ceil(n / 2), it gave correct answer then.

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

            You should have used long double instead of double

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

    Because double/float may cause precison error. e.g. (double)1000/2 can become 500.00000001. and ceil(500.00000001) is 501 (but actually it should be 500), so it can give wrong answer.

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

Good editorial !

Here are all my solutions to the contest and here is my editorial to C for beginners who have never seen binary search used for anything other than finding an element of an array.

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

F's solution states the following:

Moreover in all the cases such expressions should contain at most 7 digits.

How can one show that?

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

    For example, let’s take an expression x*y. If at least one of the expressions x, y contains at least 8 digits then the whole expression contains at least 8+1+1=10 digits, which is greater or equal to the length of every number in problem.

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

Can anyone explain what this loop does? for (int j = 0; j < k; j++) if (i & (1 << j)) c += n[j];

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

ashmelev In Div2 C, what would be the time complexity for checking function? wouldn't it be O(n/k)?

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

    We multiply the number of candies by 0.9 every day, so it decreases fast — it will be enough about log(n) / log(1 / 0.9) days, 378 days in the worst case.

    While 0.9365 is about 2e-17 :)

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

In E what is c0 and what do you mean by "check whether the string contains all digits". Please explain.

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

    In the solution c0[i] — amount of digits i in the original (input) number. ''contains all digits'' — a meant ''contains all digits which the input number contains'' i.e. if c0[i] > 0, c[i] should be > 0 too.

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

If anyone is confused with editorial about problem E, check my submission it has comments and explanation, and I tried to cover whole solution, I hope it helps you understand the solution

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

Does 991C — Candies have an O(1) solution?

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

In 991C editorial prove of same count of days is missing. If with larger k there are shorter amount of days, then Vasya may eat less amount of candies.

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

    If the k is bigger Vaysa will eat more,

    Let's Compare both situations:

    K1>K2 (K on the first day and K on the second day)

    So Vaysa will eat more in her steps.

    As the Result Petya will eat less because the result after eating Vaysa in the first situation will be less than the result in the second situation so:

    n2 < n1(after eating Vaysa)==> n2/10 < n1/10(Because this are 2-digits) ==> So Petya in the second situation will eat less.

    If it's not clear write it on paper.

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

      K is fixed. And Vasya is him. your formula is repeating of editorial. yes, petya will eat not bigger in each corresponding day, but who said that count of days is same? who said that they will eat same count of days? something is missing. proof should take into consideration count of days.

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

    Vasya is eating in the morning and Petya in the evening, how days for Vasya will be shorter ?

    Do you have any such test case?

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

      I don't compare Vasya vs Petya. I compare number of days they eat with different k. Proof in editorial talks about certain days, and for fixed index of day it looks legit. But nowhere mentioned that number of days until they eat everything may change.

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

How to solve problem D using DP approach. I solved it using greedy approach but i'm learning DP. Could you give me a detailed explanation for DP problem D? Thanks in advance.

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

    Hd7 63735860

    this is my solution if you are interested. just consider the previous orientation of the piece placed and the possible orientation to be place at column i and maximize with the case that you go the next cell without placing anything. 0 is there is no placed piece to the left 1, 2, 3, 4 the 4 orientations