ashmelev's blog

By ashmelev, history, 3 weeks ago, translation, In English,

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

Editorial

Solution1

Solution2

991B - Getting an A

Editorial

Solution

991C - Candies

Editorial

Solution

991D - Bishwock

Editorial

Solution1

Solution2

991E - Bus Number

Editorial

Solution

991F - Concise and clear

Editorial

Solution

 
 
 
 
  • Vote: I like it  
  • +91
  • Vote: I do not like it  

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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)

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

Nice , clear & descriptive editorial.

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

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

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

    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

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

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

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

        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

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

          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.

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

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!!!!!!!!

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

The recursive solution for E is nicer and simpler.

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

    So could you please explain it to me?

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

      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.

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

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it -11 Vote: I do not like it

    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

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

      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.

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

        dude check my code again!!

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

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

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

            then it should work fine :|

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

            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.

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

            You should have used long double instead of double

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

    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.

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

      I understand what you are trying to say. But can you give a proper example where it will fail. I tried your example and it works properly.

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

        I don't know any exact testcase. But you may find the accepted answer of this stackoverflow question useful.

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

        You can get a testcase like this by making a code. Say x=(long)(ceil((double)n/2)) and y=n/2 Now you can compare 2*x and y. I saw your submission verdict and found out that at 999999999999999973 these both are not equal. So that's why you got WA in that test.

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

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.

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

    +1. You are doing a great job by writing explanations. Please, keep up the good work.

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

F's solution states the following:

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

How can one show that?

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

    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.

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

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

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

how to do Dynamic programming solution for problem D?

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

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

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

    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 :)

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

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

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

    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.

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

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

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

in ques E for test case 2028 why the ans is 13

should it be 25 1> 2, 2> 20, 3> 22, 4> 220, 5> 202, 6> 8, 7> 28, 8> 82, 9> 80, 10> 280, 11> 208, 12> 820, 13> 802, 14> 228, 15> 282, 16> 822, 17> 2280, 18> 2820, 19> 2802, 20> 2082, 21> 2028, 22 >8022, 23 > 2208, 24 >8220, 25 > 8202 thanks in advance :D

EDIT: Got that we are taking numbers in such way that all distinct digits from 0 to 9 appear at least once.

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

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