MikeMirzayanov's blog

2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
By MikeMirzayanov, history, 8 years ago, translation, In English

Today 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest will be held. On behalf of jury and hosts I wish teams to make happy their coaches!

You can watch the results by the link https://contest.sgu.ru/monitor/1.

And on Sunday (October, 23) on 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

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

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

Good luck for all!

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

Good luck to all especially CF users who are participating in NEERC. make us proud :3

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

There seems to be a typo on the contests page; the contest tomorrow is named "2015-2016 ..." instead of "2016-2017 ...".

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

The contest will not affect Codeforces ratings.

For sure, it will be unrated contest.

that moment when the author no longer can put up with "is it rated" comments so he repeats the information twice to make sure no one will ask it.

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

Contest clashes with Code Festival.

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

Are problems going to be shuffled since we can see the results?

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

Great contest! Is there something like official slides with solution outlines? I remember those are available for other ICPC contests like NWERC.

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

For Problem D, with this input :

5 2 10 5 4 1 7 14 10 12 4 10

Why this output is considered as wrong answer? 5 8 10 12 46 48

while jury's solution is

5 8 10 12 40 42

i think it is possible for my solution.

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

    According to your answer, you'll begin to cross the final bridge at time 34, not 40. Did you add t_i instead of actual crossing time?

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

How did some people pass I with min cost flow? Wouldn't it TLE with these constraints?

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

    In my case, I didn't know how to solve the "right" way so I decided to give it a try (and I had good reasons since I had seen someone pass this problem with a min cost max flow solution — the flow model is basically the same as problem I)

    The Big O notation is mean to flow functions, in practice they are usually faster than they seem. If you consider my code which uses SPFA (which has O(E) average shortest path) the code would be average O(V * E) still and I think it might be hard to create an O(V * E) SPFA case for the nature of the question

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

    What is the expected approach for I?

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

      we solved problem "I" with a greedy approach with O(n2log(n)) complexity.

      code: http://mirror.codeforces.com/contest/730/submission/21712213

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

        My greedy approach for problem I is O(n^2) 21710921 and can be optimized further to O(n*log(n)) using two priority queues.

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

          Do you care to describe your approach? I always like to see what people's reasoning was for a specific algorithm, beyond just the code :)

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

            Sure, sorry for my bad code. I'll explain how I get my idea step by step:

            • For simplicity lets define F(p,s) as maximum total strength by choosing p programming students and s sport students

            • Immediately, I found very simple DP solution but O((n^3)/6) is surely TLE, so I tried to find if there is greedy approach

            • At this point I think about easy case, for example what is F(p,0), it can obviously be solved by using greedy and sorting.

            • To print the answer easily, I also define A[x]:

              • A[x]=0 if x-th student is not chosen
              • A[x]=1 if x-th student is chosen for programming team
              • A[x]=2 if x-th student is chosen for sport team

            • Next I asked myself if I can easily compute F(p,0) and A[x] for F(p,0) could I find F(p,1) and update A[x] for F(p,1), and if I can could I do it again for F(p,2),F(p,3),... until F(p,s)?

            Spoiler Alert: the answer is yes; here's how
            • Total complexity is O(n^2), you can optimize it to O(n*log(n)) by using two priority queues one for keeping maximum of S(x) for x in group 0 and one keeping maximum of S(x)-P(x) for x in group 1.

            Took one full hour to write this, now I feel how hard CF contest author to prepare editorials for 5 to 7 problems. It make me appreciate it even more :)

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

              Oh yeah, it's very hard to write good and intuitive algorithm explanations. And you killed it at this one! It's very much appreciated!

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

It would be great if someone write a solution outline for this contest. Currently I am stuck on problem A and I will appreciate a hint.

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

    The best way to lower the points of the player with most points is: Lower him at the same time as other players that have most points.

    So you need to lower him until there is at least a pair of players with most points and the rest is easy because you can lower all the players with same points at the same time by grouping them in a smart way without ever lowering the player with least points.

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

Great contest!!!

I have a question in problem "I" I found a dp solution with the DP state (position , needed_sportsmen , needed_programmers) but that would give TLE and MLE because it's 3000 * 3000 * 3000

I think the solution is dp with some optemization but I couldn't find it can someone give a hint please !!!

thanks in advance.

:)

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

WTF problem A : Toda 2 ~ Dota 2...

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

What is the expected approach for E?

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

Can anyone prove why greedy works for E? Apparently we just have to consider the teams who will have their score decreased after freezing (call these down teams) and the teams who will have their score increased after freezing (call these up teams), and start unfreezing from the up teams in ascending order of a[i], then unfreeze the down teams in descending order of a[i]. If there are only up teams then unfreezing them in ascending order of a[i] will be the optimal strategy and similarly when there're only down teams. However, why can we consider them seperately when we have both types?

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

    If you have two teams, one of which has positive delta and the other one has negative delta, it doesn't matter in what order they are unfrozen. Answer is increased by the same value in both cases. So it's enough to consider positive and negative teams separately.

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

How to solve Problem A (Toda 2)?

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

Don't understand dp solution for problem I on Codeforces (C in the editorial). Assume that sorted students by decreasing of a[i].

We have 2d dp[i][j] with states: i — length of prefix we already processed, j — size of people who goes to team A.

And we have following dp formula (it is how I see it):

dp[i][0] = b[i]
dp[i][j] = max(dp[i-1][j] + b[i], dp[i-1][j-1] + a[i])

But it will give correct answer only if total number of students is same as sum number of contestants in both events. In other case we can latter optimize and make swap of people we take. But I don't get what I am doing wrong.

Test case where given strategy will not work:

5 2 1
5 5 3 1 1
6 6 3 5 5
→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Is there English Editorial/solution sketches available for this contest?

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

How to solve J (Bottles)?

→ Reply