csacademy's blog

Round #47 (Div. 1 + Div. 2)
By csacademy, 7 years ago, In English

Hello, Codeforces!

We're going to host a new contest at csacademy.com. Round #47 will take place on Wednesday, 06/September/2017 15:15 (UTC). This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

This round will be authored by the CS Academy team.

Contest format:

  • You will have to solve 7 tasks in 2 hours.
  • There will be full feedback throughout the entire contest.
  • Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
  • Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
  • Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

About the penalty system:

  • Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
  • Solutions that don't compile or don't pass the example test cases are ignored.
  • Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

If you find any bugs please email us at contact@csacademy.com

Don't forget to like us on Facebook, VK and follow us on Twitter.

Later Edit:

Congratulations to the winners:

  1. Um_nik
  2. Egor
  3. Radewoosh
  4. anta
  5. uwi

Also, the editorial has been published. Hope you enjoyed the contest!

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

»
7 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Now that Codeforces Round #433 is over, we are waiting for you in 20 minutes :D

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

Any hints for problem E? I know the editorial exists, but I'd prefer a hint over a solution as it's a very interesting problem. :)

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

In Expected Merge, I wrote this function to see if there's a pattern, and was expecting it to work only for small N, but it was so fast so I submitted it and got AC! :P

void calc(int s, int e, int odd) {
	++states;
	cs[s] += p[odd] * (e - s + 1);
	cs[e + 1] -= p[odd] * (e - s + 1);
	if (s == e)
		return;
	int len = e - s + 1;
	calc(s, (s + e) / 2, odd + (len & 1));
	calc((s + e) / 2 + 1, e, odd + (len & 1));
	if (len & 1) {
		calc(s, (s + e) / 2 - 1, odd + (len & 1));
		calc((s + e) / 2, e, odd + (len & 1));
	}
}

p[i] = 0.5i

The worst case I found so far was N = 99669, it visits 246544793 states.

Can anyone find the complexity of this solution in worst case?

→ Reply