CCC '19 S5 - Triangle: The Data Structure

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M
Author:
Eliden
Problem type
Canadian Computing Competition: 2019 Stage 1, Senior #5

In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size M consists of M rows, with the i^{th} row containing i elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:

A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing (3,1,2) and the triangle containing (4,6,1)), three sub-triangles of size 3 (one of which contains (2,2,1,1,4,2)). Note that every triangle is a sub-triangle of itself.

You are given a triangle of size N and must find the sum of the maximum elements of every sub-triangle of size K.

Input Specification

The first line contains two space-separated integers N and K (1 \le K \le N \le 3\,000).

Following this are N lines describing the triangle. The i^{th} of these lines contains i space-separated integers a_{i,j} (0 \le a_{i,j} \le 10^9), representing the i^{th} row of the triangle.

For 4 of the 15 available marks, N \le 1000.

Output Specification

Output the integer sum of the maximum elements of every sub-triangle of size K.

Sample Input

4 2
3
1 2
4 2 1
6 1 4 2

Output for Sample Input

23

Comments


  • -1
    Kytabyte  commented on Oct. 19, 2020, 3:22 p.m. ← edit 4

    Seems I keep getting TLE on batch 2 with the \mathcal{O}(N^2 \log^2 N) approach introduced in the editorial. Any way to optimize it?

    Update: just figured out an \mathcal{O}(N^2 \log K) solution and passed.


    • 0
      PotRoast27  commented on May 30, 2021, 7:05 p.m.

      My solution is also O(N^2logK) but it TLEd :(

      any help would be appreciated


      • 3
        BalintR  commented on May 30, 2021, 10:16 p.m. ← edit 2

        This problem needs faster I/O. Try adding

        cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

        to your code.


        • 1
          aaronhe07  commented on Oct. 9, 2022, 8:24 p.m. ← edited

          Wow, I resubmitted my old solution with fast I/O and it worked. I never would have guessed.


        • 2
          Nils_Emmenegger  commented on May 31, 2021, 12:41 a.m.

          According to this codeforces blog, cout.tie(0) has no effect because cout is already tied to NULL. I briefly tested it myself and it seems to check out.


  • 0
    noYou  commented on Aug. 15, 2020, 4:17 p.m. ← edit 6

    Can java have a language specific limit, since bufferedReader takes 0.5s (half the given runtime) to take input in the worst case?

    EDIT: Solved it after like 60 submissions. The input is stupidly large, but you can get past it using System.in.read instead of regular Buffered Reader (alternatively, you can be good at coding and have a proper solution that easily passes, but if you're bad like me this MIGHT do the trick):

    public static int readIntFASTAF() throws IOException {
    int ans = 0;
    while(true) {
        int next = System.in.read();
        if(next == -1) break;
        if(next == 32) break;
        if(next == 10) break;

        ans *= 10;
        ans += next-48;
    }
    return ans;
}

    • 2
      rpeng  commented on Sept. 3, 2020, 6:42 p.m.

      Does java have the equivalent of a `get line' function that reads in a line of char, w/o any parsing?

      What's the runtime of that when reading the 3000 lines of the input file?


      • -1
        noYou  commented on Sept. 3, 2020, 8:00 p.m.

        is System.in.read() what you meant? That's the one I reccomended over buffered reader here. Bufferedreader takes 0.5s, but system.in.read takes ~0.2s with the above function.


  • 3
    ASmartWalrus  commented on Jan. 15, 2020, 2:36 a.m.

    I can't seem to have my code get full points, I keep getting TLE on Batch 3 Case 3. This is despite having the CCCgrader pass my code? Can anyone help?


    • 4
      c  commented on Jan. 15, 2020, 3:01 a.m.

      CCC Grader is too fast and the data seems to be not strong enough to break this solution.


    • 5
      Plasmatic  commented on Jan. 15, 2020, 3:00 a.m. ← edited

      Your solution is O(N^3) which cannot pass when N=3000

      CCCGrader is just stupid fast


      • 1
        Dingledooper  commented on March 12, 2020, 6:15 a.m.

        I just tried submitting an O(N^2K) DP solution, and it passes.


        • 1
          sushi  commented on March 12, 2020, 1:13 p.m.

          This is due to the new judges. It looks like we need to adjust the time limit.


  • 3
    AryanG  commented on Sept. 26, 2019, 11:33 p.m.

    Is there a specific reason as to why I might get an IR in python 3. It doesn't actually tell me what went wrong although the status codes indicate it should.


    • 8
      N3RDSLQYER84  commented on Sept. 27, 2019, 9:42 p.m.

      You recur too many times(RecursionError).


      • 3
        AryanG  commented on Sept. 28, 2019, 2:01 p.m.

        Thanks