11266 - Equations

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

11266 - Equations

Post by ani_mitr86 » Thu Sep 06, 2007 2:27 pm

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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Thu Sep 06, 2007 5:10 pm

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
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

thanks

Post by ani_mitr86 » Fri Sep 07, 2007 3:03 pm

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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Fri Sep 07, 2007 6:11 pm

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
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust » Fri Sep 07, 2007 9:00 pm

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. :oops:
Thnx in advance.

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

Post by ani_mitr86 » Sat Sep 08, 2007 3:50 pm

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
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

Post by Anindya » Sun Sep 09, 2007 5:58 am

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
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

Post by ani_mitr86 » Tue Sep 11, 2007 7:49 am

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
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust » Sun Sep 23, 2007 11:16 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 23, 2007 7:58 pm

Piklu_sust wrote: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.
Piklu_sust wrote:Can anyone explain why this case answer : 121326
What did you get? Because explaining this case would be too tough.
Ami ekhono shopno dekhi...
HomePage

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust » Tue Sep 25, 2007 5:27 am

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
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11266 - Equations

Post by Repon kumar Roy » Sat Apr 12, 2014 12:21 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11266 - Equations

Post by brianfry713 » Mon Apr 14, 2014 10:09 pm

AC output for your input:

Code: Select all

6
0
4
121326
Check input and AC output for thousands of problems on uDebug!

arkidd
New poster
Posts: 3
Joined: Wed Aug 21, 2013 1:41 pm

Re: 11266 - Equations

Post by arkidd » Tue Oct 21, 2014 5:21 pm

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
Last edited by arkidd on Wed Oct 22, 2014 7:48 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11266 - Equations

Post by brianfry713 » Tue Oct 21, 2014 9:08 pm

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”