Nintendo Challenge

Puzzles
#107

I’ve spent a few months on this problem (on and off again), and I haven’t been able to come up with a solution that’s much better than brute force. So I want to walk through my logic a bit (if that’s allowed, I’m not sure). The encryption is interesting. Obviously it helps to simplify the encryption code a bit.

And once you do, you find certain patterns. You’re comparing two 32 bit numbers, and at some point you’re comparing each bit in one number with each bit in another number. To find the value in the encrypted bit, you take the sum of the comparisons (for the last bit in your encrypted solution, you’d see if the last bit of both numbers is 1, and if they are, than the encrypted solution is 1, for example). In the second to last bit, you compare the last bit of one to the second to last bit of the other to either get 1 or 0. In the third to last bit, you compare the third to last bit with 0, then the second to last bit with the other second to last bit, and the sum is either a 1 or a 0. And so on and so forth.

And then in the middle of our four byte numbers (the 16th bit or so), you have these massive combinations of bit comparisons. But after awhile, we stop getting useful information from our encrypted numbers. We just say that bit[16] = sum of a bunch of comparisons, the outcomes of which are unknown. So my solution was to… make systematic guesses as to their outcomes? Until I came up with something that encodes to the original? This doesn’t have performance much better than brute force.

I don’t even know what to google. Is this even the right track? Others in the forum have said they used google for an algorithm, that once they understood the “mathematical name” of the problem, it was easy to find. But I’m not even sure what to google. “Broken encryption algorithm?” “Fancy math?”

#109

I am in a similar situation.
I understood all the operations of the encryption.
But I don’t have the required background to guess the “mathematical name”.

I thought of a solution, it’s not brute-force, but it would be quite heavy compared to what I can read here (a few ms !), and I don’t have time now to work on it.

#110

This is certainly the least interesting puzzle I ever had to solve. I spent quite some time on it (a few months, on and off), but I didn’t want to cheat and I decided NOT to look on internet for a solution and to try to solve it by myself. At some point I decided I had spent enough time on this, looked on internet, and found the solution in a few minutes. I was so disgusted that I decided not to submit a solution on Codingame.
Basically, if you happen to have come across the algorithm to solve that problem in your studies or somewhere else, it’s trivial to solve; if you did not, it’s impossible to recreate that algorithm by yourself.
And the problem statement is wrong: it states that “if there are several possible decoded values, you should display all the possibilities in alphabetical order”, but this is not what the algorithm Nintendo had in mind when creating the problem does.

#111

The testcases names do not correspond to real data size right ?
I don’t see how 46508fb76677e2 can fit in 32 bits

#112

The wording in the pseudocode is a bit confusing (until you understand the magic Centaurian operation), but the test case name corresponds strictly to the size=S parameter.

A size parameter of 32 does correspond to the pseudocode reading 2 (=32/16) integers into array a, and in this problems for all intents and purposes integers are 32 bits, so it shouldn’t be (too) surprising that a size parameter of 32 corresponds to an input width of 64 bits.

#113

I just finished my nintendo challenge but i still have an error. Why some solution has a four lines solution with a factorization with 1 and some other not ?

#114

I finished this problem. Used wrong mathematic name (found no useful things) until i realized the it can be expressed in other concepts but same problem…

#115

Any hints anybody as to how to solve this?

#116

This thread is just full of them.

Some of them downright past borderline spoilers.

#117

Do you need a moderator to edit them? :wink:

#118

The hardest math problem, that I have ever solved :slight_smile:

1 Like
#119

Hi everybody,

For a long time I wanted to solve the Nintendo challenge, and it is almost done !

It took me some time to understand what the problem was, I have tried many modelisations before I found one that could be solved with a polynomial algorithm. I hope the moderation will not blame me for telling everybody that effective means in P.

Understanding the pages of TAOCP explaining how to solve it took me a lot of time. It was hard, but very interesting, and I learned of lot of things.

Once you have understood the algorithm, you have to code the algorithm. And the problem with a lot technical books and publications is that the algorithms are not exposed clearly enough to be coded by someone who does not understand how they work. I had to go deeper in the mathematics involved before I could go back to my keyboard, but I don’t regret it.

I have always avoided C++ because I found it overcomplicated. So I had to make peace with this ennemy. And even if I still think C++ is a very hard language (but don’t be fooled, I love C !), I have to admit I spent a good moment learning it.

When I saw (offline of course) that (after a lot of debugging) it could solve all the test cases, it made me shed a tear :slight_smile: I had to remove all the STL collections and recode almost everything to make the algorithm run fast enough. After a modification I am certainly not allowed to share, the NERD test case went from 20 sec to 0.433 sec, seeing this case turning green made me live a great moment of joy :smiley:

But everything went wrong when I submitted my code. For a reason I am unable to understand, the validator 2 fails.

Am I the only one ?

I cannot tell more without spoiling the puzzle, but maybe the validator 2 is an edge case of the algorithm I have used, whereas test case 2 is not.

I know designing the cases can be hard, making tests that match validators can be a pain in the neck, especially if different algorithms can be used (several are exposed in TAOCP).

Of course I could recode everything with another algorithm, but since I do not know what went wrong, how can I be sure it will do better ?

The failure of a validator is impossible to debug, I have to tell you it is very frustrating…

Can someone help me ? Has someone met this problem ?

Thanks for reading, I wish you a lot of fun on CG !

2 Likes
#120

In such cases I try different approaches for the task. Sometimes different algorithms. Also try to debug with “cerr” if everything runs on the platform as expected, maybe print the name of each function when it is called. Once I fought a bug for 3 days and at the end it appeared an uninitialized float, on my machine it was always 0.f but in CodinGame sometimes it wasn’t. Try to check if some variable overflow occurs. Also make sure you got right when you have to output 2 line and when 4 lines.

#121

Thanks @Di_Masta for your answer. I have taken a look at the CG execution trace, and it seems to be the same that what I see at home.

Only the timer is different, CG execution is a little bit slower, but the since tne NERD test case works in less than 1 sec on CG servers, a time out on a 32 bits validator does not seem likely.

Following your piece of advice helped me to make sure there was no difference during the execution at home and on CG. And I have to admit you were right, it was an algorithmic issue.

Since I had 100% on the test cases and only one validator failure (a 32 bits one), it was almost impossible to debug.

After hours of trial and mistakes, I finally found what the error was. It is a tricky edge case, and building a test that could reproduce the error would require some maths and some simulations. Maybe the designer of this problem had not seen it.

If someone meets the same problem, I can dedicate some time building him a additionnal test case. If the coding game staff wants me to help designing a better test case 2, I am of course ready to help.

Thank you and have fun on CG !

2 Likes
#122

Hi, just completed 100% of this challenge.

Several years ago I spent months on that problem, only getting the first 2 cases with my quasi-brute-force method. Of course it timeout-ed all >32bit cases. I also tried to implement a pseudo-symbolic method, that also failed on big sizes.

This year I re-attacked the problem, this time (maybe being older my patience is decreasing :smile: ) after a week of tries, fruitless, I started looking on this forum, where I found references to finite fields, GF(2), etc.
So I started to study, and, I must say, it was a very wonderful discover of an entire world.
Among other interesting things, (I recommend this course http://www-users.math.umn.edu/~garrett/coding/ ), I managed to found a chapter concerning the factorization of polynomials in the book “The Art of Computer Programming”, where is described the XXXXXXX algorithm. This is an algorithm that solved in 1967 a problem risen from Galois in 1830 (around 150 years of investigations). After a couple of days of work I managed to implement the solution (without copy anything, but following the algorithm).
Now, given my eternal gratitude for all the new knowledge that this problem gave to me, the question is:
anyone in the staff really imagined someone could solve this problem by himself?
It would be the same thing to assume one can solve the factorization of big integers by inventing the elliptic curve method…
Please I need to know if someone was honestly able to solve this puzzle without implementing that algorithm.
Conclusion: to avoid people going mad, when a puzzle cannot be solved without some prerequisite, please say it!. It is anyway a big challenge to study, implement, optimize, but don’t let people being frustrated for years (in my case).

EDIT: removed the name of the algorithm used for no spoiler

2 Likes
#123

I was honestly able to solve it using another algorithm. Does that count?

IMHO understanding what the problem is about is the actual challenge, more than just implementing it. So naming one is quite the spoiler.

#124

Yes, there are few others, but my point is: you cannot “invent” the algorithm for solve that problem, do you agree?

1 Like
#125

I agree that I wouldn’t have.
I disagree that’s a problem, and would certainly not have liked it if the statement told me which direction to look into from the start.

1 Like
#126

I agree with you, I wouldn’t have be told in which direction to look, since, as you said, the fun is first to understand which it is all about, and stuff (otherwise we will be not spending our free time on this nice site).
I would just liked a statement: “feel free to consult your math books”, since I struggled literally for months (years ago) forcing myself to not look anywhere, saying “I must find a way on my own”, and finally gave up frustrated (maybe it is my problem to be so integralist).
When now I found that it was completely impossibile to solve by myself, so I wasted so much time that I could have use to study that beautiful world of finite fields, as I did now, so…
ok, you convinced me that was my mistake… :smiley:

#127

Understanding the problem is a part of the puzzle. The first time I tried, I spent a lot of time reverse engineering the given programm, and trying to find an effective modelisation. And I have given up…

Several months later I tried again, and I enjoyed this great sensation when I found it by myself !

Of course, finding an effective algorithm without TAOCP is nearly impossible, unless you are specialized in this field (remember, 150 years of investigations !). But identifying the problem, understanding the algorithm, and coding it efficiently is challenging enough.

As @geppoz said in the above message, we need TAOCP to solve this pb. But @Plopx (and others) already wrote it in this thread a long time ago, and everybody here has taken care not to spoil he puzzle…

That’s why I think @geppoz gives way too many details in his message… Removing the name of the algorithm is not enough for me since the problem is explicitly named.

@geppoz I think you should remove all reference to the field that enables a efficient modelisation of this puzzle, do you agree ?

1 Like