keko37's blog

By keko37, history, 3 years ago, In English

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!

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

»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

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

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Reminder: the contest starts in less than one hour!

»
3 years ago, # |
Rev. 11   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Consider this input:

    2
    2 2
    2 2
    
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you skip k? What is the expected output?

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

        Oh sorry, forgot to include k — should be 1. The point is that your solution will buy only one of the products but they can both be bought.

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

        If k = 1 expected output is 2 4

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it
    Solution
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    This may be abit late :P

    solution
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Intel Xeon E5-2640

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

      Ok, I guess I shouldn't expect too much from a CPU that's almost 10 years old.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How task D (Ekoeko) can be solved?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      That's interesting! Thanks for sharing your approach.

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

      Can you Share your code please :)

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

      What are the algorithms you are talking about?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

You can submit your solutions here (HONI).

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -102 Vote: I do not like it

    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.