Hello @all,
I have to say that I absolutely loved JAN14 and even though I haven’t had that much time as I would have liked to attend it (due to exams and similar constraints), I managed to solve three problems which made me learn new things, so, I call this a good contest for me.
The problems I solved were (again) the three most solved ones, which were:
- ERROR:
Thanks to this problem I managed to learn about the C++ STL find() function to search for substrings in larger strings, which I didn’t know about, so, that was quite interesting to me although the problem is relatively simple!
- PLZLYKME:
This was the second problem I solved and it was a really funny one!! 
The main thing I focused on doing was to express D1 as a function of the N following days in the hope of deriving a recursive or even a closed-form relationship, and, well, turns out I wasn’t so rusty in Maths this time and immediately derived this:
DN = D1 (C+1)N-1
However, the above formula was still terrible as now, according to the problem we needed to check that:
D1 (C+1)N-1 >= L
with the given constrains, this was not good at all.
However, if we applied some sort of “domain reduction” and still retained the increasing properties that the power function had, we’d be good!!
Well, turns out applying log function on both sides did wonders as it scaled down the values, as we needed them to and it retained all the mathematical properties needed and this solved the problem for me 
- FGFS
This problem was actually quite hard for me to reason about for a while… After drawing some drafts and intervals on a piece of paper and doing some experiments, I saw that this problem was actually about counting the maximum number of non-overlapping intervals over a given range.
After doing some google research I came against some results which told me this could be seen as the non-weighted variant of the scheduling problem.
I have never attempted to solve such problem before and after some university video lessons and powerpoints, I came to know that this variant could be solved by a simple greedy algorithm and no need for DP!!
After re-reading problem I confidentely understood that the intervals could all be marked with the same weight and that the preferred seat parameter could be seen as the “number of times” we would need to apply the simple greedy algorithm. (for this realization to come up for me, I used a data structure which was a map<prefered seat, vector of intervals> )
Once I understood this, it was easy to find online implementations of the greedy algorithm and I managed to solve it
Besides these three (very!!) funny problems, I still attempted two more during contest time: the SEAGRP one and MTRICK.
- MTRICK
I gave up on MTRICK one quite fast, as I was getting WA constantly even with the algorithm which should be giving TLE (I was thinking on using some sort of tree structure to attempt and improve my runtime if I ever managed to get a TLE veredict). Turns out that multiplication of large numbers modulo C tricked me during my first attempts and, after fixing it, I got the so desired TLE.
However, after attempting to use my tree idea to improve my solution, I understood that I wasn’t going to be able to actually implement it, as I had no idea on how I could update a range in Fenwick Tree efficiently AND at the same time, see the range updated in the original array, so I got stuck up in this issue.
After a while, I even considered maintaining two separate arrays (one for additions and another for multiplications) and use all the accumulated changes at once, but, even this approach didn’t seem such good idea to me, so I gave up for good.
- SEAGRP
SEAGRP was a lot more interesting for me to attempt, for a multitude of reasons: first, I believe there was more information available online about it, so I had much more opportunities of finding good material to work with and second, well, I really, really want to solve a Graphs problem on a contest someday.
The first “issue” that comes up with this problem, is the fact that the graph “can be” disconnected. At least, during the contest this seemed to bug some people.
I, on the other hand, quickly realized that for some cases, not only the graph “could be” disconnected, as it SHOULD BE disconnected in order for every vertex to have degree 1.
This was quite a funny thing to be looking at… How would I “check” efficiently for the degree of every vertex in the adjacency matrix? And what if we had two repeated edges between the same two vertexes (like on the first test case), what to do then?
All of these questions were very good questions and I managed to exploit some properties of the adjacency matrix while reading things for this problem (summing all columns on a given row would give me the degree of the vertex on that corresponding row for instance), but, none of these properties seemed useful to me…
I then read about Havel-Hakimi theorem and about the handshaking theorem and their relationship with the degree of the vertexes, but, nothing of this would help me in knowing if I could remove edges to make the graph 1-regular or not… It seemed like I was at a dead-end…
After doing some more researches, I ended up reading some nice formulas about eingenvalues and eigenvectors on mathstackexchange and wikipedia, and I pulled up the (very promising!!) two facts together:
- If the graph is 1-regular with N vertexes than it has N/2 edges;
- Let A be the adjacency matrix of a graph. Then the graph is regular if and only if j = (1,1…1) is an eigenvector of A;
Combining the above two facts, led me to a bunch of WAs, so, I decided to search and think even more, and, in the end, I ended up with a sort of “alternative idea” that I’m not sure at all if it is feasible and/or correct.
- My (possibly wrong) “Domain compression idea”
I decided to think in the most alternative way I could, so, I decided to represent the graph edges (which, recall, are given by the vertexes which they connect) as points on the Cartesian plane. So, now, on my representation an edge is seen as a point.
As a result of the above, connections between points represent the existence of multiple edges.
After some analysis of such scheme I came to realize that diagonal connection between points (edges), would allow for the correct answer to be derived, at least, on the sample cases, but, I had no time to implement it or explore it further.
Below you can find a drawing I did of this scheme:
.jpg)
This was as far as I got on this problem as well…
Nontheless, I can’t wait for some editorials and I can say I had really lots of fun with these problems and I hope next contests can be as good and, if possible, better than this one was!!
Best regards,
Bruno Oliveira