Codenation Test Questions jul 15, 2019 topic 1.3

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 ?

1 Like

cool!! Some post sols please!!

1 Like

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

No @stark517 is right

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)

`

@vijju123 peep into these ques too. thnx

I think this should work-

Firstly assign ranks from 1 like @ghostbug 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

1 Like

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 https://pastebin.com/kisKNzEx . 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