Obviously, size has to be a multiple of 16.
ah. is that stated somewhere? must have missed it. actually, the constraints say 0 < s <= 256 so, now i’m at a loss?
well, the code reminds me of an interview question where parts are incorrect or left out on purpose to entice you to ask questions, no constraint checks, problems with trivial corner cases, faulty constraints, and ambiguous instructions. I’m of course assuming that the author of the problem didn’t just sloppily throw something together, but put some thought behind it.
Well, sort of. It’s in the names of the tests:
32 bit
32 bit
32 bit
64 bit
128 bit
256 bit
If you attempt to submit anything, then you will see that the validators have the exact same names. Those are the only cases that you need to solve for.
- danBhentschel
Well, sort of. It’s in the names of the tests:
I did notice them, but since the constraints were much more flexible I assumed that the author wanted a general solution for all s, where 0 < s <= 256, but maybe that was errata’d somewhere?
In every puzzle, you only need to solve the tests given in order to complete that puzzle. As others have stated, I believe that Nintendo has intentionally obfuscated this puzzle because (my own interpretation here) they are not only looking for people who can write code, but also people who can infer intent from incomplete or obscure requirements. It’s certainly something that I look for in candidates when I am involved in hiring.
If you dig into the problem, you will quickly start to realize that it really only works properly for input of certain sizes.
- danBhentschel
It’s not stated anywhere indeed, but I believe you could infer it from the sample code, which would be invalid otherwise. So, assuming the sample is valid (because it’s part of the problem statement), this means that size has to be a multiple of 16.
One could argue that it’s also not stated anywhere that size / 16 should be an integer, so what does it mean to read “size / 16” values from stdin if size is not divisible by 16? Should we read partial values?
Sometimes information is missing or not explicitly stated, and you have to infer it a little bit.
sample code, which would be invalid otherwise
interesting. would it be fair to say that the problem is only valid at every s where s is divisible by 32 then, since the algorithm appears to have a different behavior on odd-numbered N1 word lengths?
It’s certainly something that I look for in candidates when I am involved in hiring.
be careful with candidates who solve problems by programming to the test cases though 
That might very well be possible.
Nintendo’s code is designed to work with multiple of 32 bits. With their formula, in case the size is not a multiple of 32, the the formula simplifies a lot and the solution is quite different. I imagine that if we want to generalize Nintendo’s fomula then it’s true that we should consider (j+size)%32.
Just spent two weeks on it. Stuck at ~2 HOURS for the smallest problem (not even brute force). Giving up. Congrats to the ones who understood this problem.
Ok, I finally was able to put the mathematical name on this problem. After some research, I found 2 well-known (apparently) algorithms to solve this. Unfortunately, university is so far away for me (16 years) that I can’t understand the mathematical notations any more. I don’t think I will be able to implement the algorithm. This is definitely a challenge for mathematicians ONLY.
I do agree that it’s quite mathematical. I wouldn’t say that it’s for mathematician only but clearly you need to have a good background.
It took me a few minutes to rewrite the algorithm so that it becomes very simple to understand. I thought that it would be not so difficult to solve but I was wrong: I spent more than a week-end to figure out what the formula means mathematically (but it would have taken me few minutes 20 years ago). Either you have good mathematical knowledges and it’s rather simple, or you don’t have the necessary background and you may be stuck for a long time, no matter how clever you are… And google does not help a lot at this stage. This is a bit frustrating to be blocked not because you are not good but because you don’t remind what this formula is.
Once you have understood which mathematical problem you have to solve then it’s not so difficult but you are far from having finished. But google is your friend : a lot of litterature exists on the web but articles are written by mathematicians so not so easy to read and understand for non-math guys. There are not many algorithms but many derivatives and it’s hard to translate the descriptions into efficient algorithms. I spent a few evenings trying to understand all the maths and trying to find ready-to-go implementations (there are some but not very friendly and not necessarily optimized for this particular case) and I wanted to do it myself thus I decided to try to write my own from scratch. I needed several attempts before I managed to implement the algorithms properly. I also discovered a very nice and powerful free cloud-based service (cloud Sage) which helped me a lot to check if my maths were correct.
I did everything in C, not real C++, and it took me ~1000 lines of code because I implemented everything on my own, trying to document things, not using the existing C++ classes, mostly for performance reasons and to track what was done at each step. By chance, I had very few bugs. If I had to redo it now that I understand it better, I would try directly in C++.
I did everything locally, outside of Codingame, using tests that I wrote myself (easy as we know the encoding formula) then putting the values from the Nintendo tests and comparing with the expected results. When I put everything under Codingame, I realized that i was expecting and writing the 32 bit integers in the wrong order. Easy to fix. I passed all tests and I submitted. Succeeded on the first submit. In total I probably spent nearly two weeks (a few hours every evening).
What I noticed is that when you take the encoded messages provided by Nintendo in the tests, you will obtain very few possibilities for the decoded messages (ie. the ones which correspond to the same encoded message). Same thing for the validators. This is a chance because some encoded messages correspond to many different decoded messages and you would spend a huge CPU time to evaluate and build the many possible combinations. I pass the 256 bit test in 12ms (on my PC using gcc with all possible optimizations on but keeping a single thread) but it may take much more time with some other messages, really a matter of chance that this one leads to only two possibilities (this is inline with the constraints on N2 given by Nintendo, meaning that they don’t choose the messages to encode randomly but select ones which are simple to decode).
Done ! At the end, I spent about one week implementing stuff in the wrong direction (working for 32 bits problems, but not more), then I understood what the problem actually is, spent 3 long days mostly trying to make any algorithm work on paper (this was the hardest part), and finally implemented it in half a day (relatively easy, ~300 LoC). Performance-wise, my result is quite bad (42ms), but I do some operations of the algorithm bit by bit (slow, shame on me), and some others int by int. That is an obvious direction for improvement. I’m still wondering why Nintendo put a 5s limit. Overall, this challenge was very frustrating as I struggled a lot to understand the maths behind it (and I still do not understand all of them). Mathematicians often use very frustrating terms like “therefore” or “obviously” between two steps of an algorithm, where I can’t see any link. So at the end, I had to read half of the internet to make all the partial info create a total image of what I had to do. The days I spent doing the maths were quite horrible, so don’t start this challenge if you don’t like that.
The puzzle description states:
Input
Line 1: size S
Line 2: N1 integers in hexadecimal format, separated by blank spaces
However, for test 3, I receive:
32
46508fb7
… and that’s it…so my test fails.
Now, if for this single test, I post an additional std::cin (I mean I explictely request to read 3 lines and not just 2 as stated in the puzzle description), then I receive:
32
46508fb7
6677e201
… and if I concatenate the 2 strings (ie “46508fb7 6677e201”) in order to comply with the puzzle specification, then my test pass…
Isn’t there something broken regarding how input data are provided ? I think that data, for this test, are not provided has they should…
As std::cin is blocking, it is not possible to have something working for tests that complies with the description (ie: where data is provided on 2 lines) and with a data set that provides integers on multiple lines…
You can set your IDE in expert mode (in the settings) and you’ll have a button to see the exact input and outpout for each test cases in the IDE.
The input for the third test case is this one:
32
46508fb7 6677e201
Their is no new line between the 2 numbers. I suppose your code for reading the inputs is wrong. This is how i read it:
int size;
cin >> size;
int inputs[size / 16];
for (int i = 0; i < size / 16; i++) {
cin >> hex >> inputs[i];
}Thanks a lot Magus. I have adopted your way to read data and it works fine. Thanks again !
I don’t understand the goal of the program.
Can someone explain it to me? Thank you!
I’ve downloaded the sample encoder, and I’m not getting the same output as what it’s saying. If I download the sample and put in “32 46508fb7 6677e201”, my output is “4eda41b7 18d70349”, not “b0c152f9 ebf2831f ebf2831f b0c152f9”. Is there a reason for this discrepancy? Could this vary by system?
That’s what your program should print when reversing the encryption.
Thus the given program should print 46508fb7 6677e201 for both b0c152f9 ebf2831f and ebf2831f b0c152f9 as input.
Ahh yes, that makes sense. Thanks!