Блог пользователя GreenGrape

Автор GreenGrape, 10 дней назад, По-русски,
Tutorial is loading...

Код: 35036267

Tutorial is loading...

Код: 35036334
Код (с прагмами и всем таким): 35036420

Tutorial is loading...

Код: 35036537

Tutorial is loading...

Код: 35053688

Tutorial is loading...

Код (динамика назад): 35036591
Код (динамика вперед): 35036674

Tutorial is loading...

Заметьте, что решения могут отличаться (и даже сильно) от написанного в разборе. Несмотря на это, основные идеи остаются теми же.

Код (GreenGrape): 35055945, 35055961
Код (KAN): 35055995
Код (x3n): 35055977

Разбор задач Codeforces Round #461 (Div. 2)
 
 
 
 
  • Проголосовать: нравится  
  • +93
  • Проголосовать: не нравится  

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks for the pretty early editorial!!!

»
10 дней назад, # |
Rev. 4   Проголосовать: нравится +21 Проголосовать: не нравится

In solution for problem E you wrote that time complexity is . Can you explain why ? Because for every n we are doing operations so I think it's more like

  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    It was possible to solve this problem faster — we can use standard trick and write ci using O(logci) nominals. Than complexity is .

    • »
      »
      »
      10 дней назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      Instead we can use two pointers
      Here To achieve previous complexity.

    • »
      »
      »
      10 дней назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      What do you mean by nominals?

      • »
        »
        »
        »
        9 дней назад, # ^ |
        Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

        Say c = 2n + k, where k < 2n. Then, these 2 are equivalent: choosing an element [0...c] times and choosing subsets of {20, 21...2n - 1, k + 1} where an element of subset is the number of times we choose the element.

        • »
          »
          »
          »
          »
          9 дней назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          So then we can compute the maximum value of min(dp[i—1][k] + X, W + k * B) + cost[i] * k, where k takes ci different values by splitting the interval into O(logci) intervals and taking max from each?

          Isn't that slower than the solution using a queue?

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    It's indeed as you said, but we can achieve the previously said complexity:

    We have dp[i][j] = max(dp[i][j], min(dp[i — 1][j — k] + X, W + (j — k) * B) — cost[i] * k). Let's get a new k = j — old k. Now, dp[i][j] = max(dp[i][j], min(dp[i — 1][k] + X, W + (k) * B) + cost[i] * (k — j)). We can take -cost[i] * j from inside to get

    dp[i][j] = -cost[i] * j + max(dp[i][j], min(dp[i — 1][k] + X, W + (k) * B) + cost[i] * k)

    Now we can use a Max_queue (push element, pop element as in a queue but answers what's the max inside the queue) to solve it in O(n * sum(birds)). Edit: since nothing inside the max/min depends on j

    Code: http://codeforces.com/contest/922/submission/35036545

  • »
    »
    8 дней назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    how to write the Mathematical formula like above?

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For 922B - Волшебный лес it is possible to write a bruteforce solution and just calculate answer for all possible input dynamically (O(n^3) with no optimisation). And then use pre-calculated answers in final submission.

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Very good contest ! The problems were all short and I enjoyed solving it immensely !

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

editorial of problem D is not available. How to solve Problem D.

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    Briefly: it is not hard to proof that cnts and cnth in (s[i] + s[j]) and in (s[j] + s[i]) equals. So answer will depend only on their relative location.

    We can sort all si with any n·logn sort algorithm, using ans(s[i] + s[j]) > ans(s[j] + s[i]) as compare function.

    Then build string t from sorted array s1, s2, ..., sn and output ans(t).

    http://codeforces.com/contest/922/submission/35039116

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In C,my brute force solution passes. i can't understand why,can anyone explain??

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    I think it means that condition m[n % i] == 1 becomes true at small k (why? theory of numbers/modules and etc.), else you stop iterating and output "Yes".

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When I did not read that in D and for an hour was trying to find the way to calculate dp for 107 birds :D

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There were so many hacks in problem A that I've thought this will be a regular unrated contest)))

»
10 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What is an official solution for problem F?

»
10 дней назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

What about the editorial of problem F? I want to know how to solve it, thank you!

»
10 дней назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I think this tournament was a good tournament! The problem was neat and fun. I have a question in Problem C I know that K is always above 43, but I do not know why. When K is 6t, 6t + 1, 6t + 2, 6t + 3, 6t + 4, we prove it all, but when K is 6t + 5, we can not prove it. Please help me! Please!

  • »
    »
    9 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    What's wrong with the solution of the editorial? Have you read it?

    If there are no repeated remainders in n % 1, n % 2, ..., n % 43, then it has to be the case that n % 1 = 0, n % 2 = 1, n % 3 = 2, ..., n % 43 = 42. This is equivalent to 1 | n + 1, 2 | n + 1, ..., 43 | n + 1. Therefore also LCM(1, 2, ..., 43) | n + 1, so 9419588158802421600 | n + 1. Therefore this is only possible if n >= 9419588158802421599.

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Thank you! I think my thinking was short on this part. Thank you so kindly.

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain me why in Magic Forest we have to include conditionals like x < j and i+j <= x (x = i ^ j) I understand why there's x > n but I can't figure out meaning of other conditionals.

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    • x < j: in that case the third number is smaller than the second, which is not allowed. The statement say that we have to count tripples (a, b, c) with a ≤ b ≤ c.
    • i + j < x: if this is the case than we don't have a triangle. E.g. try to draw a triangle with the side lengths 1, 1, and 3. Impossible. For more information: Existance of a triange
»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему в 922E — Птички, в асимптотике константа при втором слагаемом не превосходит 1/4? Если брать равномерное распределение птичек по деревьям у меня получается 1/2. Кол-во состояний динамики: (0 + S — S/n)/2 * n = Sn/2 — S/2, S = sum{Ci}. Из каждого делаем S/n переходов.

»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone tell, in question "C", how does complexity O(min(k,log(n)) is calculated? Is that an approximation(to achieve >43) or can we calculate maximum number through LCM in O(log(number)).

  • »
    »
    8 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Look up the sequence of lcm of first n integers on the Internet. (> 43) then lcm > 10^18.

    • »
      »
      »
      6 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That is okay, I know that LCM of first >43 integers will exceed 10^18. I was asking how the complexity has the log(n) factor. It means that we can calculate maximum integer whose LCM it is in O(log(n)).

»
9 дней назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Hello, GUYS!

Given a 2D array with each cell containing either 0 or 1, 0 meaning clean cell and 1 meaning dirty cell. We have a vacuum cleaner that starts at location (0,0) and we want to clean all the dirty cells. The robot can move up, down, left or right. each movement costs 1 points. How to clean all the cells with the min number of moves to minimize the score? Thank you very much

»
9 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Iam wondering why my brute-force solution for C got accepted .difficulty is like C<B<A

»
9 дней назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

I solved 922C in O(1) time. Although, the solution in the editorial seems straight forward, it didn't strike me during the contest! Solution link here.

»
9 дней назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

Can anyone please briefly explain the claim em - k <  = C.m1 / 3 that is made in the editorial for problem F.

»
8 дней назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

My solution drops out all i (starting from 2) if cntpairs(i) ≤ currentpairs - k.

I'm not sure if it is correct solution but it got AC: http://codeforces.com/contest/922/submission/35051349

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    my idea is like yours, but i'm not sure too, do u kown the reason now? can u tell me?

    I've found that a lot of people pass the problem but they don't know why it works.

»
8 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can any one provide the topdown dp solution for problem E?

»
8 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone elaborate C? I don't get how k is approximated to 43?

  • »
    »
    8 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    We are required to ensure that 1 divides (n+1) or 1 | n + 1, 2 | n + 1 and so on till k | n + 1 if the answer exists.

    So n + 1 has to be divisible by all of these. If for example n + 1 is divisble by 2 and 3, then it is also divisible by 6. Similarly we find for what kmin is the LCM(1 .. kmin) above our input limit. That gives us kmin = 43 when LCM is 19 or 20 digits long and answers don't work onwards for given input range

  • »
    »
    7 дней назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
»
8 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my code's complexity nlogn but still pass the problem c.the date of this context is amazing.

»
7 дней назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

My AC solution to F: http://codeforces.com/contest/922/submission/35125488

First I find the least m where e(m) >= k (like in the editorial). then I see how many edges should be removed to reach k, let their name be "excess". I followed a greedy approach where: while excess != 0, I remove the node from the interval [floor(m/2)+1, m] which has the greatest number of divisors and this number of divisors is <= excess, then subtract this number from excess. I know that the initial value of excess is O(m^(1/3)), but why does this greedy approach always succeed ?

  • »
    »
    7 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    For the cases where the number of primes in the interval [floor(m/2)+1, m] is >= excess it succeeds because the primes will always make it possible to reach k. but for the 16 possible counters mentioned in the editorial, why does this approach succeed ?

»
7 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

это работает на практически всех тестах, кроме некоторых случаев при m ≤ 120

"Неправильный ответ на тесте 123".

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Problem F, " You could've even written recursive bruteforce " is mentioned in the editorial. What would be the time complexity for the same ?

»
6 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone please explain why (n % i = i-1 : for all valid i) implies (n+1) % i = 0!

»
6 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution 35116450 for Problem F uses the idea in GreenGrape's 35055945 solution with only difference in that I did upper_bound over all numbers (not only over primes) and surprisingly it got AC. Fortunately it happened after the contest, to be fair with others. Seems like the acceptance criteria is much less intimidating than the problem statement looks.

»
6 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is wrong in my solution for D

http://codeforces.com/contest/922/submission/35161046

Please help

  • »
    »
    5 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    if (c1 == 0)
    {
    	val = INT_MAX;
    }
    

    I think this is the opposite of what you wanted to do? If c1 equals to 0, that means there are no 's', so it should go to the end of the final string.

    For example, the answer of 2 sh h

    should be 2 with the string "shh", but your code make it "hsh" so it prints 1 instead.

    Also, the answer could exceed the range of int, like in case of you have 50000 's' first then 50000 'h', which makes the answer 2.5 billion.

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can E be done recursively?

  • »
    »
    4 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    If the knapsack problem can be recursion, then it can also, obviously this is a knapsack problem

    If you're talking about a memory search, of course

    • »
      »
      »
      32 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how are u relating it with knapsack?

    • »
      »
      »
      32 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can u please tell in detail?

      • »
        »
        »
        »
        29 часов назад, # ^ |
        Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

        Let us solve this problem step by step.

        First, take the bird as an item, the number of birds is the amount of this item,the bag volume in this problem is not necessary to defined accurately, for your convenienc,you can take the sum(c) as the bag volume :D

        In this problem, the choice of birds is in a certain order.“Moving only forward",but in the knapsack,we actually consider each item in the order we specify.

        for(int i = 1; i <= n; ++i)   //consider each item in the order we specify. 
            for(int j = sumc; j >= a[i]; --j)
        

        right? So it doesn't affect us to solve this problem.

        Now, this problem turns into a multiple knapsack problem(I don't know the exact English name of this problem,but i think u can understand it , right?)

        Let's study how to solve this simple problem before adding other conditions,one of the ways is to dismantling the same items into different items (but their volume is the same, in this problem each bird's volume is 1,value is -cost[i]).

        The problem becomes a common knapsack problem.

        For instance,you have You have 6 A items and 4 B items,You can think of them as 10 things, but some things are the same volume and same value.

        By the way,The best way to split it is this:

        for example , you have 16 A items you can dismantle them into 1,2,4,8,1(2 ^ n ). You just have to think about the 5 pieces that are split up.

        Next, it's time to solve the problem completely.

        mana capacity indicates that the current backpack value cannot exceed this upper limit,and after putting the bird in the backpack, the value of the knapsack cannot be negative (mana exhausted).You need to solve the maximum volume of knapsack that can be filled up under this restriction( Of course, it can't exceed the total number of birds, that is sum (c).)

        my english not very well , if u cant understand,you can see my code http://codeforces.com/contest/922/submission/35191705

        Of course, in fact, just dp[maxc] is enough,A bit of redundancy in this code

        It's not recursively, and if you need it, I can write a code to show u

        Maybe some details I forgot to answer

»
4 дня назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

I accept the problem F just now, but i still don't kown why i can accept. first i find the min m satisfy e(m) >= k, then i choose the prime from 2 to m, Obviously, if I delete a prime number, it will reduce the M / P pair. If I delete the prime number, the total pair is still larger than k, and I'll delete it。

here is my mainly code (I didn't do any other extra judgment as solution.)

for(int i = 1; i <= m; ++i){
   if(prime[i] && sum - m/i >= k){
      ans[i] = false; sum -= m/i;
   }
   if(sum == k){
      break;
   }
}

i want to kown how to prove this idea is correct???

In addition, I want to know the details of the practice of recursion. Can anyone explain to me more about the principles and proof of F in more detail? I admit that I might be stupid: D