Codeforces/recommendations.cpp at master · suraj95/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*

A news recommendation system daily selects interesting publications of one of n disjoint categories
for each user. Each publication belongs to exactly one category. For each category 𝑖 batch algorithm selects
ai publications.

The first line of input consists of single integer n — the number of news categories (1≤n≤200000).

The second line of input consists of n integers ai — the number of publications of i-th category selected
by the batch algorithm

The third line of input consists of n integers ti — time it takes for targeted algorithm to find one
new publication of category i

We have to find the minimal required time for the targeted algorithm to get rid of categories with the same size.


Input:

5
3 7 9 7 8
5 2 5 7 5

5
1 2 3 4 5
1 1 1 1 1

Output:

8 // distribution will be [4,11,10,8,9]
0 // distibution is already unique


Note- For the first test case, the answer is actually listed as 6 as that will add 3 new publications to
the second publication, making its count 10. But I believe it is incorrect because it doesn't take into
consideration the fact that other numbers will increase too. So at t=6, the distribution becomes
[3,10,10,7,9].

But at t=8 is the smallest possible time period we can add where we get a unique distribution of
[4,11,10,8,9].

*/


#define _CRT_SECURE_NO_WARNINGS

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>

using namespace std;


bool isUnique(std::vector<int> vec){

	set<int> s(vec.begin(), vec.end());

	return  vec.size()==s.size();

}


int minimal_time(int categories, std::vector<int> magazines, std::vector<int> time){


	if(isUnique(magazines)){
		return 0;
	}

	else{

		int extra_time=1;

		while(true){

			std::vector<int> temp_vec;  // reinitialize at every iteration

			for(int i=0; i<categories; i++){

				int new_publications=extra_time/time[i];
				temp_vec.push_back(magazines[i]+new_publications);
			}

			// break the loop the moment we get a unique distribution
			if(isUnique(temp_vec)){
				break;
			}

			extra_time++;
		}

		return extra_time;
	}

}

int main(){

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int num_categories;
	int result=-1;
	std::vector<int> magazines_vec;
	std::vector<int> time_vec;

	cin>>num_categories;

	for(int i=0;i<num_categories;i++){

		int batch_size;
		cin>>batch_size;

		magazines_vec.push_back(batch_size);
	}

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

		int time_taken;

		cin>>time_taken;
		time_vec.push_back(time_taken);
	}

	result=minimal_time(num_categories,magazines_vec,time_vec);

	cout<<result<<"\n";

	return 0;
}