Hi vthai, The multiplication in quaternions are not commutative -- that is, there are some *a* and *b* for which *a* * *b* != *b* * *a*.
When you create all possible reduction for 'k', you must multiply it carefully (pay attention to the left and right operand). What's your output for this input: 1 2 2 ij The correct answer is YES Felix Halim On Mon, Apr 13, 2015 at 3:26 PM, vthai <[email protected]> wrote: > I might be illusion or paranoid but I think my solution is correct but > somehow google just mark it as wrong. > > As I understand the sub problem C - Dijkstra ask us to identify if for a > given string of combination i,j,k there exist any substring that can be > reduced to i , j, k in the exact order. > > So my solution is first to identify all the possible 'i' reduction and 'k' > reduction in the whole string at the same time(look for 'i' reduction from > left, 'k' from right and put into a hashmap) Next for each 'i' found, start > from the very next index and search for 'j' reduction, if one is found > check whether the next index for 'k' exist in the hashmap of found 'k' > reduction. > > But I get an incorrect answer whenever I submit, which I have go over many > times and still don't understand. > > I download the solution from the top scorer and sees the following > different in answers (attached). > > The difference is some of my answer indicates that there is a reduction > for i,j,k for the given string while the "correct" answer says "NO". (so it > is either I identify the wrong answer, or the solution misses some case) > > > I would like to show one example here: > > Case #14: > > this case should be a YES(I ran the correct solution and it gives a NO) as > I can tell(or maybe I am wrong?!?) > see the input below, it can be divided into the following portion > > from 0 --> 14 (reduce to i) > from 15 --> 18 (reduce to j) > from 19 --> end of string (reduce to k) > > the input is: > > 10000 1 > > ikkikiijkjjjikkjijkjkjjijkkkjjkijkkjjikjkjkkjjiijjjjijkikijjjijikjkikjjkjkjjkjjjiikkkjijjjjiiiikjikjikijiijjjiijjkkkjkjjkkkijijjiikkijikijjjjijkiijkjkikjjiiikijkijkikkkjjkkjkjikjjiikkjijjkikiikkjjjkjiikijjkjjiiikkikkkjikkjkkjkjkikikkjijjkjkjkkjjijiiikjjkijkkjkjjjikjkjjkkkikikkkkjiiijjjjijkkiijkjkiikkkkkkjkjikkijkijiijkkjjjikkiiijkijkiiiiijikikijjkjkkjijkjjjikkijkkkkjikjjkjijikjijikiikikkikjkikjikijijijjijjkiikkkjijkiiikikjjkjkijkjijkjkjjkkjkkkjjikkkikkkkijiikiikjkjjkkkijijiikjkikjikijkjjkkjjkikjikjkjiikjijijikkiiikiikijkkiijkjiiiikkikjiijjjiijjijjkijikkkijjkjikkkjiijkijkkjjiijiijkjijjjikkkiikiiikkjijiiijiiijijijiikijjiikjiijjkiijkkkkkkkjkkiikiijijijijkikiiiikikijjjkkkjjijiiikkijikjkkikjiijijiijjkkjkjjikjjkjkijikjjjjkkikkjjjjkjijiijjijjikijiikjkkjjjkiijijkikkijjikkkjkjjkkijkkjjjijjikkjjiikkjikkjikikjkikkkjjijikiikjjkikjjijikikiiikkjkjikkikjiikikiijijkkijiiiijijjikjjiiijkkkkkjkkkjiiijjikjjiikjiijjjkjjkijjkiiijijiijiikikjjjjkjkikiiijkkkjjkikjiikjjjiijjikjkijkkjkijkjjkkkkikijikiiiikikjjkkijiijjijjjiiijiiikjjjiiikjkkkjikjkjkjkkjkijkjjjkjiijjkikiikjkijkkjjkkjijjjkikjkikiikkikkjjkkkiijikiijijkkikkkkjkiijjkjijjijjiijkkjjikjjiikkjkijjikjjjjjjijjjiikikjjijkiikijijjjjkikijiikikjkikikjijikiiiikjiikijjkjkiikjjkijjjikkiikiikkjkjkjjjkkijkiikjkjkkkkijkkikkkikiikkkkkkkijkkkiikkikjijkkjikkjiijikjijjjijikkjkjjkjiiikkijkiijjkkkkjijkijjikkkjkkkkiijkkkijkjjiijjijjijkiiijiijkkiijiikkkijikikjkkjjijjijjjijjkjijkkjkikiijkkjiikjiikkjkiijkjijjikkikijjijijijjjkikjiiiikjkjikjjkiikiiijijikkikkijkiikiiiijkkkkkjikikiijijjiikjjijikkjikjkkikkikijjjjjjikikkjijkkkjkiijjiiijkjjiikjijjikiiikkjiijkikikikjijkjijkijiiikkjjkkijjiiikkjiijijikjijjikjjjikjkjjkkjiiikjjkkiijkkkjijiikkiikkikjkkjiijikjkkjjkkjjkjjkijjjkikjjiikjkijjikiiiiiiikijjkikkjjjijikjkjkjkkiikikijkkjjikkjkkjikijjkjijjkikjkjikikkjjiikkjkiiiiiiiiiiijjjkijjkikkkijjjiikkkiijjkijikkikkkikjikjiijjkjkjjkkkjijjjikikjkjkkkkkkjjiijikikikkkkkjijjkjkjjkjkkijkiiikiikjkiijkjikkiiijkijijjjkiikijkkjikjjkijikkkjjkijjkjjijkjkkjjkjjkkkjiiijiikkiiiikikkjkkikkkkijkijkjkjikjkkkikikjkjijkikjjkijkkjkikkikjjiijjikkjjjiikiiikiikkijjiijiijiikjjiikikjkkiikjkkjkjikikiijijkiiijjikjijijijkkjkkiikikjijikjkkikikkiikiiiikiiiiijjikjikjkiikkjjikkikikijikiikkjiikjkiijjjkijkkijjjjjkkkijkkkjkkkkiiijjijkikjikjkiikkkkkikkjkiijjkijikjkjkiikkkjikjjjkjjjjkjikkkiikiikjikkkjkkkjkkjiikjikkkiikiijjjikkijjjjkkikjjijjkjkijkiikjjiikkiikikiijijkkkjjiiikkjiiijjkikkikijjkikkiijkjkkjjjkjikiiiikiijiiiijjkiijikkiikjkiikjjkjjijkkijkkkkjkkijjjjjkikijkikikikjkjijjikkiiiiiiikjkjiikjkiikjikkjikjjkjjkjjijkiiikjijkkkikiikkkijjkjikjjjjikkkijikjijkkijiijikkikjkkiijikjjkjijkjiijkiiikjkjijkkijkkkjiiiijkjkijijjikjjjkkkkikjjijiijjikiijiijkkikiiiiijkjkikjkikkjijiikjkikikiikijikjjiikijkkkjkkkjiiijiiikjkjkikikkjiijkjikiijkiijkkkjkiijiiikkjikkjijjijiikiiiijijikiiijkjjkijjkikkjijkiikikkijjjikiiijkjiijkkkikkkkiijkikjjijijjikiikjikjijjijjijikkjkkkjijijjiijkjkkkijjkjikikjkiiijjjiikiijjjikikjiiikjijkjkkjkjijkiijijijkjkijikjkjikkjikkijjkkikikjkiijjikkjikiijikkiiijkijijkiiiikjiiikkjikiiikjkjjikjkkkkikjkjjjiiijjjkiiiikkjjjiikjkkjjjiijjjkjiijkjijjkijijjkiikjjkiikikikjjjikijjjkkjkjjjkjkkjiiijkijjjkikkkiiikjijikjkijijjjkkjikjjkjjkjkjikikijiijjikikiikikjijkjijkiikjjjjkijikjjjjjikkkkijijkijiiikikkjjijjjijjkjkkkkijjkjkijkjikkjjkikkjikkjjkikijjjijkjjkijikkiiijikikikkjjijkkkjjjikjjjikjjjjjiiijkikiikijkjiikkkjjikijiiijjkkjkkiikjjijjjjikjkjjkkjkiijikjkjjkjiijjjkjiikjjkjkikiijjjjijkiijikiijjkkkijjkijijjijkikiikkkkiiikkijjiiiiijikikjjkkjkkjkijjjjkikikjijkikikjjijkkkkjjjijkkkkikkkjjkjkiiikikjkjiijjkjijkijjkkikjkiikjijijiiikjijkkikijjjjjijkkkjjikjjjjkikjjjijjikkkkkjjjjkkikjiiiiiijkiijkijkjjjkjkikkkiiiiikkkjjjkkkkkkiiiijjjiijkjjikiikkikjkkjiikjjiijikkjikijkkkjijjiijkjkikiijkjjjkiijjkjkiijkkjkkjikjjjkkjiikiijikkkkkkjjjijjjkjikkkjikkiiiijijijkjkkjkiijkkjikkkkiiikjiikijikjjjjjkjijijkjkjkjjjjjjkjkjjkjjjijkkkikiiikjjjjikiijkkiikjkjikjkjjikkjikjjjikijjjiiikiijkkikiijijjkiikikikjjkjkkkijkjijjkkiiiiiiiikjikkikkjikkjjkijkkiiijjikiikkjkiikiiiijikijjjkjkiiiijikjkkijjikjkjjjjikijkkkkjikikijjiikijjjjiikjijikjjkkikkikijkijijjjkjkikjiijikkjjjiiikkjkjikikiijjjjiiijikjkijiiijjkkjjkjijjikkjkiiijikjijjjjiiiijkkjjkkjiijjkkjikjkikjjkiiiiijkikijiijiiijkikikijjkkiijijijiikijjjiikjikkkjkkjkijiikiijijiikkjijikikkjkkkkijkkijjjiijiijjjkijjkiijjkijijiiikkkjiiikiiikjkjkjiijkkkkiiiikijikjkijijjkijkkkkjkkikijiikkiijiiijiikijkikjkikikkkkjjkijijjikkijijiijkjikkjikjiikikkjkiijkkkkjijiikjkiikkijjjijkikjiikikiikiikjkjjkikkjjijiiijijijijiijjjiikikkkjkjjjkjkkkkkkkjijiijiijkijkjikikkkjjiikkkjiijikkjiikijkkkkiikkikikjjiikkikiijjjkkjjjkiijkkkjjkiikjkkikikkkjkkijikjkjiijiiikjjkjijkkjijjiijijikjijjijkikkjjjjiikiijkjkijjkiijkkkkjkijijjjiijkkiijjkjkkjkkikiiikjjkjijkkkikkkjkjiijiiiiikkjijkikjjjjjjjiijikijkijjikjjikkjjkkiikjkkiikikjjkjjikkkkkjjikikjjjjiikkkjkkkiijjikkkkjijkikjkkikkkjiijijkjikjjkkjkjijkkkjiikkkikjijijiijjijikkjkjkjijkkjkjjijjjiikjjiiikjjkjikjiikjikiiikkikiikkijiiijikkijkkkjjkikjkikkjkiijikkkkkkjjkjkkkjjiiikkkjkikjkiijjkijjjjiijiikjikjijijjijikkikiijkkjjkkkijjkkjkjjkijkkikkjikjjkiiikiikikkkjiijkjjkikkiijkkkjjjkjjjkkikiikkikjikiijkjijikkkjiijijjijkjikiijikiikkjjkijkijjkjiikikkjjkjjkijkiikjjikkkkkiiikiiikkikkijikjikkjkjikkkijjkkjjkikjijikjjjiijjijiijkikjjkiijjjjjijjkjkiijkkkiijijjkjkkikjijiiiijjkiijjkikjikikiijiikkijjjkjkjjjjijkkkjkkijijjkjjkjjkkijjkjkjjkjkkjkkikjiijjiijjjkkkkijjkijjkiiikjiikiiiiiijikikkjjjjiijjikjjijiikjkikiijkkkjkikkkkjjikjjikkkijkkjkikjjkikjjiijkkikjjjkkiiikjjiijkiikikjkkkkkjiikkjiiiijijkjiikkijkijijkiiijiijkjijjkkiiiiijjjkkikiijkijkijjkkikkikjijkikijjkijiikkkjkkjjkikijkkkkikkkjijkjjjkiiikkjkkkjiiiijijikjikkikkjkjjkkjiiiikiiikkjjijjjjjkkkkjkkkijkiijijjikijikkjikiiikjkjjjjkkjjjkjkkjjkkjjijkjkijiijjijijikkijkjkjjijjjkkijikkjkjjiiijjikiiikiikkiijjjjjkkijikikkiiijiiiijjjijikjijiijkkjkijkiikjjkjkjkkiikikiikkjkiijkkjiijkkjkjkikjkjijikjjkijjjjkijjjjjjkkijkkkkikjijjjkiijkjikkjjjiiikijjijkkjkjijijikjkjijijijjkjjjkjkiiijikiikjikikijkjjikijjjiiiikijjjjkkjikkkkjkkjjkkkiiijjkikikjijjkjikjkijkjiikkkkjjjikikjjkkjikkkiiiijjjkjjkjkiiijijjkkkjkkikikjkiiikjjikikijkijiikkiiikjijjiijkjiikikkikijkkkkkijikkkjiijkkiikijikkjikjjkkiikjiiikikkjkijiiiijkjiiiiijkjjikjjikkjiikjijjjikkijkjiiijijijkkjjikkkjkjikjiijiikkkkiikkjijjjjiiiikiikkkiiijkijkiijkkijkjjjjjjkikkikjjkiiikjjkijjijiiiiiiikkkikjjkiijkkkkkiiijjjiikjkikjkkkjjkikjkikikkikijjjiiiikiikijjkkkkikjkjjijikjijiijkijikkkiiikkkkijiikkkkijjkkkkijiijkjijikkjjiijkkjiikijiijkiikjjjkjjkkjkkjkkjiiiijkkkikijjkikjikikiikkijiikkkkikkjkijjjjjiikjjkjjkkjijjikiijjkjiijkkjkiiijiikkjijjjiikjikkkkijjjkjjkjkiiijikikjjijikjkikijjjjjiikiikjijkkkikkjjjkkjkikikjikjkkkiiijijijkjjkjkiijkikjijjjijkijkikikkikjiijjjiijkikijjijikkiikkijikikkijikkiiijikikkjkjjkiikkijjjikkkjiiikiiikkjikikjiiikijkkkkiikijijjkiikiiijkkijjijjjkjkijikijikijjjikkijijikkikijjjijkikjkjjkkikkkjjkkjikikjiikikjiiikjkiijiijijjijkiiiikiijiiijikjkiiiijiijkijjkkjjkijjjjjkkkiikjjijkkiijiijikjjjiijikiikjjkijjiijikijikkiijkijikkkkikkikijjjikkjijjiijikjijikijjkjikkjijikikkikijikkjjjiikjkikikjjiiikijjijjijkkijiiikkjjjjijikkjijiijjkjkkkjjkkiijjjkjkjikjiiikikkjiiikijjjiiikjjjkikkkkkjkjkiiiijjkikiijikjkkkjkkjijijjjiikijkikkkkkjjikkjiijkkjkjkkkjijjjikjkikjjikiikjijkikijkjkjkkjkjkkiijjkijjjkkjijkijjkjkiijjjkjjjiijkjjiikkkjjkkiijjkkjiikjijijijjiikjkkiijikkkikikijkjijikjkkikkjkjjjkikkijkikijjkjkjjkkikkjkkjjkiiiijkkkjjikjjjkjikjiijijjijkikikiijjikkikikkjiijkjkikkikjjjkkjkkkiijkkijiiiijjkjkkjkkikijkiiiiiikiijikjjijjkjjiikijjkiijkijjjkjjiijkiijkjiijijikkijikkjjjkiiikiikkjjkkkikkjkikkjkikjjjijkijikjjijiijjiiikikjjjjjkiijijjjijjjikijiiikiijkkjijkijiiikjkkijkkjjjjjikkiijikijijjkiiiijkjijkjjkijijkkikijjjkjkikjijiiijjkjikiiikkkkkjijkikiijkjjkkijijiikkiijkjiijkkijjkjikjjjijkiikiijkiijjijjikkjjikjkkjkikikkkikjjjiikiikjjjiiikkjkkkjjjikjijikkkkjkjiikkkiijijkkjiiiiiijiiiijjjikjkjkikijkkjkjjkjkjiijjikikkjjkjjikkjkjkkikjijiikjiiijkijjikkikijkkjjijjkkjkjkjijikiikjkikiiiikjjkijjjjkijiikijkijiijjjikkkijikikijkjkjijjiikiikkkiikkjijjjkjkijkikkjkjikkkijikjikkkjjiijkkjkijjjjjjikkikkikkkkiiijkkkjikjijkiikjiiijkjikjjkjiijjjiikkkjijikijijijiijjjkiijjjiiiijkiikkkkiiijkiiikjjjjjjikijiikiijijiijikjjjjiijkkkkkjijiiiijijkkjjijjijijijjiijjkjijjjjiijjjjikiikijkkjjiikjjkijiikiiiiikkiijjjjkkikijkjiiikjkiikijjijjijjjikkkkiiijjikikkjiijikikijjjkkjijjiijkjjkkiikkkjijjiikkjkkkjkkjikkjjikikiijikjkjkkiiijkkjjikjkjikkikiijikjijjjijjiikijiikiiiijkkkkkiikiikjjjikkkkkkkjkikjjikkikkkkjkjjjjkjiikijijjjijijijkikkiikjikkkiijjjjkkijjjiiiikijjjiiikkkijikjjjijijijkkiikijjjjkkjikjkkjijjkkjkjijjijijjkkjjkkjkkkkkkjkiiikijkkkkkijijijkjkjikikijiiijjijkjjjijikjijikkkjkjjjikjjkiijkjjijkijjjjjkkijjkjjkkiijjijjijkiijikikiijiiikiijjikkiikjjjkjkkjikkikkjijkjjjkjjiikikkikiikikkjjikkjjkijiiikkikkikkjijkkijjikjkjkikikiiiijkjjjijkiikkkkjkjjiikijjjkikjjkkjkikjiiijjijkjkijjjjkijkkkijkikiiikijkkiiiijkkijjkjikikijjkjiiijkjjiikkijiijiikjjiikjjikjijkkikkikijikiijjkiijjjjikijiiijikijkjkjkkkkijjjkkjkjikijjikiijikkjiikkjiiijikikikkkkiiijkiikkijkijikkiijjiikiijjijkiikjkiikikiiijkjkiikjiikkjkkjijijjikjjkjjkijkkjjijjjjikiijjijkjkikkjjijjiiiikkjiikiiiijikjijjjjjiijjjjiiiikiijiikkkkjkkijikijkkkikijkkjkkijjjjjkkikjikikikjkkikkiijkikikijjijikjkjjkkijijkiiikkkkjkikikkkijkkijkjikkkkjikiikijikjiijijjijjikkkkkjkkjjkkkiiikkkkkikkkjijjikikjikkkjiiikkjiijijikijjijjikkjkikiijiijjkjkkijikjkjjjikjijkkkjkjkjkjkjijiijikikkijiiiikkjkkiiikkjijkkkjijjikjjikijjjkiijkjiiikkkijkiiiijjijjijjikjjkjjkkkkjkkijjjiiijkjiiikkikijjjjijkikijiijikijjkjjjikiijikiikjkjjkjkjikiiikjjkkijiiikkijkjkkjkkjijkjiiijijjjkkikjiiikijjkkijkkkkjjkkiikjijkkkkiikiijjijikkkjijiikkjkikkkjijijikjjjkjjijiikjkjkkiiijkiijkkkjiikjjjjjkjjkkkikjiikkkjkkjjjjjjkiijijiijkjjkjikijjiiijiiiikijjikjkijiiikjkijkkjkijikkjjkikiikjjjkikiikikjiiijijikkjiiijijkikkkjkkikijjikijkjkijikijkkkkiijiiijkkjkkjkjjjkjjjijiijjijjikikkiijkjjkjiiijikikjjiijjikjjjjikijkjkiikkjiijkkiijikikjijkijkiijikiikkjjiikkiikijkikkjiijkjkjjjkkijkjikkjjkkjjijkjiiiikjkikjjiiiijkjjkjiikjkikijikikkikiikijijkkkkkkkkkjiikkkkikikkjiiijiiijjkkjkiiikkjiikjijkjjkikjijkkijikikijjiiiikkkikkiikkkjkijkkiikiikkkiiiikijjiiikikkkkiiijjkkjjijkiikkkjkiiikjjjjkkiijjjjiijjikijikijijkkikkkjkkkikiikjjjjkkiikiijjkjikjkkjkikkijjkikjikjkjkj > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/da6bdf5d-bf3c-4d64-bdbf-1a98ab796104%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAAbwPopZKHdzqu3BXCTthztmjARn%2Brd%2Bi-yLKLEpnX3%3DfgJ6mA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
