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. 
"the total weird distance. It can be proved that this distance is an integer. " Because of this many have got WA in 2nd subtask.
