vishaaaal's blog

Atcoder ACL 1 problem, getting Wrong Answer.
By vishaaaal, history, 4 years ago, In English

Hii!!! I took part in the Atcoder ACL contest 1 held a few days ago. Unfortunately, I am getting wrong answer in the first problem Reachable towns, here is my submission.

All I have done is to sort all cities according to x keeping their city numbers, and connect each city to next city with greater y and x coordinate than it with a bidirectional edge, and finally answer will be the size of connected component of graph for every city. Please tell me if I am incorrect somewhere.

Thanks in advance!!

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess because the relation is not transitive. Take three cities at (4, 6),(6, 8),(5, 3). Then {(4,6),(6,8)} ∈ R, {(6,8),(5,3)} ∈ R, but {(4,6),(5,3)}∉R

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even in this example, any city is reachable from the other.

    Let city 1 be at (4,6), 2 at (6,8), 3 at (5,3). Then you can reach city 2 from city 1 and city 3 from city 2, hence you can reach city 3 from city 1 too.

    This is shown in the sample test case 2 of the problem, where number of cities reachable from city 2 is 3. But point to be noted, the only directly reachable city is city 1, and since city 1 is connected to two extra cities, 2 more cities become reachable from city 2.

    In other words, indirectly reachable cities are to be counted.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Hmm what does your program get for this case:

https://www.imageupload.net/image/E6Vh2

If you're only connecting a point with the next one with greater y, then the edge between A and B will be drawn, but I think you'll miss the edge from A to C.

EDIT: Yup, that is the issue. On this test case:

3
1 1
2 3
3 2

Your output: 2 2 1

Answer: 3 3 3

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it 
import java.util.*;
import java.io.*;
public class Reachable_Towns {

	static int mod = (int) (1e9 + 7);
	static List<Integer> adj[];
	public static void main(String[] args) throws java.lang.Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int a[][]=new int[n][2];
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a[i][0]=Integer.parseInt(st.nextToken());
			a[i][1]=Integer.parseInt(st.nextToken());
		}
		adj=new ArrayList[n+1];
		for(int i=1; i<=n; i++) adj[i]=new ArrayList<>();
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(i!=j) {
					int x=a[j][0],y=a[j][1];
					if(a[i][0]>x && a[i][1]>y || a[i][0]<x && a[i][1]<y) {
						adj[i+1].add(j+1);
						
					}
				}
			}
		}
		for(int i=1; i<=n; i++) {
			int ans=1;
			for(int x: adj[i]) {
				ans+=adj[x].size();
			}
			System.out.println(ans);
		}
	}

}

In the first question, I have used this approach, but it is giving TLE, can anyone help me? How can I improve this approach and what modifications should I do here?

→ Reply