— Dark mode

Datatähti 2025 alku

Niitty

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Pikaksi
Submission time:2024-11-03 16:54:54 +0200
Language:C++ (C++20)
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#30
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.01 s2, 3, 4, 5, 6details
#7ACCEPTED0.01 s2, 3, 4, 5, 6details
#8ACCEPTED0.01 s2, 3, 4, 5, 6details
#9ACCEPTED0.01 s2, 3, 4, 5, 6details
#10ACCEPTED0.60 s3, 4, 5, 6details
#11ACCEPTED0.57 s3, 4, 5, 6details
#12--3, 4, 5, 6details
#13--3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 5, 6details
#17--4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21--5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Compiler report

input/code.cpp: In function 'bool closeLeftEdge(Fence, std::array<int, 26>&)':
input/code.cpp:33:51: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |         removedFlowers[field[fence.y + k][fence.x]] += 1;
      |                                                   ^
input/code.cpp: In function 'bool closeRightEdge(Fence, std::array<int, 26>&)':
input/code.cpp:55:69: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |         removedFlowers[field[fence.y + k][fence.x + fence.sizeX - 1]] += 1;
      |                                                                     ^
input/code.cpp: In function 'bool closeTopEdge(Fence, std::array<int, 26>&)':
input/code.cpp:76:51: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |         removedFlowers[field[fence.y][fence.x + k]] += 1;
      |                                                   ^
input/code.cpp: In function 'bool closeBottomEdge(Fence, std::array<int, 26>&)':
input/code.cpp:100:...

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

union Fence
{
    struct {
        uint16_t x;
        uint16_t y;
        uint16_t sizeX;
        uint16_t sizeY;
    };
    ll bytes;
};

bool containedNumbers[26] = {0};
vector<vector<char>> field;
//set<ll> elementaryFences;
//vector<Fence> eFencesFinal;
int n = 0;

void printFence(Fence fence)
{
    cout << fence.x << " " << fence.y << " " << fence.sizeX << " " << fence.sizeY << "\n";
}

bool closeLeftEdge(Fence fence, array<int, 26>& flowerCount)
{
    int removedFlowers[26] = {0};

    for (int k = 0; k < fence.sizeY; k++) {
        removedFlowers[field[fence.y + k][fence.x]] += 1;
    }
    
    for (int k = 0; k < 26; k++) {
        if (containedNumbers[k] && flowerCount[k] - removedFlowers[k] <= 0) {
            return false;
        }
    }
        
    for (int i = 0; i < 26; i++) {
        if (containedNumbers[i]) {
            flowerCount[i] -= removedFlowers[i];
        }
    }
    return true;
}

bool closeRightEdge(Fence fence, array<int, 26>& flowerCount)
{
    int removedFlowers[26] = {0};

    for (int k = 0; k < fence.sizeY; k++) {
        removedFlowers[field[fence.y + k][fence.x + fence.sizeX - 1]] += 1;
    }
    
    for (int k = 0; k < 26; k++) {
        if (containedNumbers[k] && flowerCount[k] - removedFlowers[k] <= 0) {
            return false;
        }
    }

    for (int i = 0; i < 26; i++) {
        if (containedNumbers[i]) {
            flowerCount[i] -= removedFlowers[i];
        }
    }
    return true;
}
bool closeTopEdge(Fence fence, array<int, 26>& flowerCount)
{
    int removedFlowers[26] = {0};

    for (int k = 0; k < fence.sizeX; k++) {
        removedFlowers[field[fence.y][fence.x + k]] += 1;
    }
    
    for (int k = 0; k < 26; k++) {
        if (containedNumbers[k] && flowerCount[k] - removedFlowers[k] <= 0) {
            return false;
        }
    }
    
    for (int i = 0; i < 26; i++) {
        if (containedNumbers[i]) {
            flowerCount[i] -= removedFlowers[i];
        }
    }
    return true;
}

bool closeBottomEdge(Fence fence, array<int, 26>& flowerCount)
{
    int removedFlowers[26] = {0};
    
    int y = fence.y + fence.sizeY - 1;
    
    for (int k = 0; k < fence.sizeX; k++) {
        removedFlowers[field[y][fence.x + k]] += 1;
    }
    
    for (int k = 0; k < 26; k++) {
        if (containedNumbers[k] && flowerCount[k] - removedFlowers[k] <= 0) {
            return false;
        }
    }
    
    for (int i = 0; i < 26; i++) {
        if (containedNumbers[i]) {
            flowerCount[i] -= removedFlowers[i];
        }
    }
    return true;
}

Fence findElementaryFence(Fence fence, array<int, 26>& flowerCount)
{
    //cout << "finding elem fence\n";
    bool closeUp = true, closeDown = true, closeRight = true, closeLeft = true;

    while (closeUp || closeDown || closeRight || closeLeft) {
        if (closeUp) {
            closeUp = closeTopEdge(fence, flowerCount);
            if (closeUp) {
                fence.y++;
                fence.sizeY--;
            }
        }
        if (closeDown) {
            closeDown = closeBottomEdge(fence, flowerCount);
            if (closeDown) {
                fence.sizeY--;
            }
        }
        if (closeRight) {
            closeRight = closeRightEdge(fence, flowerCount);
            if (closeRight) {
                fence.sizeX--;
            }
        }
        if (closeLeft) {
            closeLeft = closeLeftEdge(fence, flowerCount);
            if (closeLeft) {
                fence.x++;
                fence.sizeX--;
            }
        }
        //cout << "  "; printFence(fence);
    }

    return fence;
}

ll eFenceCombinations(Fence eFence, Fence fence)
{
    ll ans = eFence.x - fence.x + 1LL;
    ans *= eFence.y - fence.y + 1LL;
    ans *= fence.x + fence.sizeX - (eFence.x + eFence.sizeX) + 1LL;
    ans *= fence.y + fence.sizeY - (eFence.y + eFence.sizeY) + 1LL;
    return ans;
}

ll combinedEFenceArea(vector<Fence>& eFences)
{
    uint16_t u = 600, d = 0, l = 600, r = 0;

    for (int i = 0; i < eFences.size(); i++) {
        Fence fence = eFences[i];
        u = min(u, fence.y);
        d = max(d, (uint16_t)(fence.y + fence.sizeY - (uint16_t)1));
        l = min(l, fence.x);
        r = max(r, (uint16_t)(fence.x + fence.sizeX - (uint16_t)1));
    }
    ll area = l + 1LL;
    area *= n - r;
    area *= u + 1LL;
    area *= n - d;
    return area;
}

void getFlowerCount(Fence fence, array<int, 26>& flowerCount)
{
    //printFence(fence);
    for (int y = 0; y < fence.sizeY; y++) {
        for (int x = 0; x < fence.sizeX; x++) {
            flowerCount[field[fence.y + y][fence.x + x]] += 1;
        }
    }
}

void splitFenceAreas(Fence fence, Fence elementaryFence, vector<Fence>& outFencePos, vector<Fence>& outFenceNeg)
{
    uint16_t r = elementaryFence.x + elementaryFence.sizeX - 1;
    uint16_t l = elementaryFence.x;
    uint16_t d = elementaryFence.y + elementaryFence.sizeY - 1;
    uint16_t u = elementaryFence.y;

    bool spaceOnR = fence.x + fence.sizeX - 1 != l;
    bool spaceOnL = fence.x != r;
    bool spaceOnD = fence.y + fence.sizeY - 1 != u;
    bool spaceOnU = fence.y != d;

    if (spaceOnL) {
        Fence fenceAdd = {fence.x, fence.y, r - fence.x, fence.sizeY};
        outFencePos.push_back(fenceAdd);
    }
    if (spaceOnU) {
        Fence fenceAdd = {fence.x, fence.y, fence.sizeX, d - fence.y};
        outFencePos.push_back(fenceAdd);
    }
    if (spaceOnR) {
        Fence fenceAdd = {elementaryFence.x + 1, fence.y, fence.x + fence.sizeX - l - 1, fence.sizeY};
        outFencePos.push_back(fenceAdd);
    }
    if (spaceOnD) {
        Fence fenceAdd = {fence.x, elementaryFence.y + 1, fence.sizeX, fence.y + fence.sizeY - u - 1};
        outFencePos.push_back(fenceAdd);
    }

    if (spaceOnL && spaceOnU) {
        Fence fenceAdd = {fence.x, fence.y, r - fence.x, d - fence.y};
        outFenceNeg.push_back(fenceAdd);
    }
    if (spaceOnU && spaceOnR) {
        Fence fenceAdd = {elementaryFence.x + 1, fence.y, fence.x + fence.sizeX - l - 1, d - fence.y};
        outFenceNeg.push_back(fenceAdd);
    }
    if (spaceOnR && spaceOnD) {
        Fence fenceAdd = {elementaryFence.x + 1, elementaryFence.y + 1, fence.x + fence.sizeX - l - 1, fence.y + fence.sizeY - u - 1};
        outFenceNeg.push_back(fenceAdd);
    }
    if (spaceOnD && spaceOnL) {
        Fence fenceAdd = {fence.x, elementaryFence.y + 1, r - fence.x, fence.y + fence.sizeY - u - 1};
        outFenceNeg.push_back(fenceAdd);
    }

    /*cout << "pos fences:\n";
    for (Fence print : outFencePos)  {
        printFence(print);
    } 
    cout << "neg fences:\n";
    for (Fence print : outFenceNeg)  {
        printFence(print);
    }*/
}

void splitFence(Fence fence, Fence elementaryFence, vector<Fence>& outFence)
{
    uint16_t r = elementaryFence.x + elementaryFence.sizeX - 1;
    uint16_t l = elementaryFence.x;
    uint16_t d = elementaryFence.y + elementaryFence.sizeY - 1;
    uint16_t u = elementaryFence.y;

    if (fence.x != r) {
        Fence fenceAdd = {fence.x, fence.y, r - fence.x, fence.sizeY};
        outFence.push_back(fenceAdd);
    }
    if (fence.y != d) {
        Fence fenceAdd = {fence.x, fence.y, fence.sizeX, d - fence.y};
        outFence.push_back(fenceAdd);
    }
    if (fence.x + fence.sizeX - 1 != l) {
        Fence fenceAdd = {elementaryFence.x + 1, fence.y, fence.x + fence.sizeX - l - 1, fence.sizeY};
        outFence.push_back(fenceAdd);
    }
    if (fence.y + fence.sizeY - 1 != u) {
        Fence fenceAdd = {fence.x, elementaryFence.y + 1, fence.sizeX, fence.y + fence.sizeY - u - 1};
        outFence.push_back(fenceAdd);
    }
}

ll recursiveSplit(Fence fence, array<int, 26>& flowerCount)
{
    //printFence(fence);
    //cout << "split with "; printFence(fence);
    Fence eFence = findElementaryFence(fence, flowerCount);
    ll combinations = eFenceCombinations(eFence, fence);
    //cout << "combinations = " << combinations << "\n";

    vector<Fence> splitFencesPos;
    vector<Fence> splitFencesNeg;
    splitFenceAreas(fence, eFence, splitFencesPos, splitFencesNeg);

    //cout << "split fences = " << splitFencesPos.size() << "\n";

    for (int i = 0; i < splitFencesPos.size(); i++) {
        array<int, 26> splitFlowerCount = {0};
        getFlowerCount(splitFencesPos[i], splitFlowerCount);

        bool isValid = true;
        for (int k = 0; k < 26; k++) {
            if (containedNumbers[k] && splitFlowerCount[k] <= 0) {
                isValid = false;
                break;
            }
        }
        if (isValid) {
            combinations += recursiveSplit(splitFencesPos[i], splitFlowerCount);
        }
    }
    for (int i = 0; i < splitFencesNeg.size(); i++) {
        array<int, 26> splitFlowerCount = {0};
        getFlowerCount(splitFencesNeg[i], splitFlowerCount);

        bool isValid = true;
        for (int k = 0; k < 26; k++) {
            if (containedNumbers[k] && splitFlowerCount[k] <= 0) {
                isValid = false;
                break;
            }
        }
        if (isValid) {
            combinations -= recursiveSplit(splitFencesNeg[i], splitFlowerCount);
        }
    }
    return combinations;
}

/*ll areaRecursive(int calls, int startIndex, vector<Fence>& fences)
{
    ll area = 0;
    if (calls == 0) {
        area += combinedEFenceArea(fences);
    }

    for (int i = startIndex; i < eFencesFinal.size(); i++) {
        //cout << "recursiveLoop\n";
        fences.push_back(eFencesFinal[i]);
        area += areaRecursive(calls - 1, i + 1, fences);
        fences.pop_back();
    }

    return area;
}*/

/*void calculateCombinations()
{
    for (ll fenceBytes : elementaryFences) {
        Fence fence;
        fence.bytes = fenceBytes;
        eFencesFinal.push_back(fence);
    }

    ll area = 0;
    for (int i = 0; i < eFencesFinal.size(); i++) {
        //cout << "startLoop\n";
        vector<Fence> fences;
        ll areaLoop = areaRecursive(i + 1, 0, fences);
        if (i & 1) {
            area -= areaLoop;
        }
        else {
            area += areaLoop;
        }
    }
    cout << area;
}*/

void bruteForce()
{
    ll ans = 0;

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            for (int z = 1; z < n - x + 1; z++) {
                for (int w = 1; w < n - y + 1; w++) {
                    Fence fence = {x, y, z, w};
                    
                    array<int, 26> flowerCount = {0};
                    getFlowerCount(fence, flowerCount);
                    bool hasAll = true;
                    for (int i = 0; i < 26; i++) {
                        if (containedNumbers[i] && flowerCount[i] <= 0) {
                            hasAll = false;
                            break;
                        }
                    }
                    if (hasAll) {
                        ans += 1;
                    }
                }
            }
        }
    }
    cout << ans;
}

int main()
{
    //vector<string> testField = {"AAAAA", "AAAAA", "AABAA", "AAACA", "AAADA"};
    //vector<string> testField = {"BAA", "AAB", "AAA"};
    //vector<string> testField = {"Z"};
    //vector<string> testField = {"AZ", "ZA"};
    //vector<string> testField = {"AAAK", "ABAA", "ABAA", "AAAA"};
    //vector<string> testField = {"AAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAA"};
    //vector<string> testField = {"ZAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAK"};
    //n = testField.size();
    cin >> n;

    field = vector<vector<char>>(n, vector<char>(n));

    for (int i = 0; i < n; i++) {
        string row = "";
        cin >> row;
        //string row = testField[i];

        for (int k = 0; k < n; k++) {
            char value = row[k] - 'A';
            field[i][k] = value;
            containedNumbers[value] = true;
        }
    }

    array<int, 26> flowerCount = {0};
    for (vector<char> fieldRow : field) {
        for (char character : fieldRow) {
            flowerCount[character]++;
            //cout << (int)character;
        }
        //cout << "\n";
    }

    /*for (int i = 0; i < 26; i++) {
        cout << (int)containedNumbers[i];
    }*/

    //Fence startFence = {0, 0, (uint16_t)n, (uint16_t)n};
    //ll combinations = recursiveSplit(startFence, flowerCount);
    //cout << combinations;
    bruteForce();

    /*cout << "efences:\n";
    for (ll fenceBytes : elementaryFences) {
        Fence eFence;
        eFence.bytes = fenceBytes;
        printFence(eFence);
    }

    calculateCombinations();*/
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...
view save

correct output
2035
view save

user output
2035
view save

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...
view save

correct output
9
view save

user output
9
view save

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...
view save

correct output
3025
view save

user output
3025
view save

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...
view save

correct output
12
view save

user output
12
view save

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
1
X
view save

correct output
1
view save

user output
1
view save

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...
view save

correct output
38724
view save

user output
38724
view save

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...
view save

correct output
8334
view save

user output
8334
view save

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...
view save

correct output
44100
view save

user output
44100
view save

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...
view save

correct output
18
view save

user output
18
view save

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...
view save

correct output
1584665
view save

user output
1584665
view save

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...
view save

correct output
1077746
view save

user output
1077746
view save

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
view save

correct output
1625625
view save

user output
(empty)

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...
view save

correct output
1680
view save

user output
(empty)

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...
view save

correct output
25325366
view save

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...
view save

correct output
22342463
view save

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...
view save

correct output
25502500
view save

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...
view save

correct output
25650
view save

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...
view save

correct output
403292767
view save

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...
view save

correct output
388111321
view save

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
view save

correct output
404010000
view save

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...
view save

correct output
14159445
view save

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...
view save

correct output
15683003812
view save

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...
view save

correct output
15575906951
view save

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
view save

correct output
15687562500
view save

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
view save

correct output
3058970930
view save

user output
(empty)

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (Pikaksi)

2024-11-10 13:43:51 02024-11-10 13:23:06 582024-11-10 13:20:57 582024-11-10 13:17:30 02024-11-10 13:16:20 02024-11-10 13:05:48 02024-11-09 19:45:59 582024-11-09 18:12:38 02024-11-09 18:09:44 02024-11-09 16:35:19 02024-11-06 20:39:20 02024-11-06 18:54:32 582024-11-06 18:43:12 102024-11-06 18:28:05 02024-11-04 00:18:33 02024-11-03 18:35:54 102024-11-03 16:54:54 102024-11-03 16:53:16 02024-11-03 16:37:43 02024-11-03 15:13:08 02024-11-03 12:10:17 0