Grzegorz's blog

GP of SPb
By Grzegorz, 8 years ago, In English

It was enough interesting problems, I suggest discuss some of them. Who has proofed solutions of E and H?

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Where can we find the problems?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    If you have the opencup login then here: link. Until I don't know, could I post statements here.

    → Reply
»
8 years ago, # |
  Vote: I like it +50 Vote: I do not like it

H: Let's find a dfs search forest (from some vertices in each connected component). If it contains a path of length k + 1, print it. Otherwise, color each vertex with it's depth in the corresponding dfs tree.

Any ideas for problem I?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Who has proofed solution of H?

I do not know which solution did you mean, but my solution is proved by design.

Let's start coloring vertices using dfs. Each time we'll try to find such color C that is not used by neighbours, but color (C-1+K)%K is used. When paint vertex in this color C and remember neighbour with color (C-1+K)%K as previous for current vertex.

If we do not fail on such painting process, we have a graph's coloring. Otherwise, we failed on painting of some vertex v. That does mean, it neighbours uses all the colors, including color K-1 (0-based), so there is adjusted vertex u witch has color K-1. Here is some simple path from vertex u which is constructed by walking to previous vertices, and it's length is not less than K-1, so by adding edge u->v we have sought-for path with length K.

→ Reply
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +44 Vote: I do not like it

    Problem C:

    Consider multigraph on n vertices (not 2n!).

    Disjunction ([not]x[i] | [not]x[j]) is edge between vertices i and j.

    The solution is recursion (backtracking with optimizations).

    1. If value of any variable may be deduced, deduce it.

    2. If there are to connected components, calculate it separately, multiply results.

    3. Fix unknown variable of maximum degree and do 2 recursive calls.

    4. Your may add memoization to speed up the solution.

    5. Your may handle the case of "maximum degree is two" in polynomial time.

    As I know, the first 3 ideas were enough to get OK.

    P.S. T(n) ≤ T(n - 1) + T(n - 1 - maxDegree)

    UPD: (4) implies (2) for components of size 1 (degree equal to 0)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I just used memorization only.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Even no (1) and no (2)?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I saw that (1) happens automatically and thought solution is good enough as it is. I did not realize that hueristics can actually reduce the exponent.

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      We used just 1 & 4.

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

E: Main idea: number of ways to divide subset only depends on count of vertices. We can use DP to calculate it for every size.

dp[0] = 1;
for (int i = 2; i <= n; i += 2)
{
	for (int j = 1; j <= i; j++)
	{
		for (int h = j + 1; h <= i; h += 2)
		{
			dp[i] += dp[h - j - 1] * dp[i - (h - j - 1) - 2];
		}
	}
}

Let's find first pair in subset. Sort all possible pairs and iterate over them. We need to know number of ways with this fixed pair in order to choose, take this or not. Number of ways depends only on size of left and right subset. Find this pair and recursively solve at first for left and then for right subsets.

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

What about I? We had 2^32*const solution, it was too slow, like 45 seconds instead of 5

→ Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I've seen several "read a paper" problems in Open Cup but I've never solved it. How do you solve it?

Search, read, understand, and implement a 10-page paper during a contest looks overwhelming to me. Is it important to find an easy-to-read article? Do you know the algorithm beforehand? Are you actually very good at reading papers?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please give a link to the paper?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      According to wikipedia the fastest algorithm is O(1.2377n), but we don't have an access and maybe this is an overkill.

      This paper looks simpler, but it says this is O(1.62n) but I'm not sure if this is fast enough.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +25 Vote: I do not like it

        This paper is fine. The algorithm presented there is even harder than needed, what I've successfully submitted looks like:

        • if at any moment you can deduce value of some variable or remove unnecessary clauses, do it
        • if the graph induced by clauses on the variables (n vertices in total) is disconnected, solve each component separately and multiply the answers
        • otherwise, try two options for some of the variables: if mentioned graph has the articulation point, try it (and perform two recursive calls), otherwise try the vertex of the maximum degree

        But I think that using such classical problems on a competition is a completely bad idea. All I had to do was to know that this problem is called #SAT (or sharp-SAT). Also, this particular problem is very hard to prepare, I'm not sure that it is possible to come up with reasonable tests for it.

        By the way, it is one of the main counting problems that arise in CS, the #3SAT is actually a #P-complete problem, meaning that many counting problems may be reduced to it, like 0-1 matrix permanent, counting number of topological sorts of the DAG, counting number of correct k-colorings, and several others.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        This one

        http://codeforces.me/blog/entry/47641?#comment-319796

        is not very hard to invent without any papers.

        It works in 1.46n or 1.38n (if you handle the last case).

        In practice it works faster.

        To solve you have to know only one base idea "consider graph, take vertex of maximal degree".

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +36 Vote: I do not like it

          P.S It's interesting to know, how many people used papers from google to get OK.

          Please, "like" this comment,

          if you read special papers during the contest, and got OK.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +162 Vote: I do not like it

          Please, "like" this comment,

          if you did not used any special papers during the contest, and got OK.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            173 people got OK?

            Anyway, if we believe the ratio, it seems we should ignore the paper and solve it as usual.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +13 Vote: I do not like it

              Possible reasons: If you rating is high, your upvote gives more than +1. Also most teams consist of three members.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +20 Vote: I do not like it

                Lol, your upvote gives +2 at maximum, there are 3 members at a team and 19 teams that solved this problem, giving us 114 votes at maximum.

                I believe there were lots of people who didn't even participate in opencup, but who like the idea of using or not using any papers in general, and who felt that it is fine to give their upvote for one of the options, even though they were not asked for it.

                → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Despite the fact I've never solved, let alone attempted such a problem, I suppose it's more about having an eye for a particular algorithm, which usually means you have already implemented the said algorithm in the past at least once or twice, and all you need during the contest is a quick(?) rehearsal.

    → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    Just try to randomly generate some sets with sizes 10..1e7 and look at the min/max/avg value of distinct_values/total_asked_values (hint: it's better to ask 10_000 values).
    Then you'll able to find the answers and insert it to the main program.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    My solution used Birthday Paradox. That is, the number of questions until two cards repeat is somehow close to sqrt(n), where n is the size of the set.

    Let's do the following procedure: while I still have questions, ask questions until two cards are identical. Then, store in a vector number of question asked and repeat.

    All numbers from my vector should be close to a value of sqrt(n), where n is in the set {10, 100, ...., 10^7}. The only remaining part is to find n such as numbers from my vector match best sqrt(n).

    Let's iterae over powers of 10 and call X = sqrt(current number). We simply need to find an heuristic to see how close are number from the vector to X. We used sum {(vector[i] — X) ^ 2}

    Then, pick X such as the sum is minimized and output corresponding power of 10.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I used Bayes formula and returned sets size with maximum probability (using uniform distribution over allowed values as prior).

    → Reply
»
8 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Had solved stringy problem 'J' (about timer) with Perl, 127 lines (ideone).

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Anyone know how to solve problem I?

→ Reply