SEATL - Editorial

editorial
, ,
8

I got only 30 pts, could not figure out the reason.
I was using approach for 100 pts using (multisets of pair). I inserted each element with row number in “rows” multiset and with column number in “columns” multiset. Then iterated over all elements finding the row with the max frequency of each element, then storing these row numbers with max frequency in another vector.The same procedure for columns.

This is my solution
https://www.codechef.com/viewsolution/9366100

Any help would be appreciated

2 Likes
9

Same approach :

Implementation

1 Like
10

Even a well implemented code with maps can pass for 100 points. AC Solution

Overall complexity is O(nm(logn+logm))

1 Like
11

i have used approx same approch with O[n*m] complexity but i dont know why i am getting wrong ans
please any one help to solve this 9427788

12

AC after 100+ submissions.
Really tough one though. :smiley:

Here’s how I cracked this problem : mysol

1 Like
13

how is it that the iterating over all max row and max column combinations of each number amounts to only NXM ? Isn’t it possible that a single row can be the max row for many numbers and similarly for columns? for example this 4X4 matrix:
{1 1 2 2},
{2 2 1 1},
{1 1 2 2},
{2 2 1 1}

14

I really expected much better from sereja. I am disappointed with this one.

15

@mogers In the second snippet given above, shouldn’t it be columns[a[j][i]] instead of columns[a[i][j]] ?

16

Can not see editorialist solution… :frowning:

17

int num = a[pi][pj];
if (pos[num].size() > 0){
int bestx = 0, besty = 0;
BX.clear(); BY.clear();
for (int p = 0; p < pos[num].size(); p++){
int x = pos[num][p].first;
int y = pos[num][p].second;

please explain this section of author’s solution.

18

Yes, as long as we use arrays. Using hash tables or binary search trees could add overheads that induce TLE. Sample implementation - CodeChef: Practical coding for everyone

1 Like
19

Thanks i got it, i was trying a lot of that kind of approach and endded up in TLE , and the overall complexity would be more than O(NxM) ,doesnt it depend on the number of distinct characters

20

I think these will be available soon, my code is at CodeChef: Practical coding for everyone

1 Like
21

I think these will be available soon, my code is at CodeChef: Practical coding for everyone

22

Its written that sum of n*m <= 10^6 over all test cases, which means that ‘t’ should’ve been fairly large in smaller subtasks :stuck_out_tongue:

1 Like
23

i think inserting in multiset would be taking larger time. Think for the case when all numbers are distinct and N*M is 10^6. This happened with me when i was using set.

1 Like
24

Note I mentioned O(NM), so within a constant factor of N*M).
The key is that the more times a row/column is best for a specific number, the less distinct numbers we have. While in your example both 1 and 2 have 4 options for each row/column, there are only 2 numbers to consider.

25

Oh okay that is true! Thanks :smiley:

26

Your link says “Access Denied.” This link is the real link to your solution. Also, I might be wrong, but I do not think you are accounting for the case where you need to subtract 1 because the row and column have the number in question at its intersection.

27

No, j processes columns and i the rows.