# Problem solving

# Problem solving

fengyuxue11011 + 0 comments it's a weird problem. Hard to understand.

vrotaru_md + 3 comments I'm looking at the second test case

5 1

5 3 4 5 6

And don't understand can it be solved in a day. We have 2 problems with the same difficulty level - 5.

Solving two problems with same difficulty in a day will be against the rules, right ?

nishant_304 + 0 comments [deleted]GrantDuan + 0 comments 5 in '5 3 4 5 6' do not mean difficulty.

ashwinscode + 1 comment It says that the two

**consecutive**problems that you solve in a given day should have a minimum difference of K in their vi ( and not every pair of problems that you solve in a given day)n=5, k=1; 5 3 4 5 6 is can be solved in a given day because that sequence has atleast a variation of 1 between consecutive numbers that is met.

However, if instead it was n=3, k=1; 5 5 6, then you need minimum 2 days to solve it.

pazdaniel7 + 1 comment It also mentions that the difficulty of problems within a same day must increase . So you cannot solve 3 4 5 5 6 in that order on a same day, because you are not increasing difficulty from 5 to 5. Therefore, I have the same doubt, seems like you need 2 days to solve the second example for me too.

reyvaj64 + 0 comments I can only assume that: " Problems with similar vi values are similar in nature" means you can solve all fives at the same time, but that might be stretching it

mesutekici + 1 comment Hi,

I still have hard time understanding why 5 3 4 5 6 can be solved on the same day as 5 and 5 are similar in nature and 5-5 = 0. But k=1, which means that 5 and 5 cannot be solved on the same day.

regards

CS_1716410156 + 0 comments did u understand that now?? coz i am not getting this same query..

rangansit + 7 comments n=8 k=51 , a[8] = {49 ,57 ,3, 95, 98, 100, 44, 40} we'll have 3 57, 40 95, 44 98 , 49 100 => 4 days total How come 3 is the answer??

dheerajHackerRank Admin + 1 comment Hi @rangansit, [57,3,95,44] [49,100] [98,40] This gives 3.

rangansit + 0 comments But in the problem statement it is given that You’ve decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Then how can the solution be 57,3,95,44

dheerajHackerRank Admin + 2 comments 57th difficulty is 1. 3 difficulty is 2. 95 difficulty is 3. 44 difficulty is 4. so the difficulty level is increasing. The difficulty rating is the index of every element. The vi rating is the value at that array index

tlambrou + 0 comments Perhaps for clarity it would be better to call vi a "simliarity" rating or something that describes a type/category, or cardinality instead of something that is ordinal like a "rating" or "ranking". It's frustrating to have to spend time to understand a problem because of unclear language.

rangansit + 0 comments oops....Thanks a lot!

andrewmasj + 0 comments [deleted]

muthiahpriyanka + 0 comments # include

# include

# include

# include

# include

# include

# include

# include

# include

# include

using namespace std;

# define maxn 310

vectora[maxn]; bool visit[maxn]; int match[maxn]; int n; bool find(int x) { for (int i = 0; i < a[x].size(); i ++) { if (!visit[a[x][i]]) { visit[a[x][i]] = true; if (match[a[x][i]] == -1 || find(match[a[x][i]])) { match[a[x][i]] = x; return true; } } } return false; }

int main() { // freopen("data.txt", "r", stdin); int t; cin >> t; int k; int d[maxn]; while (t --) { cin >> n >> k; for (int i = 0; i < n; i ++) { a[i].clear(); cin >> d[i]; match[i] = -1; } for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j ++) { if (abs(d[i] - d[j]) >= k) { a[i].push_back(j); } } }

`int res = 0; for (int i = 0; i < n; i ++) { memset(visit, false, sizeof(bool) * maxn); res += find(i); } cout << n - res << endl;`

} return 0; }

muthiahpriyanka + 0 comments # include

# include

# include

# include

# include

# include

# include

# include

# include

# include

using namespace std;

# define maxn 310

vectora[maxn]; bool visit[maxn]; int match[maxn]; int n; bool find(int x) { for (int i = 0; i < a[x].size(); i ++) { if (!visit[a[x][i]]) { visit[a[x][i]] = true; if (match[a[x][i]] == -1 || find(match[a[x][i]])) { match[a[x][i]] = x; return true; } } } return false; }

int main() { // freopen("data.txt", "r", stdin); int t; cin >> t; int k; int d[maxn]; while (t --) { cin >> n >> k; for (int i = 0; i < n; i ++) { a[i].clear(); cin >> d[i]; match[i] = -1; } for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j ++) { if (abs(d[i] - d[j]) >= k) { a[i].push_back(j); } } }

`int res = 0; for (int i = 0; i < n; i ++) { memset(visit, false, sizeof(bool) * maxn); res += find(i); } cout << n - res << endl;`

} return 0; }

chenyg + 0 comments Python就是爽

def hung(i,s): for x in E[i]: if F[x]!=s: F[x]=s if B[x]==-1 or hung(B[x],s): B[x]=i return 1 return 0 for _ in range(int(input().strip())): N,K = map(int,input().strip().split(' ')) D,F,B = [int(x) for x in input().strip().split()],[-1]*N,[-1]*N E = [list(filter(lambda j:abs(D[j]-D[i])>=K,range(i+1,N))) for i in range(N)] print(N - sum(map(lambda i :hung(i,i),range(N))))

prakhar_070 + 1 comment I have a doubt here. I was trying to use a relatively simpler approach but its giving me wrong answer.I simply iterated through all the elements and considering each of these previously unvisited elements as starting point i looked for elements that could fullfil the given condition. Here is my solution.

#include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n,k,cnt=0; cin>>n>>k; int arr[n]; bool vis[n]; memset(vis,false,sizeof(vis)); for(int i=0;i<n;i++){cin>>arr[i];} for(int i=0;i<n;i++) { if(!vis[i]) { vis[i]=true; int var=arr[i]; for(int j=i+1;j<++) { if(!vis[j] and abs(arr[j]-var)>=k) { vis[j]=true; var=arr[j]; } } cnt++; } } cout<<cnt<<endl; } return 0; }

please tell me where i have gone wrong

aclowes + 1 comment I tried something very similar to this which did not work. I believe this is because choosing the first allowed value is not always best. Consider the case N = 5, K = 5, [V_i] = [7, 1, 2, 7, 6]. The algorithm will pick [7, 1, 7], [2], [6] giving 3 subsets. But choosing [7, 1, 6], [2, 7] results in just 2 subsets.

prakhar_070 + 0 comments Ohh...thanks!!

pb1038 + 0 comments testcase #1 [113 , 128]

Expected output is 5, where as my solution solves in 3 dayz. And seems correct to me..

Day 1 :: 383 694 335 335 160 986 355 762 973 542 717 853 663 483 218 16 507 852 365 791 264 492 173 38 538 860 281 988 857 591 342 971 353 666 512 70 518 362 84 352 113 301 507 639 365 33 876 680 142 413 970 637 171 957 761 466 315 887 184 40 970 536 153 622 394 791 290 110 632 265 736 549 296 878 314 834 199 950 356 156 794 469 157 961 824 287 678 141

Day 2 :: 422 422 958 763 400 155 829 668 490 155 539 845 650 815 327 674 934 172 359

Day 3 :: 440 851 174 872 105 246

Am I missing any constraint??

clarson + 0 comments Can someone share how to use the STDIN and STDOUT for the built-in Java 7/8 Compilers? I'm used to the netbeans IDE which uses System.in

Sort 17 Discussions, By:

Please Login in order to post a comment