Hello.

Last Satuday we had the Brazilian Sub Regionals for ICPC 2015/16, an online contest was held at the same day on uva online judge.

I'm creating this post so we can discuss the contest problems.

Can anyone give me a hint on how to solve "I — Ominobox", "G — Curious Guardians" and "L — Lottery"?

(The other problems we either have solved during the contest or have solved after, so if you need help with any other one, let me know)

Hello, I'll be preparing more seriously for this years subregionals/regionals for the months to come. So I thought this would be a good idea.

I've created a mailing list for a study group here: https://groups.google.com/forum/#!forum/icpc-2016-study-group

The idea is to create a study group where whenever we find a good problem that helped we learn something new in a good way, or some good materials to learn something, etc, we share so we can help each other prepare better for the ICPC this year. Or maybe motivate ourselves and push each other to work harder as well.

(For asking questions I think it's probably better to do it here because then more people can see it/learn from it, but maybe in a study group we can ask more "silly" stuff without being afraid as well lol).

Anyone that wants to join is welcome, but please contribute if you do so! =)

Hello, I'm trying to solve E — New Year Domino from last contest, following the tutorial #1.

The tutorial mentions that you can calculate R[i] "using a segment tree or using a stack". My first approach was to try using a stack to see how it could be done, but I'm getting TLE on test 12: Here's my code/submission: http://mirror.codeforces.com/contest/500/submission/9349751 Is there something wrong with the way I'm using the stack to do it?

I also tried to do it with a segment tree then, but I'm getting "WA on test 7" with this approach. Code: http://mirror.codeforces.com/contest/500/submission/9352369 (the segment tree code is from the book Competitive Programming — 3rd edition). It's essentialy the same approach as before, but using the segtree instead of a stack. Printing the contents of U and R for the small test cases is giving me the correct values, so I was unable to find the error. Can someone please help?

PS: in the code:

• pos[i] and len[i] are the x-position and length of the i-th domino

• R[i] is the maximum x position covered when you drop the i-th domino

• U[i][j] has the 2^jth "uncovered" piece index when you drop domino i (the 2^jth piece to 'break the interval'), as described in the tutorial

• S[i][j] has the value needed to cover from i to U[i][j].

Hello all,

I'm trying to solve this problem on UVa: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3783 (from ICPC South America Regional Finals 2011).

I've seen how to solve it using Suffix Arrays/LCP Arrays. However, I'm trying to solve it using a Suffix Automaton, mainly to learn more/get more used to it.

So, my approach is this:

• Concatenate each file using a different separator $ (one that is not a-z).

• Build the Suffix Automaton for the resulting string

• Now, instead of finding the end-sets of each node (the indexes on where the substrings represented by that node end), I use a bitmask on each node the following way: If index i would appear in the end-set of node n and i belongs to file f, turn f on in node n (n.mask |= (1<<f)).

• To see the how many searchable subsets are there, I do a DFS from the root (ignoring any '$/!/..." transitions) and count how many different bitmasks I have. (Also, I ignore the source node that represents the empty string).

The rationale behind this is that if the substring appears on indexes belonging to the files f0, f1..., that substring (and all substrings represented by that node) can be used to search that subset (and only that one). Ignoring the '$'-transitions should guarantee that we don't end up checking any invalid substring.

I'm getting WA with this approach. (It gives the correct answer for the mojority of the test cases, though :( ).

Could anyone please help me find out what's wrong with this idea?

Hi, I've being trying to solve this problem on SPOJ: http://www.spoj.com/problems/WPUZZLES/ (which I've seen in many places as a recommended Aho-Corasick problem).

I'm currently getting WA on it and can't figure out why, could someone please help giving me a hint about what is wrong? (Or maybe giving me some test cases where it fails).

My current code is this: http://pastebin.com/vzLNwKk6 The aho-corasick part is based on this implementation: https://gist.github.com/andmej/1233426

My idea is: put both the word and its reverse on keywords[], then run on the matching machine with each line of the puzzle. I'm currently running 2 directions at a time in the loop (4 with the reverses). Directions 'A', 'C', 'E', 'G' in one and the remaining in another.

As far as I can tell, a matching is missing when the code is printing the answer, have no idea under what circumstances this happens though.

Any help is appreciated!

Hello,

I came across this problem from NWERC 2012: https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4283

It seems like you need to use vertex cover and take advantage of the recursive structure. However, I'm warping my mind around it and I'm not still sure of how to solve it.

I would like to try to solve some basic vertex cover problems first and try to approach this later. Does anyone know a good problem from any online judge to recommend?

(I'm talking about the NP-Complete vertex cover on small instances, not vertex cover on bipartite graphs, trees, etc)

Is it possible to enter a contest after it has started?

I'm trying to find where I can register here, without success :(