WWALK - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Vivek Chauhan
Tester: Radoslav Dimitrov
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Bob and Alice are walking on an infinite street, starting from the same position (say X = 0), walking towards increasing X. Denoting Alice’s speed and Bob’s speed during i-th second by A_i and B_i.

Find out the number of meters Alice and Bob walk side by side at the same speed.

QUICK EXPLANATION

  • Only two conditions matter, current positions of Alice and Bob, and their speeds.
  • If the distance traveled after x seconds is same, and their speeds are same in next second, then they shall walk together in the next second.

EXPLANATION

All we need to do is to read the statement and derive the condition for a weird walk. From the statement, we can see the following conditions.

  • They must walk at the same speed.
  • They must walk side by side. This implies that before the current second, Bob and Alice should be at the same position.

Now, we can just denote the position of Alice by P_a and the position of Bob by P_b. In the i-th second, conditions become

  • A_i = B_i
  • P_a = P_b (Before updating P_a and P_b)

If both conditions are true, they walked A_i (same as B_i) distance together.
After i-th second, P_a becomes P_a+A_i and P_b becomes P_b+B_i

Refer to implementation if anything is still unclear.

Side tip: Watch out for overflow in second subtask.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 100005;
char en = '\n';
ll inf = 2e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
	if (n & 1)
	  res = (res * x) % mod;
	x = (x * x) % mod;
	n >>= 1;
  }
  return res;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll t;
  cin >> t;
  while (t--) {
	ll n;
	cin >> n;

	ll a[n + 5];
	ll b[n + 5];
	for (ll i = 1; i <= n; i++)
	  cin >> a[i];
	for (ll i = 1; i <= n; i++)
	  cin >> b[i];

	ll sumA = 0, sumB = 0;

	ll res = 0;
	for (ll i = 1; i <= n; i++) {
	  if (a[i] == b[i] && sumA == sumB)
	    res += a[i];
	  sumA += a[i];
	  sumB += b[i];
	}
	cout << res << en;
  }

  return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n;
int a[MAXN], b[MAXN];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> b[i];
	}
}

void solve() {
	int64_t pos_a = 0, pos_b = 0;
	int64_t ans = 0;
	for(int i = 1; i <= n; i++) {
		if(pos_a == pos_b && a[i] == b[i]) {
			ans += a[i];
		}

		pos_a += a[i];
		pos_b += b[i];
	}

	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while(T--) {
		read();
		solve();
	}

	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class WWALK{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni();
	    int[] A = new int[N], B = new int[N];
	    for(int i = 0; i< N; i++)A[i] = ni();
	    for(int i = 0; i< N; i++)B[i] = ni();
	    
	    long ans = 0, Pa = 0, Pb = 0;
	    for(int i = 0; i< N; i++){
	        if(Pa == Pb && A[i] == B[i])ans += A[i];
	        Pa += A[i];
	        Pb += B[i];
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new WWALK().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

#include
using namespace std;

int main() {
long int t,n,i,suma,sumb,p;
cin>>t;
while(t–)
{
cin>>n;
int a[n],b[n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
cin>>b[i];
suma=0;
sumb=0;
p=0;
for(i=0;i<n;i++)
{
suma+=a[i];
sumb+=b[i];
if(suma==sumb&&a[i]==b[i])
{
p+=a[i];
//cout<<i<<":";
}
}
cout<<p<<endl;
}
return 0;
}

Not able to understand why I got a WA in second subtask
Have a look https://www.codechef.com/viewsolution/33485325

/hey brother i had seen the problem late just before 5 min. remaining. Anyone have any idea how to check my code or how to submit it…
if anyone have any idea please reply.
and here is my code…
/
#include < iostream >
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
for(int i=0; i<t; i++){
int a,x=0,y=0,sum=0;
cin>>a;
int arr2[a],arr1[a];
for(int j=0; j<a; j++){
cin>>arr1[j];
}
for(int j=0; j<a; j++){
cin>>arr2[j];
}
for(int j=0; j<a; j++){
if(arr1[j]==arr2[j] && x==y){
sum+=arr1[j];
}
else{

        }
        x+=arr1[j];
        y+=arr2[j];
    }
    cout<<sum<<endl;
}
return 0;

}

You didn’t use long long int(Read Side tip in editorial)

It is a competition dude ! :neutral_face:
You can not submit your code once time is over. But you can submit and check on practice section page for the same question. Hope you got it…

#include <stdio.h>

int main(){
int i, T;
scanf("%d", &T);

for(i = 1; i <= T; i++){
	int i, N, arr[100000], brr[100000], res = 0, dist_a = 0, dist_b = 0;
	scanf("%d",&N);
	for(i = 0; i < N; i++){
		scanf("%d", &arr[i]);
	}
	for(i = 0; i < N; i++){
		scanf("%d", &brr[i]);
		dist_a += arr[i];
		dist_b += brr[i];
		if(dist_a == dist_b && arr[i] == brr[i]){
			res += arr[i];
			dist_a = 0;
			dist_b = 0;
		}
	}
	printf("%d\n", res);
}
return 0;
}

I am getting WA on second subtask. Can anyone explain why?

Same Here. Use long long instead of int.

At least you should not write this line in the problem :sweat_smile: "the total weird distance. It can be proved that this distance is an integer. " Because of this many have got WA in 2nd subtask.

2 Likes

Thanks… :slight_smile: :stuck_out_tongue:

#include<bits/stdc++.h>
#define ll long long
//#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);
#define md 1000000000+7
using namespace std;

int main()
{
IOS;
ll tc;
cin>>tc;

for(ll t=0;t<tc;t++)
{
    ll n;
    cin>>n;
    ll *arr1 = new ll [100001];
    //ll arr1[n+1];
    arr1[0]=0;
    for(ll i=1;i<n+1;i++)
    {
        ll k;
        cin>>k;
        arr1[i]=k+arr1[i-1];
        
    }
    ll arr2=0;
    ll sum=0;
    ll prev=0;
    for(ll i=1;i<n+1;i++)
    {
        ll m;
        cin>>m;
        arr2=arr2+m;
        if(arr1[i-1]==prev && arr1[i]==arr2)
        {
            sum=sum+arr1[i]-arr1[i-1];
        }
        prev=arr2;
    }
    cout<<sum<<"\n";
  }   

}

Can someone plz tell why am i getting SIGSEGV?

I am getting second subtask 2 as WA, can someone point out the error in my code. The 1st subtask test cases got accepted.
Please help

#include <stdio.h>
int main() {
	long long int a[100001],b[100001],p1=0,p2=0,sum=0;
	long long int i,j,t,n;
	scanf("%lld",&t);
	for(i=1;i<=t;i++){
	    scanf("%lld",&n);
	for(j=1;j<=n;j++)
	    scanf("%lld",&a[j]);
	    for(j=1;j<=n;j++)
	    scanf("%lld",&b[j]);
	    for(j=1;j<n;j++){
	    p1=p1+a[j];
	    p2=p2+b[j];
	    
	    if(p1==p2){
	        if(a[1]==b[1] && j==1 )
	        sum=sum+a[1];
	         if(a[j+1]==b[j+1])
	        sum=sum+a[j+1];
	    }
	    }
	    printf("%d\n",sum);
	    sum=0;
	    p1=0,p2=0;
	}
	return 0;
}
1 Like

What’s wrong with my code?

#include <bits/stdc++.h>
#define ll long long
// #define C cin>>
using namespace std;

//O(n^2) approach

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n;cin>>n;
// int a[n],b[n];
vectora(n),b(n);
ll total=0;
vectorpre1(n,0),pre2(n,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
pre1[i]+=a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
pre2[i]+=b[i];
if((pre1[i]-a[i]==pre2[i]-b[i])&&(a[i]==b[i]))total+=a[i];
}
cout<<total<<"\n";
}

return 0;

}

If u have not given any custom input then it may leads to run time error. Try giving any input then u will get ur answer.

1 Like

update value of suma and sumb after checking if condition

for _ in range(int(input())):
N = int(input())
da = 0
db = 0
wd = 0
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(N):
if(da == db):
if(a[i] == b[i]):
wd += a[i]
da += a[i]
db += b[i]
# print(da, db)
print(wd)

here’s my code for wwalk in PYTH 3.6.^^

#include <iostream>
using namespace std;

int main() {
    int test_cases;
    cin >> test_cases;
    while(test_cases)
    {
        int n;
        cin >> n;
        long long walk {};
        long long A[n+1],B[n+1];
        A[0] = 0;
        B[0] = 0;
        for(int i=1;i<=n;i++)
        {
            long long x;
            cin >> x;
            A[i] = x + A[i-1];
        }
        for(int i=1;i<=n;i++)
        {
            long long x;
            cin >> x;
            B[i] = x + B[i-1];
        }
        for(int i=1;i<=n;i++)
        {
            if(A[i-1]==B[i-1] && A[i]==B[i])
            {
                walk += A[i] - A[i-1];
            }
        }
        cout << walk <<"\n";
        test_cases--;
    }
    return 0;
}
*indent preformatted text by 4 spaces*

i am getting WA error in this problem anyone solve this error
https://www.codechef.com/viewsolution/33517816

`#include<bits/stdc++.h>

using namespace std;
int main()
{
long long int i,j,N,sum,T,suma,sumb;
cin>>T;
int result[T];
for(i=0;i<T;i++)
{
sum=0;
cin>>N;
int Alice[N];
int Bob[N];
suma=0;sumb=0;
for(j=0;j<N;j++)
cin>>Alice[j];
for(j=0;j<N;j++)
cin>>Bob[j];
for(j=0;j<N;j++)
{
if(Alice[j]==Bob[j]&&suma==sumb)
sum+=Alice[j];
suma+=Alice[j];
sumb+=Bob[j];
}
result[i]=sum;
}
for(i=0;i<T;i++)
cout<<result[i]<<"\n";
}
`
pls guide me where i m making the mistake i m not able to clear the 2nd subtask

Because the sum can be greater than 10^9 and you have used int to store the sum which isn’t enough.Just declare a_stap,b_stap and wiard with long instead of int and then you will get AC for even subtask 2.