11266 - Equations

[ani_mitr86]

can smbd provide me some smple i/o

i have tested it for given i/o as well as some other i/o it is giving correct ans

but when submitted its wrong ans

thanks in advance

[Wei-Ming Chen]

Input

Code: Select all

3
6 325
10 25
41 255
36 78
10 100
25 125
200 575
8 20
6 6
5 5
-9 -9
8 8
1 1
7 7
-8 -8
10 10
6 -100
-5 -1
0 26
-1000 999
6 14
5 20
7 48

Output

Code: Select all

56
1
16468

Hope it helps.

[ani_mitr86]

thanks for the sample i/o

my prog is giving the same output but still i am getting wrong ans

i am posting the code as i have no other option

#include<iostream>

using namespace std;

long long comb(long long n, long long r){
long long a[10], i, j;
for(i=0; i<r; i++) a=n-i;
for(i=r; i>1; i--)
for(j=0; j<r; j++)
if(a[j]%i==0){ a[j]/=i; break; }
i=1;
for(j=0; j<r; j++) i=(i*a[j])%200003;

return i;
}

void swap(long long& a, long long& b){
long long temp=a;
a=b;
b=temp;
}

int main(){
long long s, n, cases, lt[10][2], i, j, k, a, co[1024], d[10], cnt;
cin>>cases;
while(cases--){
cnt=0;
cin>>n>>s;
for(i=0; i<n; i++){
cin>>lt[0]>>lt[1];
if(lt[0]>lt[1]) swap(lt[0], lt[1]);
s-=lt[0];
d=lt[1]-lt[i][0]+1;
}
j=(1<<n);
for(i=0; i<j; i++){
co[i]=0;
for(a=0, k=0; k<n; k++)
if(((i>>k)%2)==1){ co[i]+=d[k]; a++; }
k=s-co[i];
if(k>=0){
if(a%2==0) cnt+=comb(n+k-1, n-1);
else cnt-=comb(n+k-1, n-1);
cnt%=200003;
}
}
cout<<cnt<<endl;
}
return 0;
}

[Wei-Ming Chen]

try this case

Code: Select all

1
6 5874 
-521 5789 
-7895 25 
-123 456 
987 10000 
-1000 0
-10000 10000

answer is 50938

[Piklu_sust]

Can anyone tell me how can i solve it without passing the TLE (Within 5 seconds during the onsite contest).
I cannot figure out DP or direct formula for this problem.
Thnx in advance.

[ani_mitr86]

actually in c++ -1%3 is giving -1 and not 2, i wonder why cna smbd tell

but still i fixed this problem and got the correct ans for the sample i/o

but still i am getting wrong ans

anyway thanks to all for the help

[Anindya]

Hello ani_mitr86:
i think the following i/o set will be helpful to you:
Input:

4
3 10
-1 3
2 4
6 7
1 6
0 5
2 6
0 5
0 4
10 50000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000

I got this output from my ac code:

6
0
4
121326

hope you get ac.

[ani_mitr86]

thanks to all who helped me, i hv now got it ac
there was a bug, logic was fine

thank to all once again

[Piklu_sust]

I have got the idea what should do. I use exclusion-inclusion to find the desired output.
What should I do for the following case:
Solutions are {1, 2, 3}, {1, 3, 2} .
Should I count twice for these solution set?


Can anyone explain why this case answer : 121326
Case:

10 50000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000
-10000 10000

Thnx again everyone who posts in this thread.

[Jan]

I have got the idea what should do. I use exclusion-inclusion to find the desired output.
What should I do for the following case:
Solutions are {1, 2, 3}, {1, 3, 2} .
Should I count twice for these solution set?

Ofcourse.

Can anyone explain why this case answer : 121326

What did you get? Because explaining this case would be too tough.

[Piklu_sust]

Thanks Jan and everybody who posts in this thread.

After get several wrong answer I couldn't find my bug. So, ask this kind of question.

But now I got it accepted after finding silly bug in my code. problem is my nCr function. This function couldn't work with handing overflow.

Thanks again everybody.

[Repon kumar Roy]

This is my code .. .

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 200003


ll  ara[15];
ll murikha,sum,n;

long long nCr(long long n, long long r){
    long long a[10], i, j;
    for(i=0; i<r; i++) a[i]=n-i;
    for(i=r; i>1; i--)
        for(j=0; j<r; j++)
            if(a[j]%i==0){ a[j]/=i; break; }
    i=1;
    for(j=0; j<r; j++) i=(i*a[j])%200003;
    
    return i%mod;
}

int main()
{
    ll test,i,pri,res,low,high;
    //printf("%lld",nCr(5, 4));
    scanf("%lld",&test);
    
    while (test--) {
        scanf("%lld %lld",&n,&sum);
        pri=0;
        for(i=0;i<n;i++){
            scanf("%lld %lld",&low,&high);
            pri+= low;
            ara[i]= high-low+1;
        }
        sum = sum -pri;
        if(sum>=0)res = nCr(sum+n-1,n-1);
        else {
            printf("0\n");
            continue;
        }
        
        sort(ara, ara+n);
        
        ll p= 1<<n;
        for (i=1; i<p; i++) {
            int mask=1<<0;
            int cnt=0;
            int hurrah=0;
            for(int j=0;j<n;j++){
                mask=1<<j;
                if(i&mask){
                    hurrah+= ara[j];
                    cnt++;
                }
                
            }
            if(hurrah<=sum) {
                if(cnt &1) res= (mod+res- nCr(sum-hurrah-1+n, n-1))%mod;
                else res= (mod+res+ nCr(sum-hurrah-1+n, n-1))%mod;
            }
            //if(res>mod) res %=mod;
        }
        printf("%lld\n",res);
    }
    return 0;
}

My code gives following I/O


Input :

• 4
  3 10
  -1 3
  2 4
  6 7
  1 6
  0 5
  2 6
  0 5
  0 4
  10 50000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000
  -10000 10000

OUT PUT :

• 6
  0
  4
  2291

Why The last output is wrong !!!!
I tried but failed....
Help needed... pls

[brianfry713]

AC output for your input:

Code: Select all

6
0
4
121326

[arkidd]

My code passes all the testcases you guys gave, but still WA

Can someone help provide more testcases or find out what's wrong with my code?

Thanks!

Code: Select all

Code removed after AC

[brianfry713]

Input:

Code: Select all

50
3 46972
-5257 921
5414 8939
5461 5646
6 23143
-8238 -2321
-8821 6583
2913 7332
231 8528
6075 8971
-5437 1032
8 -10231
-4500 -306
4078 8151
-6891 6475
862 7646
2098 9704
-2633 2227
881 7561
13 3011
2 15513
-1816 5520
6473 9535
8 -26803
-5788 -2544
5075 5409
6463 9680
3406 6284
-692 6058
-7658 9676
9996 9998
-8888 -1033
1 -49524
-6675 -5493
9 -12361
3861 4191
2554 4448
-8221 4637
-3138 317
9451 9451
5222 9485
-6430 -2702
-4372 7984
-8912 1116
7 -22796
4794 5505
-5925 -5872
-6011 9270
-1895 1521
4897 7875
-1906 5427
4668 8740
3 47383
7116 9024
8770 9736
6180 9916
3 -38273
-604 5541
-9554 8522
-7185 8840
4 -14327
-9479 5465
-9045 -7537
-525 4409
-7012 -4170
3 23245
3130 7861
9172 9622
4470 9750
8 9745
-9706 452
4672 4991
-1314 1528
-3294 5291
-8008 -2343
-8522 -3721
4572 6127
-1223 5339
9 44144
-1691 2121
-3656 7609
5464 9956
-7754 -1419
4568 9611
4644 7478
3675 4910
6262 8386
7485 9504
1 2159
7801 7921
6 42012
-4807 9551
2441 3347
1253 1812
9664 9937
4496 9973
1226 7298
2 -37048
-1684 5296
3908 8133
9 -10266
-8383 -1675
-2909 5359
9744 9968
-2986 3657
2513 5319
-2015 2606
-6107 -1967
5397 9750
4261 9113
6 -11226
-1491 5419
-7564 9062
4289 6131
2642 8779
3711 8384
-6779 -5641
2 -17595
-8128 -4193
-9022 -6688
9 -31974
7054 8389
4919 7860
-3447 8421
9814 9882
2817 5299
3291 4141
9060 9321
-3523 3775
200 9420
8 -21525
4016 9417
-3320 -3174
-39 7193
3146 9933
-8842 8614
-5570 -1064
3696 8893
-7121 7337
1 -14374
-5217 -3114
1 -32139
4968 7877
2 16293
-1775 6899
-5717 8333
5 42921
3139 7632
-551 2720
-8254 -1862
4038 5673
3884 8203
10 -32120
-1021 1374
1549 7332
7851 7971
6006 6893
-8153 2884
7383 9438
6138 7068
8252 8751
-3462 5484
-3840 152
6 11052
-3504 -1036
-8076 3943
-7389 721
165 3542
828 9084
-7394 -4055
2 -3637
-7570 -152
404 7732
4 -49219
1088 7788
-9166 -493
-6352 1288
4105 9715
7 47833
-862 5417
-1949 819
2683 3778
4311 8911
-4448 -3353
-4288 1820
1236 5064
8 46412
-2944 5133
-8336 -6877
7967 8854
-68 1256
-4189 4930
3615 3925
-2892 6573
1981 8604
2 19046
8470 9289
8136 8204
9 38395
-8361 -119
9288 9968
-2682 6340
262 3272
-4475 -2861
-5201 540
-1602 3485
-266 4469
2031 3119
9 -26708
-7385 201
-7174 8187
7300 9838
5806 8349
-8483 -2502
-3436 -936
-5753 4431
-6527 3456
-5084 4978
8 -34365
3102 5256
-8625 6577
-810 4314
5708 9809
-8101 9216
-5919 -1518
822 9593
1104 2172
9 39503
998 8318
-4060 7850
-2240 7231
-2867 6927
-4528 9880
2409 8673
-3788 -1654
3313 5628
-2991 8325
1 -6409
-2556 3502
1 -20390
6272 6560
9 2923
96 4189
8006 8532
-3878 5793
8655 9139
7853 8730
-1164 9354
-8442 5822
-4102 2001
-3245 6708
2 36581
-4566 709
-6077 7022
7 27468
1845 6691
-4111 5400
-1941 -859
-7043 -985
7079 9719
9 5993
-3317 6904
10 -4203
8628 9906
-9516 -8968
-4269 -664
-2543 5594
-5275 1415
-8815 -6803
-511 7058
-9997 -7791
-3718 -1317
-7228 8200
2 19952
-5874 -947
-7749 5274
6 -21150
3159 9275
1894 5055
-947 4835
-9969 2938
-6661 -3096
-2966 -1771
2 -11801
-5847 -2450
7538 9946
6 47134
7490 8505
-4399 142
8308 8340
3204 7424
5025 7620
6934 8155
10 43111
-6311 -2125
-1353 4491
-1136 6063
8651 8800
-2509 3890
5279 8287
-2500 1908
-6759 8729
-5924 4011
-7559 3180
10 -36288
567 8020
-1252 6110
-2764 1460
-8785 -1016
-8051 -5534
-3657 4850
6066 6913
24 6381
-7734 -3090
-1372 7299
6 -22110
4081 4084
7154 9682
-5707 9131
8996 9515
-2216 4386
-9987 1574

AC output:

Code: Select all

0
52649
0
0
0
0
0
0
0
0
61777
97540
73720
40112
0
0
0
0
0
0
0
0
0
0
0
0
0
111155
3530
0
0
0
0
0
90898
0
166425
0
0
0
0
102431
82223
0
0
0
0
73360
0
0