Jun 112016

This post is about last year contest (2015). As you might already noticed, there are no post on **INC 2015** and **ACM-ICPC 2015 Jakarta** in this blog. The reason is … I was quite busy at that time (sorry), and by the time I have free time to do so, I already forget the details.

I’m writing this post for the sake of continuity (and completeness). Also I would like to let you know a couple of things:

- ACM-ICPC 2015 Jakarta problems are available on ACM-ICPC Live Archieve. I guess it has been around for quite some time as I sent the data immediately after the contest. Alternatively, you can download the problemset HERE.
- INC 2015 problemset is available to download HERE.
- I’m not going to write any problem analysis for both INC 2015 and ACM-ICPC 2015 Jakarta in this blog.
- You can download the problem analysis for ACM-ICPC 2015 Jakarta which was distributed to the contestants HERE.

Thanks for preparing these interesting contests! Some problems inspired us a lot!

By the way, if convenient, could you please reset/resent the data of 2015 Jakarta problem C(Counting Partition) at Live Archieve? It seems that the input data may be misplaced.

Hmmm, yeah. It seems there is problem with the uploaded test data (reference solution got Wrong Answer).

I have contacted the LiveArchive admin (I can’t upload the data by myself). Hopefully he’s not too busy and can fix this as soon as possible.

You’ve been a great help already. Thanks a lot 🙂

After reading the solutions, I am confused with the analysis of 2015 Jakarta problem J and wondering if you could do me a favor 😛

The analysis pointed that “the number of nodes in the graph is at most 210 * 19 = 3990 nodes”, which is what I can not understand. I understand in this way:

Considering the maximum length of each string is 20, there are at most 210 substrings of each string. But each substring can be replaced by at most 4 other strings (each with length at most 20), thus the number of nodes in the graph(NFA) is at most 21 + 210 * 4 * 19 = 15981 nodes.

Do I analysis it in a wrong way? It seems the number of nodes is kind of too large to suit the DP solution. Hopefully you will be convenient to correct me soon.

I’ve just had discussion with the author (also the writer for the analysis). It seems we made an error on setting up the constraint for problem J 🙁 Your understanding is correct, the total nodes should further be multiplied with 4.

In the author’s defense: he made several changes when preparing the problem, and failed to keep track on the complexity of the solution. apologize 😐 The tester’s solution is slower than the reference solution (TLE), it used different approach; we only used that to test the correctness of the data.

After discussing with him, there’re seems to be some optimizations can be applied to “patch” the solution, e.g., contracting some nodes, thus, turn the dp transition from “move both via a same character” into “move both via a same string X” — but the implementation can be quite challenging; you have to analyse what “string X” is (should be done on-the-fly). As for the state, you can simply use map data-structure. Note: we haven’t analysed the complexity of this optimized version.

BTW, the test data does not contain case where the total nodes is more than 3990. So, you may get AC with the original solution.

Well, it is still a nice problem in spite of the condition which is not pointed out. The original solution could be implemented as BFS, but the optimized one may not. Anyway, the original solution is educational for me. Thanks for the detailed response. 🙂