Atcoder Beginner Contest-177 Problem C

help
,
1

ATCODER BEGINNER CONTEST - 177 PROBLEM-C

Submission 1 : (WA)

Submission 1 : (WA)

  • In the First Submission I’ve applied modulo and prefix sums array also
  • I’ve just removed the Modulo From Prefix Sums array and the solution Works Fine
  • I Don’t Understand Why?
2

The variable res can be negative, so just add res = (res + mod)%mod before returning it.
In Python modulo is defined to be positive but in C/C++ you need to be careful with it.
Check your new submission: Submission #16394482 - AtCoder Beginner Contest 177

3

When all the elements of Array A are positive then where is the chance for res to go negative

4

When sum becomes more than mod, then value reduces, suppose prefix[n-2] = 10^9+5 and arr[n-1] = 2, in that case prefix[n-1] = 0 and prefix[n-1] - prefix[n-2] < 0. Did you understand it?
It’s always better to add res = (res+mod)%mod in the end.

5

Yeah Thanks

6

I got 2 WA when I used C++. Then I implemented the same logic in python and got AC :sweat_smile:

7

Use long long

8

I got AC in c++… hope this piece of code helps…
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl “\n”
#define append push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________

int main() {
roastedcoder
ll n; cin>>n;
ll a[n], dp[n] = {0};
cin>>a[0];
dp[0] = a[0];
for(int i = 1; i<n; i++) {
cin>>a[i];
dp[i] = dp[i-1]+a[i];
}
ll res = 0;
for(int i = 0; i<n; i++) {
res += (((dp[n-1] - dp[i])%mod)*a[i])%mod;
}
cout<<res%mod<<endl;
}

//__________________________________________________________________

1 Like
9

My solution : “Submission #16321181 - AtCoder Beginner Contest 177”

I make other functions like modmul ,modadd , modsub so that my answer will never wrong bcz of modular arithmetic.

ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}
 
ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}
 
ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}
1 Like
10

watch this video:

13

My Python Submission:

  1. N=int(input())
  2. l=[int(i) for i in input().split()][:N]
  3. arr=[-1]*N
  4. arr[0]=l[0]
  5. for i in range(1,N):
  6. arr[i]=arr[i-1]+l[i]
  7. cnt=0
  8. for i in range(N-1):
  9. cnt+=(l[i]*(arr[-1]-arr[i]))%1000000007
  10. print(cnt%1000000007)
14

i have used #define int long long

15

Did using such function help you in preventing WA.

16

Yes , and code is clear too , but make your own functions