icode_247's blog

By icode_247, history, 5 years ago, In English

So i am trying to solve this problem`` And this is the tutorial i am referring to.Also this is the code. And I am trying to do it by dynamic approach. But can anyone please explain me this part :


` if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8])` ` dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j];` `` ` // If we exclude the number from our combination` ` if (dp[i — 1][j] > dp[i][j])` ` dp[i][j] = dp[i — 1][j];`

what is j * 10 + arr[i]) % 8 doing here?. what is j here?. It will be great if you could explain in details?

Thank you!

Full text and comments »

  • Vote: I like it
  • -11
  • Vote: I do not like it

By icode_247, history, 6 years ago, In English

Can someone please explain the logic used in the solution of this problem?. I see that they are trying to make a dp[] and then when we query for an input we get the result from the []. But how is this dp[] being developed?.

Please help. Thank you.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By icode_247, history, 6 years ago, In English

Hi, So i tried to solve this problem . And i did understand the first part of the tutorialbut got a little confused at the end. It says that I have to add everything from cnt[0] to cnt[n-1] to get my answer. But to get a faster result they did a different workaround. They created sums[] and worked on it. This is the c++ solution. Now, why would they do this?:

 for(int i = n-2 ; i >= 0 ; --i)
            cnt[i] += cnt[i+1];

and in this :

        for(int i = 0 ; i+2 < n ; ++i) {
            ss += a[i];
            if (ss == s)
                ans += cnt[i+2];
        }

Why i+2?.

Full text and comments »

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

By icode_247, history, 6 years ago, In English

Hi, I am a bit confused in the kind of logic used in the problem 991C Candies. The tutorial says that I have to produce a K using binary search every time and then check if for that k the person consumes more than half of the total candies. But I couldnt understand how the K is being generated using binary search. Basically can someone please explain me the logic in details?

Thank you!.

Link to the problem click here The model solution from tutorial is given below:

#include <bits/stdc++.h>
 
using namespace std;
 
bool check(long long k, long long n) {
    long long sum = 0;
    long long cur = n;
    while (cur > 0) {
        long long o = min(cur, k);
        sum += o;
        cur -= o;
        cur -= cur / 10;
    }
    return sum * 2 >= n;
}
 
int main() {
    long long n;
    cin >> n;
 
    long long l = 1, r = n;
    long long ans = r;
    while (l <= r) {
        long long k = (l + r) / 2;
        if (check(k, n)) {
            ans = k;
            r = k - 1;
        }
        else
            l = k + 1;     }
 
    cout << ans << endl;
}

Full text and comments »

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