# Atcoder beginner challenge 202 - C - can't figure out what's wrong

#include<bits/stdc++.h>

#define endl ‘\n’

#define ll long long

#define debug(x) #x<<": "<<x

#define armax 100001

ll a[armax];

ll b[armax];

ll c[armax];

ll btmp[armax];

using namespace std;

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

ll n;

cin>>n;

ll bsize[armax+1];

memset(bsize,0,armax);

for(ll i  = 0;i<n;i++)

cin>>a[i];

for(ll i  = 0;i<n;i++)

{

cin>>b[i];

btmp[i] = b[i];

}

for(ll i  = 0;i<n;i++)

cin>>c[i];

sort(btmp,btmp+n);

sort(c,c+n);

for(ll i = 0;i<=n;i++)

{

if(binary_search(c,c+n,i+1))

{

ll nooftimes = upper_bound(c,c+n,i+1)-lower_bound(c,c+n,i+1);

bsize[b[i]]+=nooftimes;

}

}

vector<ll> bpositions;

for(ll i = 0;i<n;i++)

if(binary_search(btmp,btmp+n,a[i]))

bpositions.push_back(a[i]);

ll ans = 0;

for(ll pos:bpositions)

ans+=bsize[pos];

cout<<ans;


}
here’s my code. I have looked at the editorial and felt that my approach is very similar to that mentioned in it. But, I can’t seem to find what’s wrong. This gives WA on bound_00 and bound_01. Any help would be appreciated.

1 Like

In this problem you find How many pairs (i,j) where Ai = B(ci)
so firslty you count in map : map[B[C[i]]]++; for all i
and print the ans.

my Java Code:

import java.util.*;
import java.io.*;
import java.math.*;

/**
*
*/

/**
* Main , Solution , Remove Public
*/
public class Main {

public static void process() throws IOException {

int n = sc.nextInt();
int count[] = new int[n+1];
int freq[] = new int[n+1];

for(int i = 0; i<n; i++) {
count[b[c[i]-1]]++;
freq[b[i]]++;
}
long ans = 0;
for(int i =0; i<n; i++) {
int val = a[i];
int ff = count[val];
ans+=ff;
}
System.out.println(ans);

}

//=============================================================================
//--------------------------The End---------------------------------
//=============================================================================
private static long INF = 2000000000000000000L, M = 1000000007, MM = 998244353;
private static int N = 0;

private static void google(int tt) {
System.out.print("Case #" + (tt) + ": ");
}

static FastScanner sc;
static PrintWriter out;

public static void main(String[] args) throws IOException {
boolean oj = true;
if (oj) {
sc = new FastScanner();
out = new PrintWriter(System.out);
} else {
sc = new FastScanner(100);
out = new PrintWriter("output.txt");
}
int t = 1;
//		t = sc.nextInt();
int TTT = 1;
while (t-- > 0) {
process();
}
out.flush();
out.close();
}

static class Pair implements Comparable<Pair> {
int x, y;

Pair(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int compareTo(Pair o) {
return Integer.compare(this.x, o.x);
}

//		 @Override
//		    public boolean equals(Object o) {
//		        if (this == o) return true;
//		        if (!(o instanceof Pair)) return false;
//		        Pair key = (Pair) o;
//		        return x == key.x && y == key.y;
//		    }
//
//		    @Override
//		    public int hashCode() {
//		        int result = x;
//		        result = 31 * result + y;
//		        return result;
//		    }
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

static void println(Object o) {
out.println(o);
}

static void println() {
out.println();
}

static void print(Object o) {
out.print(o);
}

static void pflush(Object o) {
out.println(o);
out.flush();
}

static int ceil(int x, int y) {
return (x % y == 0 ? x / y : (x / y + 1));
}

static long ceil(long x, long y) {
return (x % y == 0 ? x / y : (x / y + 1));
}

static int max(int x, int y) {
return Math.max(x, y);
}

static int min(int x, int y) {
return Math.min(x, y);
}

static int abs(int x) {
return Math.abs(x);
}

static long abs(long x) {
return Math.abs(x);
}

static long sqrt(long z) {
long sqz = (long) Math.sqrt(z);
while (sqz * 1L * sqz < z) {
sqz++;
}
while (sqz * 1L * sqz > z) {
sqz--;
}
return sqz;
}

static int log2(int N) {
int result = (int) (Math.log(N) / Math.log(2));
return result;
}

static long max(long x, long y) {
return Math.max(x, y);
}

static long min(long x, long y) {
return Math.min(x, y);
}

public static int gcd(int a, int b) {
BigInteger b1 = BigInteger.valueOf(a);
BigInteger b2 = BigInteger.valueOf(b);
BigInteger gcd = b1.gcd(b2);
return gcd.intValue();
}

public static long gcd(long a, long b) {
BigInteger b1 = BigInteger.valueOf(a);
BigInteger b2 = BigInteger.valueOf(b);
BigInteger gcd = b1.gcd(b2);
return gcd.longValue();
}

public static long lcm(long a, long b) {
return (a * b) / gcd(a, b);
}

public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}

public static int lower_bound(int[] arr, int x) {
int low = 0, high = arr.length, mid = -1;

while (low < high) {
mid = (low + high) / 2;

if (arr[mid] >= x)
high = mid;
else
low = mid + 1;
}

return low;
}

public static int upper_bound(int[] arr, int x) {
int low = 0, high = arr.length, mid = -1;

while (low < high) {
mid = (low + high) / 2;

if (arr[mid] > x)
high = mid;
else
low = mid + 1;
}

return low;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

static class FastScanner {
StringTokenizer st;

FastScanner() throws FileNotFoundException {
}

FastScanner(int a) throws FileNotFoundException {
}

String next() throws IOException {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() throws IOException {
return Integer.parseInt(next());
}

long nextLong() throws IOException {
return Long.parseLong(next());
}

double nextDouble() throws IOException {
return Double.parseDouble(next());
}

String nextLine() throws IOException {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}

int[] readArray(int n) throws IOException {
int[] A = new int[n];
for (int i = 0; i != n; i++) {
A[i] = sc.nextInt();
}
return A;
}

long[] readArrayLong(int n) throws IOException {
long[] A = new long[n];
for (int i = 0; i != n; i++) {
A[i] = sc.nextLong();
}
return A;
}
}

static void ruffleSort(int[] a) {
Random get = new Random();
for (int i = 0; i < a.length; i++) {
int r = get.nextInt(a.length);
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
Arrays.sort(a);
}

static void ruffleSort(long[] a) {
Random get = new Random();
for (int i = 0; i < a.length; i++) {
int r = get.nextInt(a.length);
long temp = a[i];
a[i] = a[r];
a[r] = temp;
}
Arrays.sort(a);
}
}
1 Like

Actually during the contest I didn’t see the constraint that A, B, C have elements in the range [1, n]. I just solved generally with maps Anyways you can construct array d as d[i] = b[c[i]] and problem reduces to counting pairs of equal elements between a, d which can be done in \mathcal O(n) time (I implemented with maps, so mine was n \log n )

3 Likes

lol🤣

I understood the solution and I have been able to code the solution from scratch after the contest using the same idea as yours but I can’t seem to find what’s wrong in my solution that I posted above. I coded that during the contest and it gave me a WA. Wish I could see where its wrong.

@leo_valdez I implemented the same approach in Python but got AC in 10 test cases and TLE in rest. Any idea if AtCoder has a language multiplier system?

1 Like

I think usually Python has a larger multiplier than C++. I don’t think using a dict is as fast as using map in C++. But of course, I could be wrong. Maybe AtCoder does have a multiplier system, but I’m not sure…