Hello Programmers In this post, you will know how to solve the College Admissions Codechef Solution. Problem Code: ADMIT
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
College admissions are starting and Chef has also recently completed his high school. There are NN colleges, numbered from 11 to NN, and they are ranked from 11 to NN. Each college has only a single seat left. To apply for the colleges, every student has to give a common exam, the result of which decides their destiny, i.e, the student having best rank (scoring max marks) gets to choose the college of their preference first.
Each student has a list of colleges that they like. They will want to get to the best-ranked college from their list. If they can’t get into it, they will want to get into the second-ranked college from among their list, and so on.
If the single vacant seat of a college gets filled, the admission for that year is closed in that college. Then, the people who have applied for that college have to look for a lower-ranked college in their preference list provided that it still has vacancies.
Given information about MM students, about their marks scored in the exam (given as ranks) and the id’s of the college they are applying for, find which college Chef will land into given that he is the student with id=1id=1.
Every student tries to get into the highest-ranked college on his list which has a vacancy and if not possible to get into any of the colleges on his list, he won’t join any college this year.
Input:
- First line will contain TT, number of testcases. Then the testcases follow.
- Each testcase contains M+3M+3 lines of input.
- First line contains 22 space separated integers NN, MM, the total number of colleges, and total number of students respectively.
- Second line contain NN distinct space separated integers RiRi, rank of the ithith college. Here 11 denotes a higher rank and NN denotes a lower rank.
- Third line contains MM distinct space separated integers SiSi, the rank of the ithith student in the exam. Here 11 denotes a higher rank, i.e, maximum marks scored and MM denotes a lower rank, i.e, minimum marks scored.
- Next MM lines contain K+1K+1 space separated integers which the first integer KK is the number of colleges ithith student will apply to and the next KK integers describe the same.
Output:
For each testcase, output in a single line the college in which Chef applies and 00 if he won’t be joining any college this year.
Constraints
- 1≤N,M≤5∗1041≤N,M≤5∗104
- RR is the permutation of integers from [1,N][1,N]
- SS is the permutation of integers from [1,M][1,M]
- Sum of NN over all tests is atmost 3∗1053∗105
- Sum of MM over all tests is atmost 3.5∗1053.5∗105
- Sum of KK over all students over all tests is atmost 1.5∗1061.5∗106
- Every student applies to atleast 11 college and all the applied colleges are different.
Sample Input 1
3
2 2
2 1
1 2
2 1 2
2 1 2
1 2
1
2 1
1 1
1 1
2 1
1 2
1
2 2 1Sample Output 1
2
1
Explanation
Case 1: Here since Chef has the highest rank, he gets to choose the highest rank college in his preference list first, that is college with id=2.
Case 2: Here since there is only 11 college and Chef stood second, he won’t be able to apply to any of the colleges this year, so we print id=0.
Case 3: Here since Chef is the only student and thus has the highest rank, he gets to choose the highest rank college in his preference list first, that is college with id=1.
College Admissions CodeChef Solution in JAVA
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Throwable {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int tc = 0; tc < T; ++tc) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] R = new int[N];
for (int i = 0; i < R.length; ++i) {
R[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
int[] S = new int[M];
for (int i = 0; i < S.length; ++i) {
S[i] = Integer.parseInt(st.nextToken());
}
int[][] applied = new int[M][];
for (int i = 0; i < applied.length; ++i) {
st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
applied[i] = new int[K];
for (int j = 0; j < applied[i].length; ++j) {
applied[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
out.append(solve(R, S, applied)).append("\n");
}
System.out.print(out);
}
static int solve(int[] R, int[] S, int[][] applied) {
Integer[] sortedIndices = new Integer[S.length];
for (int i = 0; i < sortedIndices.length; ++i) {
sortedIndices[i] = i;
}
Arrays.sort(sortedIndices, Comparator.comparing(i -> S[i]));
boolean[] used = new boolean[R.length];
for (int i = 0; ; ++i) {
int collegeIndex = -1;
for (int j : applied[sortedIndices[i]]) {
if (!used[j] && (collegeIndex == -1 || R[j] < R[collegeIndex])) {
collegeIndex = j;
}
}
if (collegeIndex != -1) {
used[collegeIndex] = true;
}
if (sortedIndices[i] == 0) {
return collegeIndex + 1;
}
}
}
}Disclaimer: The above Problem (College Admissions) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.