adamant's blog

By adamant, history, 7 months ago, In English,

Hi everyone!

I gave a contest in winter Petrozavodsk programming camp and now I'd like to share it with codeforces by making it a contest in codeforces gym: 2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1. It was my first experience giving a contest to the camp and I'm pretty much excited about it!

In the camp only 7 out of 11 problems were solved, so there should be something in the contest for everyone. To make the contest more interesting I suggest you to participate in it as live contest on Saturday, 9 March, 12:00 (UTC+3), which may be changed in case of overlap with some other contest or if it's inconvenient for many participants. After this I suggest to gather here and discuss problems (if anyone's going to participate, of course). I will also post editorial which may (or may not) contain some neat stuff.

Uhm, good luck and have fun :)

P.S. It appears you already may see problems if you have coach mode enabled, I'd ask you to not do this unless you're not going to participate in contest!

UPD: Gentle reminder that it's less than 24 hours before the contest and it's hopefully not going to be rescheduled this time.

UPD 2: Thanks everyone for participating in the contest! Here are editorials: link

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

There is an AGC on 9 March, 15:00 (UTC +3). Could you change the time?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think so, but I'm not sure what time should I choose then.

    I'm considering 9 March, (from 17:30) or 8 March (from 12:00) or 10 March (from 16:30), all UTC+3. By "from HH:MM" I mean any time from HH:MM to, like, 18:30.

    Would like to know opinion of somebody who is interested in writing contest (if any)

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

      Personally I prefer 8 March, 12:00 (UTC +3).

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

        Welp, so be it then :)

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Oh, codeforces placed rated round on the same time >.<

        Guess have to move it again...

        I moved it to 15:30 same date for now, will move again if anyone complains

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the duration of the contest ?

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

how many string problems will there be?

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Because AGC has moved to Sunday, I move the time of my contest back to initial time of 12:00 (UTC+3) on Saturday, 9 March.

Sorry for inconvenience ^.^'

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems! I really enjoy them.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems! How to solve A?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it
    (A * B)[0] = (A[1] + A[2]) * (B[1] + B[2])
    (A * B)[2] = A[0] * B[1] + A[1] * B[0]
    (A * B)[1] = (A[0] + A[1] + A[2]) * (B[0] + B[1] + B[2]) - (A * B)[0] - (A * B)[1]

    O(4^k)

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

    You may also look into editorial for some kind of rigorous proof.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B and G?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do I?

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

How to solve F?

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

    F: Consider all edges with cost at least x. Maintain connected components for all edges with such costs and for only major edges. Each component connected by all edges is a union of one of more components connected by major edges. If there are more than one components in that union when all vertices in this component are bad.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's assume there are no '?'. Then let's build a bipartite graph with n vertices in each part. For columns i and j if the first m - 1 characters in i-th column are equal to the last m - 1 characters in j-th column, add an edge (i, j) to the graph. We need to count the number of perfect matchings in this graph. Notice that each component in this graph is complete. If in some component number of vertices in both parts of the graph is different then the answer is 0, otherwise it's the product of factorials of sizes of components.

    Now let's deal with '?'. For each row calculate multiset of characters it that row. If some of these multisets are different then we can find out what each of '?' must be and solve the problem without '?'. Otherwise all the '?' should be the same character. Let's just try all possible characters. We only counted multiple times permutations that map each '?' to another '?'. So count the number of such permutations and subtract it each time.

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

WJMZBMR you might also be interested in discussion here and/or editorial :)

(Since I saw you wrote it on opentrains)

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

    Actually it's me.

    I think you should write "we should compute the distinct pairs" in the statement for the string problem.

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

      That's true... Has it caused you any trouble?

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

        Not too much. BTW I really love the problem set. However, after finishing easy problems, I don't know which one is more solvable.