Night_Lord's blog

By Night_Lord, history, 2 months ago, In English

In a subset sum problem always we have to find a subset which equals a given sum. Like in this example if $$$A=[1,2,3,4,5,15,21]$$$ and $$$sum=8$$$. Then the optimal subset would be [3,5]. But what if we consider all greater or equal subsets ? Like $$$[15]$$$,$$$[21]$$$ these are the minimum element subsets with sum greater or equals the given sum. How can I implement it?

Although general subset sum algorithm I learnt is-

        bool T[n+1][sum+1];
	for(int j=1;j<=sum;++j)
	{
		T[0][j]=false;
	}
	for(int i=0;i<=n;++i)
	{
		T[i][0]=true;
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=sum;++j)
		{
			if(arr[i-1]>j)
				T[i][j]=T[i-1][j];
			else
				T[i][j]=T[i-1][j]||T[i-1][j-arr[i-1]];
		}
	}

Can I able to change some snipets of code and get my output value or I have to learn something else. Thanks in advance.

Read more »

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

By Night_Lord, history, 3 months ago, In English

Today I have faced a weird type of wrong submission.Is that because of the power value is huge?or am I missing some things?

Problem:Little Pony and Expected Maximum

Read more »

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

By Night_Lord, history, 3 months ago, In English

Hello,as I am beginner in dp ,I am facing problem with this problem.Anyone help me understand the states and base cases for this problem?

The statement: When monkeys are given some fire-crackers, they have only thing in the mind — to blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k identical mailbox prototypes each fitting up to m fire-crackers. However, he is not sure of how many fire-crackers he needs to provide you with in order for you to be able to solve his problem, so he asks your help.

The constraints are:

  1. If you blow up a mailbox, you can't use the mailbox again, so if you have only k = 1 mailboxes, you would have to start testing with 1 fire-cracker, then 2 fire-crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m fire-crackers, you would need 1 + 2 + 3 + ... + m = m * (m + 1)/2 fire-crackers.

  2. If a mailbox can withstand x fire-crackers, it can also withstand x-1 fire-crackers.

  3. Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

Now the manufacturer wants you to find the maximum number of fire-crackers that his mailboxes can withstand. Before doing that you have to buy some fire-crackers to test that. So, you need to find the minimum number of fire-crackers you need to buy to test the mailboxes.

Read more »

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

By Night_Lord, history, 4 months ago, In English

Hello, as the constrains are huge I used big integers to multiply the numbers in this problem from ABC. However I am still getting TLE .Anyone help me how I use Big Integer for this problem? My submission is here The blog I followed for the Big Integer code is here

Read more »

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

By Night_Lord, history, 4 months ago, In English

Hello,I know this question might be silly to most of you but I desparetly seeking the answer.Here is my question-

#include <bits/stdc++.h>

using namespace std;

long long BaseConversion(long long n,long long p)
{
    if(n<p)return n;
    return n%p + 10*BaseConversion(n/p,p);
}

int main() {
    long long n;
    while(cin>>n)
    {
    	cout<<BaseConversion(n,9)<<endl;
    }
    return 0;
}

How do I calculate complexity from this problem?As long as I know about complexity depends on loop. But in recursion how can I calculate this? The above code works in 0<=N<=10^18 range .How this code gives log(n) complexity?

Thanks.

Read more »

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

By Night_Lord, 4 months ago, In English

Hello, recently I am having some issues in math related problems. Most of the other tag problems like implementation,brute force,games,number theory problems seems to be ok to me.But when it comes to math related problem I most of the time do it in bruteforce approach or implementation result is obvious. Most heart breaking part is even 800-900 rating problems in math becomes harder while contest time sometimes. If A problems getting 2-3WA or takes longer than 10-15 minutes then it's really hard to focus on the next questions cause of depressions. And it's not like I haven't solve math related problems so often.But when it comes to contest time simple formula seems to be a big of a deal and it's really hard for coders like me.Please suggest me some sites from where I can enrich my thinking capabilities in math and has some decent problems. Thank you.

Read more »

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

By Night_Lord, history, 5 months ago, In English

I was lately trying to access every 2nd last element from a multiset container. Here I want to first print every 2nd last element from the container then erase it from the container. This process continues until the size of the container reaches to 1.

My so far approach for this process is given bellow-

    int n;cin>>n;
    multiset<int>st;
    for(int i=0;i<n;++i)
    {
        int x;cin>>x;st.insert(x);
    }
    while(st.size()!=1)
    {
        auto it=st.rbegin();
        prev(it,1);
        cout<<*it<<" ";
        st.erase(*it);
    } 

Here, my expected results for the given case is-

6
0 0 1 0 1 1

ans- 1 1 0 0 0

Thanks in advance.

Read more »

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

By Night_Lord, history, 5 months ago, In English

Hello, I got stuck here in this problem from cses Subarray Divisibility.I know that showing solutions is prohibited from cses but still I need some help here.My solution is here.Plz don't down vote me.If u can't help me just ignore this topic.

Read more »

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

By Night_Lord, history, 5 months ago, In English

Hello,need idea for this problem from SPOJ SEQ — Recursive Sequence . I am really new in matrix exponentiation learning.Here I learnt from this blog T matrix for the test case-

3 
1 2 3 
4 5 6 
6

is T=

0 1 0
0 0 1
6 5 4

Then I multiply T with Identity matrix I.For me the answer should store in I[n-1][n-1].But maybe here I am missing something which I clearly missing completly.I searched in google and github but could not get a satisfactory answer.

my code

Read more »

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

By Night_Lord, history, 5 months ago, In English

Hi coders,getting wa in this problem.My submission is here .Any idea?

Read more »

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

By Night_Lord, history, 6 months ago, In English

Hello. I was wondering if it's possible to use two accounts for codeforces contests?I want to use one account to submit only accepted solutions and other one for testing the problem if it's possible to accepted or not?I think it's not a cheating as I am not taking others solutions I just don't want to face -100 everytime . Plz help me with this

Read more »

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

By Night_Lord, history, 9 months ago, In English

Hello, I have been coding last three years. I have solved quite a number of problems in various sites like uva, lightoj.I also completed static a2oj(<1300) rating problems. But still in the codeforces contest there are so many problems I faced lately. Like, I solved A no question after 30-40 min. Someday I can't get the efficient algorithm to solve B no question. In some contest, I get wa for some very silly mistakes like not using long long integer or like not checking critical test cases etc. Here so many of the great coders just take 1 or 2 years to become blue or even further .But I don't know what I am missing in my approaches?

Read more »

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