3rd time writing this blog since no one could find the error of a 1200-rated problem before!

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	maomao90	164
2	Um_nik	163
3	atcoder_official	158
3	cry	158
3	-is-this-fft-	158
6	awoo	156
7	adamant	154
7	nor	154
9	TheScrasse	153
10	Dominater069	152

1846C - Rudolf and the Another Competition

My Code

using ll = long long;

void solve() {
   int n, m, t;
   cin >> n >> m >> t;
   vector<vector<int>> a(n, vector<int>(m));
   vector<tuple<int, ll, int>> tp; 
   for (int i = 0; i < n; i++) {
      for (int k = 0; k < m; k++) {
         cin >> a[i][k];
      }
      sort(a[i].begin(), a[i].end());
      int cnt = 0;
      int sum = 0;
      ll pen = 0;
      for (int k = 0; k < m; k++) {
         if (sum + a[i][k] <= t) {
            sum += a[i][k];
            pen += sum; 
            cnt += 1;
         } else {
            break;
         }
      }
      tp.emplace_back(cnt, pen, i);
   }
   sort(tp.begin(), tp.end(), [&](tuple<int, ll, int> a, tuple<int, ll, int> b) {
      if (get<0>(a) == get<0>(b)) {
         return get<1>(a) < get<1>(b);
      } 
      return get<0>(a) > get<0>(b);
   });
   int ans = 0;
   for (int i = 0; i < n; i++) {
      if (get<2>(tp[i]) == 0) {
         ans = i + 1;
         break;
      }
   }
   cout << ans << "\n";
}

I don't know why my code is not working even though the approach is correct, and I don't see anything wrong with my code. Even the 10th test case where it failed should give the right answer, according to me. I would be grateful if you could find out where the error is.

Comments (4)

Write comment?

Jsanchez1011

3 hours ago, # |

yeah i found your problem.

The problem is how you find the rudolf result, you put rudolf the id 0, but in the sort function you not drive the case where the amount of problems and the penalizing are the same.

For example imagine there is two competidor, they have 1 1 0, and 1 1 1, so at the moment to sort there are two possibles case: {[1 1 0], [1 1 1]} or {[1 1 1], [1 1 0]}. And in the stament say you have to get the first if there is and draw.

The solution

You can compare by problems and pen for found the score of rudolf, or put another case (the id) in the lambda sort when the problems and the penalize are equal

if (get<0>(a) == get<0>(b) && get<1>(a) == get<1>(b)){
         return get<2>(a) < get<2> (b);
}

→ Reply

Adityaxv

36 minutes ago, # ^ |

Thanks for replying! Your solution worked.

If we sort vector<pair<int, int>> pr using the default std::sort function, it automatically sorts the pr.second value in non-decreasing order if the pr.first values are equal.

So, I always thought that we don't need to specify the sort function if we want their value sorted in non-decreasing order if the previous values are equal.

But guess it is not true for more than two values! I even implemented your approach before, but I made mistakes in implementing that :(

25 minutes ago, # ^ |

i'm not sure, but when you used a personalized comp, you replace the default like you said, so if you will use a lambda sort, remember that you are doing is replace the default comparator to your new fuction, so be sure in thinking in all cases...

(please correct me if i'm wrong)

6 minutes ago, # ^ |

I checked with vector<pair<int, int>>. You are right! We have modified the sort function so it won't sort automatically the non-specified value in a non-decreasing order.

Adityaxv's blog