Me neither, I used a very simple implementation of a trie.
Phew Finally Solved this !
Turns out my code was right but Visual Studio command buffer wasnāt supporting the huge input.It could only read 4096 chars in one line.WEIRD
I dont know why I had to use the TRIE data structure which confused the hell out of me.
Just using DP with standard matching turned out to be pretty fast.
I got confused by the problem statement that the maximum number of possibilities was 263ā¦ I thought I was doing a mistake calculating things by hand, until I decided to try to find out the real answer for test#4 by just guessing the digits. Then I realized that 2^63 was meant
But in the end a simple trie and a secondary array the size of L did the trick.
It would be nice to be able to compare the solution to other peopleās though. Is that possible?
0 ā¤ R < 263 is meant to be 0ā¤ R < 2^63. A very misleading typo.
I finally did this. LSLD was a big problem. Trie helped me to achieve 100%. Thanks to MaximeC for metioning it.
LSLD: 47ms in Java
Hi chrm!
Finally came to giving a try to āMyProgram.exe < TestCase.txtā.
Youāre absolutely right - having the same code for site and VS would be just awesome - I have to change it everytime I copy back and forth.
But I met some issues when I executed my example it reads first line as
Ńāā4 3
While it is just 4 3 when I read it with stream reader.
Solved it now by converting text file to ANSI from UTF-8.
There must be a way to make program read UTF-8, right?
I still cannot make VS to āeatā this parameter.
I set Start Options command line arguments to <1.txt
and when I run it with Debugger attached (F5) - it works fine.
But when I run it without Debugger (Ctrl-F5) - it waits for the input from the console.
I usually run applications without debugger when I donāt specifically need it.
So it is inconvenient for me.
Itās strange, but I with simple implementation trie even didnāt pass 7th test- āMany possibilities, with small sequence and small dictionaryā as well as 9th- LSLD. In my case only implementation trie with memorization was successful.(C++ 13ms)
Same here, my simple version of a trie was way off in terms of speed in the last test.
I restarted from scratch with memorization, no trie, and got it down rather easily.
It might sound stupid, but double check your Morse codes
I tried all the hints here, but still couldnāt pass LSLD (others were good) - Iāve missed one dash in āXā letterā¦
Hi Everyone,
I come to you beause I have a problem of time (like everyone) but I canāt find a another more fast that I do :
I use a binary tree with two sub-node (one for . and one for -).
On each node, I have the number of word possible with the translation in Morse from the root to this node.
Iām doing recursivity on it to find all the possibility.
Do you know how I can do faster ? Thanks
What is the last thing you do in your algorithm? Take the nodes from the last level and sum the numbers to get the result?
I go through my tree when I am on a node with possible word, I save this possibility and I start from the beginning of the tree. If I arrive on a node without result, then I cancel this possibility.
You didnāt answer my question. How do you compute the end result?
If you construct a tree containing all the possible messages, why do you need to save āthis possibilityā somewhere else?
Why do you keep starting at the root after you found something? Thatās what slows down your algorithm considerably.
oh
I save this possiblity because If there are two words for the same morce code, then it multiplies by two the following possibilities in the āsentenceā.
I restart from root because, it a new word (Root is the begining of all word in my tree)
Sounds like youāre close. The key for me was avoiding re-parsing sections Iād already done (when the chain diverges and then re-converges further on down). Switching to a breadth-first search instead of depth-first was part of that, as well as using a graph rather than a tree for the evaluation.
Really ?
That must be a matter of personal taste then i guessā¦
I have found this puzzle to be a lot more work than Mars lander 3 or Triangulation for instanceā¦
Had the same issue for quite a whileā¦
I guess I should have read the problem statement with more care -.-
It gave me a real -ā¦-ā¦-ā¦-ā¦
I really liked this problem, because the hard part wasnāt the implementation, but finding the right approach. The algorithm becomes very simple when you have the right idea.
I liked it too, it gave me a run for my āmoneyā.
I donāt undestand what do you mean with : āavoiding re-parsing sections Iād already doneā ?
I try a another way, I created a tree with children in the number of - or. which follows. It works but I have the same problem of time :-/