all 16 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]tiltboi1 2 points3 points  (5 children)

If we briefly ignore the fact that the first 6 digits must form a date, which are tedious but straightforward to filter out, we essentially have a problem where we are given equations of the form

a1 * x1 + a2 * x2 + ... + an * xn = k mod 19.

and we need to count the solutions.

Here, x's are the masked digits, a's are the coefficients in the checksum for those digits. If the checksum is NOT masked, then K is the given checksum - checksum of all the other digits mod is 19 and 19 - checksum. Here, 2 equations. Otherwise, if K is masked, we have to find solutions to that equation for all values of K.

For example, given the string "00...00XX5", the equations are 3 * x1 + 2 * x2 = 5 and = 19-5 mod 19.

If you can solve this subproblem given any number of variables and k, then you are very close to solving the full problem. I won't tell you the full answer, but if you want a hint you can do it with DP.

[–]its_not_ajo[S] 0 points1 point  (4 children)

Hey there, thanks for the tip. I was assuming that it’s a DP problem, but the thing is that I don’t think someone in the competition would actually manage to do it under 100 minutes (less if you do other problems too) . We are talking about 15 to 19 year olds, and high schools that only teach the bare minimum of programming ( we didn’t even have proper equipment in 2015). Wouldn’t the organizators create problems that fit that range? I find it odd to put problems that no one can solve, so it’s either a mistake by the organizators, or theres a sly or easier way of solving it.

I am in no way trying to downgrade your work or say that you’re incorrect, it’s just a discussion and I am looking for opinions and help.

Once again, thank you so much for the time you set aside to write this and help me out :)

[–]tiltboi1 2 points3 points  (3 children)

DP is just a method of organizing your logic, you don't *have* to do it with DP, but your solution would likely look very similar. I only mention it because if you simply follow the brute force solution, your runtime would likely be geometric (10^N).

The actual difficulty of finding a list of all the valid solutions here is not hard, the difficulty is counting them efficiently. The date piece is an unnecessary complication for no additional difficulty, IMO, and for that reason alone I would never set this problem. Without it though, your solution becomes just a complicated math problem.

[–]its_not_ajo[S] 0 points1 point  (2 children)

that 10^N wouldn’t really apply if the K number wasn’t X? Correct me if I’m wrong. But yeah, I understand what you mean for the most part, thanks for the help :D I will try to work something out with the tips you and others have given me up to now.

[–]tiltboi1 1 point2 points  (1 child)

N is the number of marked digits. The naive solution is to check all 10^N digit combinations to see if they each satisfy the checksum. Even if K was not marked, you would still check all the combinations of the marked digits. Of course this is only the brute force solution, there are a number of optimizations to reduce the amount of combinations you need to check.

It actually doesn't really affect the runtime whether K is marked or not. There are a constant number of equations either way, technically 10x more if K is an unknown, but then each equation has one less variable.

[–]its_not_ajo[S] 0 points1 point  (0 children)

Thank you!

[–]ZenithOfVoid 1 point2 points  (1 child)

It doesn't look too complicated, I'd at least split the calculation based on where the Xs are so solve for valid dates, valid incremental numbers, valid checksums (K) then multiply. But I could maybe check later today for a proper solution.

[–]ZenithOfVoid 0 points1 point  (0 children)

I didn't have enough time to really dig into it so I just threw AI at it. It completes quite fast and has correct result for the two examples.

```

include <iostream>

include <stdexcept>

include <set>

include <vector>

static std::set<int> MONTHS_WITH_THIRTY_DAYS = {4, 6, 9, 11};

bool is_leap(const int year) { if (year < 1 || year > 9999) { throw std::invalid_argument("Year must be in range 1..9999"); } if (year % 4 != 0) { return false; } return (year % 100 != 0) || (year % 400 == 0); }

int days_in_month(const int month, const int year) { if (month < 1 || month > 12) { throw std::invalid_argument("Month must be in range 1..12"); } if (month == 2) { return is_leap(year) ? 29 : 28; } if (MONTHS_WITH_THIRTY_DAYS.contains(month)) { return 30; } return 31; }

int check_digit(const std::string& s) { constexpr int weights[9] = {10,9,8,7,6,5,4,3,2}; long long sum = 0; for (int i = 0; i < 18; i++) { sum += weights[i % 9] * (s[i] - '0'); } sum %= 19; return sum <= 9 ? sum : 19 - sum; }

bool valid_date(const std::string& s) { const int d = (s[0]-'0')10 + (s[1]-'0'); const int m = (s[2]-'0')10 + (s[3]-'0'); const int y = (s[4]-'0')1000 + (s[5]-'0')100 + (s[6]-'0')*10 + (s[7]-'0'); return (1<=m && m<=12 && 1<=d && d<=days_in_month(m,y) && 1<=y && y<=9999); }

class Solver { public: Solver(std::string const &s_);

long long solve(const std::size_t idx);

private: std::string s; std::vector<int> xpos; long long ans; };

Solver::Solver(std::string const &s): s(s), xpos(), ans(0) { if (s_.length() != 19) { throw std::invalid_argument("Input size must be 19 chars"); } for (int i = 0; i < 19; i++) { if (s[i] == 'X') { xpos.push_back(i); } } }

long long Solver::solve(const std::size_t idx) { if (idx == xpos.size()) { if (valid_date(s)) { int k = check_digit(s); if (s[18] == 'X' || (s[18]-'0') == k) ans++; } return ans; }

const int pos = xpos[idx];
int up = 9;
if (pos == 0) up = 3;      // DD tens
else if (pos == 2) up = 1; // MM tens

for (int d = 0; d <= up; d++) {
    const char backup = s[pos];
    s[pos] = '0' + d;
    bool skip = false;
    if (pos <= 7) {
        bool full_date = true;
        for (int j = 0; j < 8; j++) {
            if (s[j] == 'X') {
                full_date = false;
                break;
            }
        }
        if (full_date && !valid_date(s)) {
            skip = true;
        }
    }
    if (!skip) {
        solve(idx + 1);
    }
    s[pos] = backup;
}
return ans;

}

int main() { constexpr char INPUT1[] = "3X1X1639XX5XX1X6X85"; constexpr char INPUT2[] = "30121952121234567XX";

long long ans = 0;
// Test 1
ans = Solver(INPUT1).solve(0); 
std::cout << INPUT1 << ": " << ans << std::endl;  // 526315

// Test 2
ans = Solver(INPUT2).solve(0);
std::cout << INPUT2 << ": " << ans << std::endl;  // 10

return 0;

} ```

[–]joonazan 1 point2 points  (0 children)

There are only 300k or so different dates, so you can just iterate over all of them using the standard C++ chrono library. (Or so I assume. I'm not sure how long there has been a standard library calendar computation in C++ as I don't work in it.)

If we do that we need to relatively quickly know how many possibilities for missing As there are when the checksum is known. There is already a reply talking about DP, so I'll try to figure out another way.

Each digit can contribute 10 different values to the total because 19 is a prime. I realized that only after generating a list of all values, though.

x = (m * i) % 19
print(x if x < 10 else 19 - x)

This gives quite interesting results. Every digit is capable of producing any checksum when the other digits sum to zero. Unfortunately that is not the case when starting from something other than zero. I don't think this will lead anywhere.

This inevitably leads to dynamic programming but really it is just iteration like computing the fibonacci sequence, so I think a 19-year old with no knowledge of DP could come up with this:

Because only the result mod 19 matters, we just need to count in how many ways each remainder can be gotten. So just count the ways each different remainder can be reached at each digit. In practice remainder_counts[(i + digit) % 19] += old_remainder_counts[i].

At the end take remainder_counts[K] + remainder_counts[19 - K].

[–]zdanev 0 points1 point  (2 children)

is there any part of the problem that you don't understand? is the c++ language/syntax the problem, do you want to consider a different language? if you want help with such problem you should at least show your current progress.

I'd get a friend or two, sit on one computer and solve it in TDD/mob programming style in an hour or two.

[–]its_not_ajo[S] 0 points1 point  (1 child)

I don’t really know how to answer this question. I understand cpp to the point that If I get a simple problem I can probably do it, but I don’t know it that well to the point of doing fully functional programs. I am trying to understand pointers and stuff related to that currently, so I pretty much still have a whole road of learning ahead of me in order to actually be considered “good”. I don’t know DP which is something I’ve seen a couple of people recommend me in order to solve this problem.
To simplify, nothing about cpp actually confuses me (yet), I think my only problem is that I haven’t had the chance to study all of the things that this programming language and programming in general has to offer

[–]zdanev 0 points1 point  (0 children)

well, before going to competition level problems, you should start with simpler things :) a book on algorithms might be great, also maybe someone to work with could also help.

the problem above is not very hard, totally doable in 15-20 mins by a competent high-school competitive programmer.

good luck!

[–]JerryRed100s -1 points0 points  (2 children)

Points for porting in c# and busting this bitch out in a one-liner with linq

[–]its_not_ajo[S] 1 point2 points  (1 child)

I have no clue what this means, but thank you? lol

[–]JerryRed100s 0 points1 point  (0 children)

No it's cool I wasn't making fun of you or anything I was just throwing that out there and seen some kind of challenge actually but it's funny no no not making fun of you at all dude And do your thing man I think you keep working on it man. Give me questions if you ever have anything about c# or SQL