Vasiljko's blog

How to solve SPOJ ADACOINS ?
By Vasiljko, history, 7 years ago, In English

What is the idea behind this problem?

Link to the problem

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

Comments Comments (8)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Use bitset.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Can you elaborate further?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Giveaway:

      bitset<100001> posi; posi[0] = 1;
F0R(i,N) {
    int x; cin >> x;
    posi |= posi<<x;
}
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sum can go upto 10^9 and we cannot have bitset with that no. of bits. How to proceed pls help

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Read the constraints. You only care about sums up to 105.

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes but the query asks for values upto 10^5 only.so, u dont dont have to care for numbers above 10^5.You have to update the bitset for every incoming x by shifting the bitset and doing or with previous bitset so that the bitset at the new possible sums become 1.you can refer to the snippet below.

          bitset<100001> bs;
   bs[0]=1;
   for(int i=0;i<n;++i)
   {
   	int x;
   	scanf("%d",&x);
   	bs|=bs<<x;
   }
   int s[100005]={0};
   for(int i=1;i<=100001;++i)
   	s[i]=s[i-1]+bs[i];
   while(q--)
   {
   	int a,b;
   	scanf("%d%d", &a, &b);
   	printf("%d\n", s[b]-s[a-1]);;
   }
          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can someone explain me the logic behind " bs|=bs<<x " statement

            → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

O

→ Reply