ADMIT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Implementation

PROBLEM

Given N colleges ranked from 1 to N from best to worst, each having exactly one seat available, and M students ranked by their performance in an entrance exam, and a list of colleges preferred by each student, all students are considered in order of their rank in exam. Student gets admission in college with best rank having a vacant seat, or none if no college in student’s preference has a seat.

Determine the college in which first student is admitted, or not admitted at all.

QUICK EXPLANATION

Just simulate the whole process, considering students in order of their rank while maintaining the status of seats available in each college.

EXPLANATION

This problem is mostly implementation, simulating the process of admission in colleges. First we reorder the students in the order of their rank. Hence student with rank 1 shall be admitted first, then student with second rank and so on.

The idea here is that we also need to keep track of lists corresponding to a student, so that when we reorder the students, the list is also reordered.

The best way to keep this relationship would be to encapsulate all information about the student, i.e. student id, student rank and list of college student has applied to, in a single object, so that we can reorder the whole information of student simultaneously.

An object would have class definition something like this

class Student{
    int id, rank;
    list<Integer> appliedTo;
}

For colleges, all we need to do is to keep track whether the seat in that college is vacant or not, which can be done by a boolean array.

Hence, we consider all students one by one. For current student, we iterate over all college this student applied to, find the one having best rank among those having vacant seat. If no such college is found, this student doesn’t get admission. Otherwise this student is admitted in that particular college, and that college no longer has vacant seat.

Hence, by simulation of this process, we can find all colleges having vacant seats when student 1 is processed, easily finding the college with best rank among these, to which student 1 applied.

This college is the required answer.

If having trouble with implementation, refer solutions below.

TIME COMPLEXITY

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
 
using namespace std;
 
const int maxt = 1e5, maxn = 1e5, maxm = 1e5, maxapp = 1e6, maxtn = 250000, maxtm = 250000;
 
int main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    int tn = 0, tm = 0, tapp = 0;
    while(t--){
        int n, m; cin >> n >> m;
        tn += n; tm += m;
        int rank[n + 1]; set<int> urank; urank.clear();
        int prank; 
        for(int i = 1; i <= n; i++){
            cin >> prank;
            rank[i] = prank; urank.insert(prank);
        }
        assert(urank.size() == n);
        
        int mark[m + 1]; set<int> umark; umark.clear();
        int pmark;
        for(int i = 1; i <= m; i++){
            cin >> pmark;
            mark[pmark] = i; umark.insert(pmark);
        }
        assert(umark.size() == m);
        
        vector<int> app[m + 1]; bool inc[m + 1]; memset(inc, false, sizeof(inc));
        for(int i = 1; i <= m; i++){
            app[i].clear();
            int k; cin >> k;
            tapp += k;
            int id;
            for(int j = 1; j <= k; j++){
                cin >> id;
                app[i].push_back(id);
            }
            sort(app[i].begin(), app[i].end(), [&rank](int &a, int &b){return rank[a] < rank[b];});
        }
 
        int ans[m + 1]; memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= m; i++){
            vector<int> papp = app[mark[i]];
            for(int x : papp){
                if(!inc[x]){
                    ans[mark[i]] = x;
                    inc[x] = true;
                    break;
                }
            }
        }
        cout << ans[1] << endl;
    }
}  
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>

#ifdef HOME
#define NOMINMAX   
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
	    char g = getchar();
	    if (g == '-') {
		    assert(fi == -1);
		    is_neg = true;
		    continue;
	    }
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    }
		    cnt++;
		    assert(fi != 0 || cnt == 1);
		    assert(fi != 0 || is_neg == false);

		    assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
	    }
	    else if (g == endd) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    return x;
	    }
	    else {
		    assert(false);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    // 		if(g == '\r')
	    // 			continue;

	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
    if (IsDebuggerPresent())
    {
	    freopen("../ADMIT_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 2'500'000);
    forn(tc, T)
    {
	    int N = readIntSp(1, 2'500'000);
	    int M = readIntLn(1, 3'000'000);
	    vector<int> A(N);
	    vector<bool> UA(N);
	    forn(i, N)
	    {
		    if (i + 1 == N)
			    A[i] = readIntLn(1, N);
		    else
			    A[i] = readIntSp(1, N);
		    A[i]--;
		    assert(UA[A[i]] == false);
		    UA[A[i]] = true;
	    }
	    vector<int> S(M);
	    vector<bool> US(M);
	    forn(i, M)
	    {
		    if (i + 1 == M)
			    S[i] = readIntLn(1, M);
		    else
			    S[i] = readIntSp(1, M);
		    --S[i];
		    assert(US[S[i]] == false);
		    US[S[i]] = true;
	    }
	    vector<pair<int, vector<int>>> KV(M);
	    forn(i, M)
	    {
		    KV[i].first = i;
		    int K = readIntSp(1, 1'500'000);
		    forn(j, K)
		    {
			    int tmp;
			    if (j + 1 == K)
				    tmp = readIntLn(1, N);
			    else
				    tmp = readIntSp(1, N);
			    --tmp;
			    KV[i].second.push_back(tmp);
		    }
	    }

	    int res = 0;
	    vector<bool> student(M);
	    vector<bool> coll(N);
	    forn(i, M)
	    {
		    //find the best available student
		    int bestStId = -1, bestStVal = M + 1;
		    forn(j, M)
		    {
			    if (student[j] == false && bestStVal > S[j])
			    {
				    bestStId = j;
				    bestStVal = S[j];
			    }
		    }
		    student[bestStId] = true;
		    //find best available college
		    int bestCollId = -1, bestCollVal = N + 1;
		    const auto& actkv = KV[bestStId];
		    for(const auto actkvi : actkv.second)
		    {
			    if (coll[actkvi] == false && bestCollVal > A[actkvi])
			    {
				    bestCollId = actkvi;
				    bestCollVal = A[actkvi];
			    }
		    }
		    if (bestCollId != -1)
		    {
			    coll[bestCollId] = true;
			    if (bestStId == 0)
			    {
				    res = bestCollId + 1;
				    break;
			    }
		    }
	    }
	    printf("%d\n", res);

// 		int res = 0;
// 		vector<bool> coll(N);
// 		sort(KV.begin(), KV.end(), [&S](const auto& a, const auto& b)->bool {
// 			return S[a.first] < S[b.first];
// 			});
// 		for (auto& kvi : KV)
// 		{
// 			int act = kvi.first;
// 			auto& akv = kvi.second;
// 			sort(akv.begin(), akv.end(), [&A](const auto& a, const auto& b)->bool {
// 				return A[a] < A[b];
// 				});
// 			for (const auto& akvi : akv)
// 			{
// 				if (coll[akvi] == false)
// 				{
// 					if (act == 0)
// 						res = akvi + 1;
// 					coll[akvi] = true;
// 					break;
// 				}
// 			}
// 		}
// 		printf("%d\n", res);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class ADMIT{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        //zero based indexing everywhere
        int N = ni(), M = ni();
        int[] collegeRank = new int[N];
        for(int i = 0; i< N; i++)collegeRank[i] = ni()-1;
        int[] score = new int[M];
        for(int i = 0; i< M; i++)score[i] = ni()-1;
        Student[] students = new Student[M];
        for(int i = 0; i< M; i++){
            int[] applied = new int[ni()];
            for(int j = 0; j< applied.length; j++)applied[j] = ni()-1;
            students[i] = new Student(i, score[i], applied);
        }
        Arrays.sort(students);
        boolean[] available = new boolean[N];
        Arrays.fill(available, true);
        int ans = -1;
        for(Student s:students){
            int assigned = -1;
            for(int college:s.appliedTo){
                if(!available[college])continue;
                if(assigned == -1 || collegeRank[college] < collegeRank[assigned])assigned = college;
            }
            if(assigned != -1)available[assigned] = false;
            if(s.id == 0){
                ans = assigned;
                break;
            }
        }
        pn(1+ans);
    }
    class Student implements Comparable<Student>{
        int id, rank;
        int[] appliedTo;
        public Student(int id, int rank, int[] applied){
            this.id = id;
            this.rank = rank;
            appliedTo = applied;
        }
        public int compareTo(Student s){return Integer.compare(rank, s.rank);}
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    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 ADMIT().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;
        }
    }
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define all(c) c.begin(), c.end()
#define show(x)            \
    for (auto it : x)      \
        cout << it << " "; \
    cout << endl;
bool colleges[50000];    //college availablity
int college_rank[50000]; // rank of colleges
int student_rank[50000]; 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, chef_rank, p, chef_college = 0;
        map<int, set<int>> db; // student rank and choice of colleges rank wise
        //after contest - no its college id wise
        //storing ranks will get id from unordered_map
        unordered_map<int, int> college_rank_db; //college rank, college id
        cin >> n >> m;
        fill(colleges, colleges + n, true);
        for (int i = 0; i < n; i++)
            cin >> college_rank[i], college_rank_db[college_rank[i]] = i + 1;
        cin >> chef_rank;
        student_rank[0] = chef_rank; // apna halwai
        for (int i = 1; i < m; i++)
            cin >> student_rank[i];
        for (int i = 0; i < m; i++)
        {
            int k, college_id;
            cin >> k;
            for (int j = 0; j < k; j++)
                cin >> college_id, db[student_rank[i]].insert(college_rank[college_id - 1]);
        }
        for (auto itr = db.begin(); itr != db.end(); ++itr)
        {
            bool chef = false;
            for (auto it = itr->second.begin(); it != itr->second.end(); it++)
            {
                if (colleges[college_rank_db[*it] - 1])
                {
                    colleges[college_rank_db[*it] - 1] = false;
                    if (itr->first == chef_rank)
                    {
                        chef_college = college_rank_db[*it];
                        chef = true;
                    }
                    break;
                }
            }
            if (chef)
                break;
        }
        cout << chef_college << "\n";
    }
    return 0;
}
2 Likes

I came across this situation many times where I was expecting the solution to work and I got a run time exception say ArrayOutOfBounds, Null Pointer etc… This is first time, where I was expecting an exception/some error it gave me AC. This is a bit implementation-heavy (at least for me), thought to submit before taking a second look at the implementation…Happy about it… This doesn’t happen always though :slight_smile:

https://www.codechef.com/viewsolution/43247813

#include<bits/stdc++.h>

#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;

class student

{

public:

int rank;

int id;

vector<int> list;

};

class college

{

public:

int rank;

int id;

bool vacancy;

};

bool compare(student a, student b)

{

return a.rank<b.rank;

}

int main()

{

speed;

int t;

cin>>t;

while(t--)

{

    int n,m;

    cin>>n>>m;

    student s[m];

    college c[n];

    for(int z=0;z<n;z++)

    {

        cin>>c[z].rank;

        c[z].id=z+1;

        c[z].vacancy=1;

    }

    int chefrank;

    for(int z=0;z<m;z++)

    {

        cin>>s[z].rank;

        if(z==0)

        {

            chefrank=s[z].rank;

        }

        s[z].id=z+1;

    }

    for(int z=0;z<m;z++)

    {

        int k;

        cin>>k;

        for(int y=0;z<k;y++)

        {

            int rr;

            cin>>rr;

            (s[z].list).push_back(rr);

        }

    }

    sort(s,s+m,compare);

    int i;

    for(i=0;i<chefrank-1;i++)

    {

        for(int z=0;z<s[i].list.size();z++)

        {

            if(c[s[i].list[z]].vacancy==1)

            {

                c[s[i].list[z]].vacancy=0;

                break;

            }

        }

    }

    bool b=1;

    for(int z=0;z<s[i].list.size();z++)

    {

        if(c[s[i].list[z]].vacancy==1)

        {

            b=0;

            cout<<c[s[i].list[z]].id<<endl;

            break;

        }

    }

    if(b)

    {

        cout<<"0"<<endl;

    }

}

return 0;

}

why this code gavies time limit exceeded error

@taran_1407 @iscsi can you plz help what I am doing wrong by any test cases or by making any correction in this code thanks Solution: 43294916 | CodeChef

I am getting WA , i dont know why can anyone help me out

#include<bits/stdc++.h>

using namespace std;

struct Student{

int rank;

int id;

vector<int> list;

};

bool compare(Student s1 , Student s2){

return s1.rank < s2.rank;

}

int main(){

ios_base::sync_with_stdio(false); 

cin.tie(NULL); 



int t;

cin >> t;

while(t--){

    int n,m;

    cin >> n >> m;

    unordered_map<int,int> college_list;

    for(int i = 1 ; i <= n ; i++){

        int x;

        cin >> x;

        college_list[x] = i;

    }

    Student arr[m+1];

    for(int i = 1 ; i <= m ; i++){

        cin >> arr[i].rank;

        arr[i].id = i;

    }

    for(int i = 1 ; i <= m ; i++){

        int k;

        cin >> k;

        vector<int> rank_list;

        for(int j = 0 ; j < k ; j++){

            int x;

            cin >> x;

            rank_list.push_back(x);

        }

        arr[i].list = rank_list;

    }

    sort(arr+1,arr+m+1,compare);

    bool present = false;

    for(int i = 1 ; i <=m ; i++){

        vector<int> temp =  arr[i].list;

        sort(temp.begin(),temp.end());

        for(int j = 0 ; j < temp.size() ; j++){

            if(college_list[temp[j]] != -1){

                if(arr[i].id == 1){

                    cout << college_list[temp[j]] << endl;

                    present = true;

                }

                college_list[temp[j]] = -1;

                break;

            }

        }

        if(arr[i].id == 1){

            break;

        }

    }

    if(!present){

        cout << 0 << endl;

    }

}

}

for(int y=0;z<k;y++) **
for(int y=0;y<k;y++)