Блог пользователя keko37

Автор keko37, история, 3 года назад, По-английски

Hi everyone!

The third round of COCI will be held tomorrow, December 11th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by Bartol, pavkal5, ominikfistric, and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you tomorrow!

  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Would you consider adding rust, while we are at it? :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Sure, we'll try to get it up and running by next round.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      I am currently solving round 2 on DMOJ, and I can send you my solutions afterwards if you need them

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Reminder: the contest starts in less than one hour!

»
3 года назад, # |
Rev. 11   Проголосовать: нравится 0 Проголосовать: не нравится

Why is this code WA for Akcija sub-tasks 1 and 2?

const int N = 2003;
int n, k, w[N], d[N];
vector<int> v[N];
pair<ll,int> best_set[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    REP(i,1,n) cin >> w[i] >> d[i], v[d[i]].push_back(w[i]);
    REP(i,1,n) {
        if (v[i].empty()) continue;
        sort(v[i].begin(),v[i].end());
        best_set[1].first += v[i][0];
        best_set[1].second++;
    }
    cout << best_set[1].second << ' ' << best_set[1].first;
}
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve E?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится
    Solution
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    This may be abit late :P

    solution
    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you recommend other problems that require finding the first $$$k$$$ best answers but solvable with a DP that looks like this?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

What are the specs on the judge computers? My solution to C runs in 2.6s on max-size data on my machine, but got TLE when submitting.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

For problem C(Akcija), does this idea help for a full credit soluton: https://stackoverflow.com/questions/33219712/find-k-th-minimum-sum-of-every-possible-subset? If so, may anyone please elaborate it?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How task D (Ekoeko) can be solved?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I don't have a formal proof of correctness, but here's how I solved it. Go through the left half, left-to-right, and whenever you encounter a letter for which you've already seen 50% of them, flag it (it needs to move to the other half). Do the same with the right half, working right-to-left. The minimum number of swaps to get the balance correct is to move all the left flagged letters to the start of the right side (without changing their order), and vice versa. Once you've got the sides balanced, you can permute the right side to match the left side (or vice versa, or meet somewhere in the middle, but there is a triangle inequality that prevents meeting in the middle from being any better).

    Rather than doing all the swaps, you can compute what the final string will look like. Then there are standard algorithms to determine the number of swaps required to implement a permutation in O(n log n) time.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      That's interesting! Thanks for sharing your approach.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you Share your code please :)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What are the algorithms you are talking about?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        You need to count the number of pairs of elements that are out of order ("inversions"). One option is to run mergesort and augment it to count the number of inversions between the two halves of each merge as you merge. Another is to run through the elements left-to-right, counting the number of previous elements that are larger than the current element, with a data structure such as a Fenwick tree to quickly count the number of values seen in a range.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please elaborate a bit more on the triangle inequality that prevents meeting in the middle from being any better? I am unable to understand this part. Thanks for your great explanation!

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Let A and B be two permutations, and d(A, B) be the minimum number of swaps needed to transform A to B. Then d(A, B) ≤ d(A, C) + d(C, B) for any C, because the RHS is the cost to go from A to B via C. And if you want to make A and B match by transforming them both to some C, then the cost is d(A, C) + d(B, C) = d(A, C) + d(C, B) ≥ d(A, B) = d(A, B) + d(B, B). So it is always at least as good to just transform both to B.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

The tasks, test data, and solutions are now published! You can find them here.

You can submit your solutions here (HONI).

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -102 Проголосовать: не нравится

    Good morning sir(In Croatia it's about 9 o'clock I think), I want to see the PDF of all the tasks but when I clicked on Tasks just now, it showed me the status 403. Could you please take a look into it? Thanks in advance.