Linkus's blog

By Linkus, history, 7 years ago, In English

Hello Codeforces, on the 1st stage of the lastest Polish Olympiad in Informatics, appeared a problem which I could not get full score for. I would be very thankful, could somebody provide me with an efficient solution.

Self-translated statement: (Różnorodność, in Polish https://szkopul.edu.pl/problemset/problem/eHGwrk9xShVF-z_2f7K4Yyb_/statement/)

You're given a 2d array of integers. Subarrays of this array, of size KxK we will call it's K-fragments. "Diversity" of a K-fragment we will call the number of different elements it contains. You are to count the max diversity of a K-fragment, out of all possible and the sum of diversities from all K-fragments of the array.

Input: First line contains 3 integers m,n,K denoting the array size (mxn) and size of fragments (KxK). m,n,K <= 3000

The next m lines has n integers being the successive numbers of the array. The numbers are in interval [1,100000].

Example:

For input:             the right output is:
3 5 2                  4 20
1 5 3 3 3
4 1 3 3 4
4 2 4 4 3

The memory limit is 512MB, time limit 15 seconds.

I made a solution, which traversed through every K-fragment, by erasing the first K element column of the previous fragment, and including new column of K elements.

For that I got only 64 points from a total of 100.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it