rng_58's blog

CODE FESTIVAL 2016 Qualification Round B
By rng_58, history, 8 years ago, In English

CODE FESTIVAL 2016 Qualification Round B will be held on Monday (time). The writer is DEGwer.

Contest Link

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. Top 5 foreign students of this round will qualify. If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/code_fes_2016. Please check the detail of the tournament at http://codeforces.me/blog/entry/46647.

The contest duration is 2 hours, and there will be 5 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added one more problem and we hope this is interesting enough for choosing top 5 qualifiers. (Anyway, most probably the qualifiers will be determined by the speed of solving all problems). Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 500 — 700 — 1100. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

UPD: Among the top 5 foreign participants, Arterm has already qualified from round A, and matthew99, Reyna, SkyDec are too young. Congratulations to Merkurev, polequoll, fqw, sevenkplus, and Zlobober! Note that this information is unofficial, and it is possible that some of them don't want to participate in finals (or ineligible).

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

Comments Comments (21)
| Write comment?
»
8 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Excuse me, does author of E's statements know such language as English?

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

    Was it unclear? All English statements of AtCoder Problems are written by the same person.

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

      "Output the sequence of the string Sk". I would say "sequence" is kinda unusual word for "position". Moreover I also had hard time understanding "when the literal sequence is pi, 1 < pi, 2 < … < pi, 26", which alone is not that very bad, but connected with previous "sequence" issue made guessing what is going on from sample in/out an only option for me.

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

      On this time, the English problem statement writer is not the usual person, but the statement was once checked by him.

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

    How many guys like me read pE as "who is rank k" instead of "what's the rank of s_k"?

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

      Same here ._./

      But, whether "who is rank k" is solvable with same constraint?

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

        Same here... So many Taiwanese people misunderstand the problem...

        BTW, The misunderstanded problem can be solve in O(Q*sqrt(sum of |Si|)*26).

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

          Compressed Trie?, or is there a better way to do it?

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

      Samples rule it out, don't they? I believe samples and constraints are essential part of statement (but I don't like ambiguous legends too).

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

        I almost never look at samples if I think I got the statement correctly (which is often a mistake, but that explains such behavior), however here I have no idea how can could have thought he understands statement after reading it, so I also don't get how it was possible to think that one understands statement, but getting it wrong.

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

      I even wrote entire solution for wrong problem. It was quite unpleasant surprise when I agreed with my program on sample tests, but provided outputs didn't.

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

        I did too :(

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

        Me too. It seems that I didn't qualify for the finals just because of that. The code is almost the same, but I spent some time to understand what's wrong.

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

    I rechecked the statement, and it was indeed very difficult to understand. I'm sorry about that. However, since we don't want to disappoint the top 5 people in this contest, we will choose the qualifiers based on the results of this contest (and no rematch).

    I think this trouble was caused by the change of translation process. Usually evima translates the statements from scratch, and when he translates he understands the statement and then reconstructs it. However, in Code Festival rounds the problems are first translated by professional translaters (who has probably no experience in competitive programming / mathematical statements) and evima proofreads it. I feel the translation was too direct and also not suitable for competitive programmers (for example, it seems one of the meanings of the word "sequence" is "index", but for us "sequence" just means "array"). We are discussing if we can change the process of the translation from next round.

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

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

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

How to Solve task C?

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

    Let at some point you have used R rows and C columns costs. Now pick the minimum of all the costs that you have and if it's a row cost, answer will increase by : (cols + 1 — C) * thisCost; and R++. Similarly for a column cost.

            sort(vals.begin(), vals.end());
	matSize[0]++;
	matSize[1]++;
	ll ans = 0;
	fl(i,0,vals.SZ())
	{
		pair<ll, ll> p = vals[i];
		ans += (p.first * (matSize[p.second ^ 1] - done[p.second ^ 1]) );
		done[p.second]++;
	}

    Proof of this solution is trivial as you would try to use the minimum cost to connect maximum nodes.

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

SkyDec is the same grade as me :)

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

Sorry,I don't want to participate in finals. And I am the same grade as matthew99,so I am ineligible.

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

I have just started competing at atcoder and like everything very much except for one thing: testing results are only shown after whole testing is completed. It's really annoying if you for example have wa1 because testing is not very fast. Would you please fix it somehow?

Really like type of problems, exponential system of scoring and acm-style system. Everything makes competition results more exact and I like it!)

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

    I've felt the same thing for years and asked officials to fix it several times.

    It seems that they know the matter is urgent but they're too busy (it seems they don't have many engineers and there're a lot of contests these months) to start on the modification.

    → Reply