Alex_KPR's blog

By Alex_KPR, 13 years ago, translation, In English

It will be fully translated later, sorry for slowpoking :(


Blackjack (problem A, div-2). The problem's author is Alex_KPR

 

 

Obviously, suits are not change the answer. Look at all possible situations:

[0 - 10] — zero ways.
[11] — four ways using aces.
[12 - 19] — four ways using cards from 2 to 9.
[20] — 15 ways, they are described in statement.
[21] — four ways using aces.
[22 - 25] — zero ways.

 

 

Complexity is O(1).

 

 

Testing Pants for Sadness (problem B, div-2; problem A, div-1). The problem's author is Alex_KPR

 

 

We can't move to the i + 1-th question before clicking all answers at i-th question. We will move to the very beginning clicking at ai - 1 answers and only one will move us to the next step. Every way from beginning to i-th question have length equal to i - 1 plus one for click. There is a simple formula for i + 1-th question:

ci = (ai - 1)· i + 1, 1-based numeration.

Let's summarize all values of ci for making the answer.

 

 

Complexity is O(n).

 

 

Cthulhu (problem C, div-2; problem B, div-1). The problem's author is Alex_KPR

 

 

Look at the formal part of statement. Cthulhu is a simple cycle with length of 3 or more and every vertix of the cycle should be a root of some tree. Notice this two important facts:

a) Cthulhu is a connected graph
b) Cthulhu is a graph with only cycle

If we add only one edge to tree (not a multiedge nor loop) then we will get a graph that a) and b) properties. There is a simple solution: let's check graph for connectivity (we can do it by one DFS only) and check n = m restriction. If all are ok then graph is Cthulhu.

 

Complexity is O(m).

 

 

Russian Roulette (problem D, div-2; problem C, div-1). The problem's author is Alex_KPR

 

 

Let's solve the problem when value n is even. Obviously, if k = 1 we should put a bullet at most right position. For example, choose n = 8 and our answer string will be:

.......X

Let's find probability of winning at this situation. We will write zeros at losing positions and ones at winning positions:

10101010

The simple idea is to put every next bullet for non-dropping down our winning chance as long as we can. After that we should put bullets in lexicographically order with growing value of k. Look for the answer for another k's with n = 8:

.....X.X
...X.X.X
.X.X.X.X
.X.X.XXX
.X.XXXXX
.XXXXXXX
XXXXXXXX

When n is odd our reasoning will be the same with a little bit difference at the beginning. Look at the answer with n = 9 and k = 1::

........X
010101010

We may put second bullet as at even case. But there is exists another way, we may put our bullet at 1st position and turn left the cylinder, look here:

X.......X => .......XX
010101010    101010100

Obvioulsy probability of winning was not changed but answer made better. Next steps of putting are equal to even case:

.....X.XX
...X.X.XX
.X.X.X.XX
.X.X.XXXX
.X.XXXXXX
.XXXXXXXX
XXXXXXXXX

There is no difficulties to give answers to queries.

 

Complexity is O(p).

 

 

Time to Raid Cowavans (problem E, div-2; problem D, div-1). The problem's author is Alex_KPR

 

 

Let's solve this problem by offline. Read all queries and sort them by increasing b. After that there are many effective solutions but I tell you a most simple of them. Look at two following algorithms:

1. For each (a, b)-query calculate the answer by the simple way:

for(int i = a; i < n; i += b)
  ans += a[i];

2. Fix the value of b and calculate DP for all possible values of a:

for(int i = n - 1; i >= 0; i--)
  if (i + b >= n)
    d[i] = a[i];
  else
    d[i] = d[i + b] + a[i];

Obvioulsy, the 1st algorithm is non-effective with little values of b and the 2nd algorithm is non-effecitve with very different values of b. Behold that it's impossible to generate the situation where all b's are so little and different simultaniously. There is a simple idea: we may solve the problem by 1st algo if values of b are so large (if they are greater than c) and solve by 2nd algo if values of b are so small (if they are less of equal to c).

We need to sort our queries because of no reason to calculate DP of any b more than once.

If we choose c equal to that we will get a complexity.

 


Complexity is .

 

 

Buying Sets  (problem E, div-1). The problem's author is winger

 

 

Translated by Borisp.

http://codeforces.me/blog/entry/2539

 




 


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

| Write comment?
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Buying Sets is really cool.
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
If codeforces want to face the world, why not just use the English only?
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I dont understand russian...Why dont u post it in english or atleast in both languages:(

13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
and what about the many who dont understand Russian. English is the standard language accepted all over the world.That's why I told that versions of both languages should be written.
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I've answered to "why not just use the English ONLY?", not to you.
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      No..Its a serious thing ,,If questions are asked in both languages then why not give solutions as well in both languages
13 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Wow I really like your editorial style (grey tables, complexity at the end of task's tutorial).
It would be great to:

1 - Make this style standard for every round (maybe automated: the author should only fill in a "form")
2 - Write complexity in this form: "Time: O(1) - Space: O(1)"

UPD: Another idea: wouldn't be fantastic if editorial pages are structured like a wiki? With the possibility to edit (most likely to translate) the text to all users? Maybe only to "trusted" users? (something like problem tags)
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
nice tutorial. Thanks :)
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Does the last one will be translated too? :)
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice tutorial.
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why the complexity for Time to Raid Cowavans (Div1-D) is O(P * sqrt(N))? I'm new to this complexity analysis stuff

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

    Because we use 1-st method only for queries where B >= sqrt(N), so each query runs in O(sqrt(N)) time. 2-nd method works O(n) time for initializing array d, and O(1) to answer each query. We don't need more than sqrt(N) initializations, because we use 2-nd method only for groups of queries where B < sqrt(N). Total complexity is O(sqrt(N) * p1 + sqrt(N) * N + p2) = O(sqrt(N) * max(N, P)). p1 — number of queries where B >= sqrt(N), and p2 == p - p1.

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

      Thanks for the detailed explanation!

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

      Exactly, so there is a mistake in the solution where they say the complexity is O(sqrt(n) * p). It's actually O(sqrt(n) * max(n, p).