In continue to topic 1.2
1 Like
Do you have screenshot of the first question or can you tell what the first question was about?
sharing it in new issue. last night it didnt allow me to create a new one in next 24hr. so wait
How did you get to know about this contest ? I mean was it a public or private contest ?
cool!! Some post sols please!!
2 Likes
Here is a possible solution to the problem Elys with Matrix.
This is an O(NlogN) solution. This is because it stores data in a set which uses log N for storage and retrieval.
Here N will be m*n as it is 10^5.
Kindly share your thoughts and any possible corrections to the solution.
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
int main()
{
set <ll> occurance ;
ll m, n ;
cin >> m >> n ;
ll matrix[m][n] ;
ll pos, length = 0 ;
for(ll i =0 ; i < m ; i++)
{
for(ll j = 0 ; j < n; j++)
{
cin >> matrix[i][j] ;
occurance.insert(matrix[i][j]) ;
}
}
auto first = occurance.begin() ;
ll num ;
for(ll i = 0 ; i < m ; i++)
{
for(ll j = 0 ; j < n ; j++)
{
auto last = occurance.find(matrix[i][j]) ;
// cout << "last -- > " << *last << endl;
num = distance(first, last) + 1 ;
// cout << "distance --> " << num << endl;
matrix[i][j] = num ;
}
}
for(ll i = 0 ; i< m ; i++)
{
for(ll j = 0 ; j < n; j++)
{
cout << matrix[i][j] << " " ;
}
cout << endl;
}
}The output for
2 7
3 2
must be
1 2
2 1
1 Like
thats right this is the right sol to ur input
Dude, yesterday I submitted code following same approach as yours. In fact, after the test, I had a talk with all of my friends who participated and everybody did pretty much the same. It passed only 5/13 test cases.
Rank should be minimized and if you observe carefully,
1 2
2 1
satisfies all the given criteria : Larger number has larger rank, smaller number has smaller rank, equal numbers having same row/column number can have same rank(not applicable in this example though)
2 Likes
Okay! Maybe now when I look it like this, I see the error.
Thanks !!
It was off campus hence any one could participate…check code nations fb page for further updates. test rescheduled on 21st I guess.
Here is A possible slution to Elys With matrtix:
m,n=[int(x) for x in input().split()]
matrix=[]
for i in range (m):
x=[]
x = list(map(int, input("Enter a multiple value: ").split()))
matrix.append(x)
t=()
t=tuple(matrix)
f=set()
for i in range (m):
s=()
s=set(matrix.pop())
for j in s:
f.add(j)
f=list(f)
matrix=list(t)
for l in range (len(f)):
for i in range (m):
for j in range (n):
if matrix[i][j]==f[l]:
matrix[i][j]=l+1
print(matrix)
`
I think this should work-
Firstly assign ranks from 1 like @anon28120812 did.
Iterate to (i,j) in order of increasing rank ,r :
NewRank(i,j) = max(max element in row less than r,max element in column less than r)+1
2 Likes
I was discussing this question with @taran_1407 and we both agreed that it is dp + bitmask.
His solution is better and clearer than mine so I’d tag him to explain. Essentially he made states as dp[mask] = Number of teams which can be formed if people are chosen according to mask (‘1’ means that person is chosen, ‘0’ means not chosen)
1 Like
I couldn’t login to the test that day but here is my solution for Project Allocation //// Created by Naman Bhalla on 2019-07-15.//#include <bits/stdc++.h>u - Pastebin.com . A short explanation is dp[i][j][k] where maximum groups till ith person with current status as j and k = 0 => no single group yet, 1 => one single group.
1 Like