my_name_is_khan's blog

By my_name_is_khan, 5 years ago, In English

Hi sir, We are facing a huge issue from last 3 contests. As the participant count have been constantly been 10k+ in past 3 contests. The queue is getting stuck for a long time. This issue is being constantly occurring. It really decreasing confidence in many of the coders. Kindly I request codeforces team to look into this problem and find an solution to this in future contests.

Thanks MikeMirzayanov

Full text and comments »

  • Vote: I like it
  • +190
  • Vote: I do not like it

By my_name_is_khan, 5 years ago, In English

I have tried to solve it for many times. But i cannot decrease complexity. Can anyone please help me ? Problem:

Given an array A of N integers. Find the number of good triplets (i, j, k), where i, j, k are all distinct indices such that 0 < i , j , k <= N. A good triplet (i, j, k) is a triplet such that the sum, S = A[i] + A[j] + A[k], is divisible by exactly one of A[i], A[j], or A[k].

Array values of a triplet (i,j,k) is (A[i], A[j], A[k]).

input: N=4 A=[1,2,2,1]

output: 12

Explanation : S=2+2+1=5 is divisible only by number 1 in the triplet and the triplet with array values 1, 1, 2 is not a good triplet as S = 4 is divisible by all three. So there are two triplets (1,2,2) and (2,2,1). Look at the i,j,k values which are indices. So, there are 12 possibilities of triplets of indices that can have array values as 2, 2, 1. They are:

(1, 2, 3), (1, 3, 2), (2, 1, 3), (3, 1, 2), (2, 3, 1), (3, 2, 1), (2, 3, 4), (2, 4, 3), (3, 2, 4), (4, 2, 3), (3, 4, 2), (4, 3, 2).

My attempt:

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int[] A=new int[N];
		for(int i=0;i<N;i++){
			A[i]=sc.nextInt();
		}
		Arrays.sort(A);
		int i,j,k,count=0;
		for(i=0;i<N;i++){
			for(j=i+1;j<N;j++){
				for(k=j+1;k<N;k++){
					if(getIfGood(A[i],A[j],A[k])) count+=6;
				}
			}
		}
		System.out.println(count);
	}
	
	static boolean getIfGood(int a, int b, int c){
		int count=0,sum=a+b+c;
		if(sum%a==0) count++;
		if(sum%b==0) count++;
		if(sum%c==0) count++;
		if(count==1) return true;
		return false;
	}
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it