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

Автор Dalgerok, история, 6 лет назад, По-русски

Привет, Codeforces!

Codeforces Round #553 (Div. 2) состоится в Apr/18/2019 18:35 (Moscow time). Раунд будет рейтинговым для участников из второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут участвовать в раунде вне конкурса.

Большое спасибо arsijo и KAN за координацию раунда, тестировщикам: Markellonchik (отдельное спасибо за помощь в подготовке одной из задач), mohammedehab2002, Jeel_Vaishnav, а также 300iq за идею и подготовку одной из задач, Aleks5d и isaf27 за её тестирование, и конечно же MikeMirzayanov за системы Codeforces и Polygon.

В этом раунде вы будете помогать жителям Королевства Кремляндии. Настоятельно рекомендую прочитать условия ВСЕХ задач (ну и конечно же попытаться решить их).

Удачи!

UPD: Разбалловка раунда: 500-750-1250-1750-2250-2750.

UPD: Разбор

UPD: Спасибо за ваше участие в этом раунде! Поздравляем победителей!

Div. 2

  1. square1001
  2. hitonanode
  3. jaguar1996
  4. Mofk_wont_2k8
  5. sansen
  • Проголосовать: нравится
  • +260
  • Проголосовать: не нравится

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

"...прочитать условия ВСЕХ задач". Задачи не будут отсортированы по сложности?

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

how much problems are required to solve in division 2 to get expert rating

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

Ok

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

Those feelings when you wait for the contests to read the tasks and not solve them

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

Sorry if my question is silly, will it be rated for Div3 participants as well?

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

6 problems?

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

Can div3 pupils improve their rating by solving A problem?

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

    Depends on how fast you are, where in pupil range you are, and of course how hard the tasks are, but generally I don't think so. You may try solving at least A and B, which I think in most case will give rating improvements.

    BTW. I don't think that there is a big gap between Div.2 AB and Div.3 AB. Difficulty gap between 2 different div2 contests are actually larger (in my opinion, but problem rating data also kina shows similar results.)

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

I strongly recommend you to read the statements of ALL tasks (and of course, try to solve them)

I have seen a similar thing here. I will read all the tasks only if you say so. :P

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

But still, any updates on 0 IQ Challenge?:)

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

I wish positive rating for every participant :)

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

i hope to got an expert grade after this contest!

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

Блиин, Андрей, вот ты флексишь...

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

How much should I solve 2 get specialist rating?

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

Will (Forethought Future Cup — Elimination Round) be a rated contest? Can any one tell me, please.

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

Expecting this round to be full of awesome questions with strong pretests!!!

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

Hear This before contest and you will RISE by 100

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

Score distribution?

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

No interactive problem today :(

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

No extra registration?

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

I am not able to submit my codes. I am getting an error message saying "You have already submitted the exact code before" even when I haven't made a single submission.

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

Solution for D?

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

    Sort by $$$(a_{i}-b_{i})$$$

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

      Got this algorithm right away, but pretest 12 wouldn't run fast enough with my Python code... Tweaked it for efficiency as much as I could, and eventually it got past 12 but gave me a time limit error on 13.

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

    Notice that $$$a_i(j-1)+b_i(n-j)=j(a_i-b_i) + n b_i - a_i$$$. So, what matters is the value $$$a_i - b_i$$$.

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

    Dissatisfaction be rewritten as $$$j(a_i-b_i)+b_in-a_i$$$. Thus, we are trying to order $$$i$$$'s to minimize the sum of $$$j(a_i-b_i)$$$. Just sort them in decreasing order of $$$a_i-b_i$$$ and that should be the minimum. You can use an exchange argument to prove it.

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

For contests like these, you should get my script which sorts problems by number of submissions :)

Here

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

Can someone give me a hint on D?

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

Nice problems!

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

Any hint for E?

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

    Hint: What's the formula for number of components in a forest?

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

    First Compress the array by merging consecutive indices with same value in one component.

    Consider $$$dp[r] = \sum_{l = 1}^{r} f(l, r) $$$.

    Now, we have $$$dp[r] = (\text{number of elements with value r}) * r + dp[i - 1] - \text{number of edges that occur when we add elements with value r} $$$.

    the last term can be found by going through elements with value r, and checking its neighbours, If the neighbour's value is less than r, say x, it means for l <= x there will be an added edge. hence you add x to the last term in dp.

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

    Let's consider the starting of any component. Let it start at position i. Now, this is a starting position iff a[i — 1] does not belong to the range [l, r] and a[i] belongs to the range [l, r]. So we'll calculate the number of ranges [l, r] s.t. a[i] is inside this range and a[i — 1] is outside this range. The sum of the number of possible ranges over all i will give you the answer.

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

Hacks for A and B?

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

    I did one successful hacking attempt in B, and the testcase was:

    2 2 // H, W
    8 9 // A[1][1], A[1][2]
    8 8 // A[2][1], A[2][2]
    

    The only possible answer is TAK: C = [2, 1], but I found a submission which is assuming that $$$C$$$ is non-decreasing, so I could hack this solution.

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

what's about test 4 in C?

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

My submission for the 1st question is showing correct answer when i am running it on online compilers but on codeforces it is showing a different output and thus a wrong answer

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

strictly greater than zero or greater than zero, same things?

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

Got wrecked on problem C because of double precision in C++. I used double everywhere but when I switch to long double it gives another result. Both results are remarkably close to the expected answer on pretest 3. Can someone help me on this one ?

On pretest 3:
- Expected answer: 761141116
- Answer I get using double everywhere: 761034963
- Answer I get using long double everywhere: 761141203

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

    Why are you using doubles? Just use ints/long longs and modulo 1e9+7 as you go.

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

      I added the results by "chunks" like it was explained in the problem, so the chunks could get over the maximum long long value in C++

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

    You should not be using floating point numbers in a problem like this, where the exact answer can be found using integers.

    Solution: It is enough to calculate the sum of values in the range [1..M], because then the sum of values in the range [L..R] can be found doing a subtraction. To find it, we can recreate the process in which numbers are written in the blackboard to find how many odd and even numbers where added. Something like this:

    int to_add=1, remaining=M, numodd=0, numeven=0;
    while (M > 0) { // Complexity log(M) because you are substracting powers of 2
      if (remaining >= to_add) then
        sum to numodd or numeven;
      else
        put the rest in numodd or numeven;
      to_add*=2;
    }
    

    Once you know how many odd and even numbers are the in the black board, you can calculate two sums of the form 1+3+5+... and 2+4+6..., which are easy arithmetic sums (use a formula). In addition, remember that you must perform the operations modulo 10^9+7.

    Hope it helps.

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

      Thanks for the answer. I basically tried this implementation, but I thought that sum_to_numodd could exceed the maximum long long value if r is very big. Looks like I was wrong

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

        Well, think about it. The number r fits in a long long, and r = num_odd+num_even (all positive), so those fit as well.

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

          I'm afraid I don't understand. Surely r fits in a long long, but the sum of all even integers from 2 to r doesn't. That's why I think I needed double

          edit: well it turns out I have not done your implementation. Sorry for the misunderstanding

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

            Ok, fine then.

            Just to clarify in case someone else is also confused: num_odd is the number of odd numbers written in the board, not their sum. Their sum can be easily calculated using the formula for the sum of an arithmetic progression.

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

After reading B:

Me: OK, randomized algo should work

Inner Me: But there's a possibility it will fail

Me: Very low though

Inner Me: So, you are saying you never had something happened to you that was totally unexpected?

Me: Ok Ok. I will write a dp solution.

Conclusion: Got Hacked 2 minutes before the end of the contest. Then resubmitted a randomized solution anyway because there was not enough time for debugging

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

Approach for E ?

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

    I haven't solved it But I have some idea with stack、、wait for help too.

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

    Number of connected components $$$f(l, r) = 1 + (\text{number of cut edges}) - (\text{number of cut vertices})$$$

    You can calculate total number of cut edges and cut vertices in $$$O(n)$$$ each.

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

      thx

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

      can you please elaborate a little more?

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

        $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r) = \sum_{l=1}^{n} \sum_{r=l}^{n} (1 + (\text{number of cut edges}) - (\text{number of cut vertices}))$$$ $$$ = \frac{n(n+1)}{2} + \sum_{l=1}^{n} \sum_{r=l}^{n} ((\text{number of cut edges}) - (\text{number of cut vertices}))$$$ $$$ = \frac{n(n+1)}{2} + \sum_{\text{for each edge}} (\text{how many cut occurred on this edge?}) - \sum_{\text{for each vertex}} (\text{how many cut occurred on this vertex?})$$$

        Let $$$p = \text{min}(a_{i}, a_{i+1}), q = \text{max}(a_{i}, a_{i+1})$$$

        When $$$p \lt l$$$ or $$$r \lt q$$$ then the edge will be cut.

        Cut count of edge $$$i$$$ ~ $$$i+1$$$ is equivalent to $$$\frac{1}{2}((n-p)(n-p+1) + (q-1)q - (q-p-1)(q-p))$$$

        When $$$l \le r \lt a_{i}$$$ or $$$a_{i} \lt l \le r$$$ then the vertex will be cut.

        Cut count of vertex $$$i$$$ is equivalent to $$$\frac{1}{2}((a_{i}(a_{i}-1) + (n-a_{i})(n-a_{i}+1))$$$

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

          A simpler way of thinking about this problem: for each element a[i] count the number of ways to choose (l, r), such that a[i] is the last element in its component.

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

          if n=3 S(l=1 to 3)S(r=l to 3)= 1+2+3+2+3+3 How you derive n*(n+1)/2 If im wrong, correct me.

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

            $$$\sum_{l=1}^{n} \sum_{r=l}^{n} 1 = \sum_{l=1}^{n} (n-l+1) = n^{2} - \frac{1}{2}n(n+1) + n = \frac{n(n+1)}{2}$$$

            It's $$$1$$$, not $$$l$$$.

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

Any ideas about Test Case 8 in problem B?

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

very poor pretests

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

How to solve div2 B? what I did is that I maintained a cnt[] array and I didn't registered a number if is has been entered more than once. After this I took maximum element from each row and computed the answer. (I now know this approach is wrong) Any additions here?

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

    The idea look like dp

    dp[510][1024]

    dp[i][j] means The preceding i-line scheme for forming number “j”

    and dp[510][1023] can be optimized to dp[1024]

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

    Basically if a row contains at least two different numbers then there is a solution. If not any row contains two differents numbers, then just compute bitwise xor of a_(i,1) for i in range (0,n). If it's 0 then the answer is NIE, else you have your solution

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

    observation: if a != b, a ^ b > 0 (in this problem i used bruteforce).

    fix a row that has > 1 unique value (if there's any, but if none than you can pick any row).

    let k be the fixed row, after that you xor any value of a[i][0] excluding that row (that is a[0][0] ^ a[1][0] ^ ... ^ a[n — 1][0] ^ a[k][0]), let the value val.

    now you try all possible value x in this row k, if any val ^ x > 0, then you found the answer (n — 1 column 1 and 1 column in the fixed row).

    My submission: 52983517

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

    Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

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

Какой крутой больше бы таких ) ) ))) )) ) . . . . . . . . . . . .

. . . .

. .

( нет)

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

Any tips for B?

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

    If x is not y, then (x xor a) is not (y xor a).

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

    Randomly assign one number from each row. If the xor of all the assigned numbers is greater than 0,the problem ends there, else changing any one number among the chosen ones will change the xor. Try replacing each number in the matrix and when the xor is not equal to zero, that's one solution

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

    Well, you can consider each bit separately (there are $$$\leqslant 10$$$ bits). Now for $$$\operatorname{xor}$$$ to be non-zero you need an odd number of $$$1$$$'s. If the answer is 'yes' for at least one bit, then you have found a solution.

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

    Look at it as a dynamic programming problem. N <= 500, A_{i,j} <= 1023 Try them all and save the answer.

    Spoiler - dp states

    I don' t know how to use latex or markdown in comments, sorry for bad formatting.

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

    Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

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

What is the difference between greater than zero & strictly greater than zero ?

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

My solution for pE was :

First, calculate the numbers of the interval that each vertex will leave in the tree.

Second, minus the numbers of the interval for each pair (i,i+1) that there is an edge between them.

	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ans += a[i]*(n-a[i]+1);
	}
	for(int i = 1; i < n; i++){
		int mn = min(a[i],a[i+1]),mx = max(a[i],a[i+1]);
		ans -= mn*(n-mx+1);
	}
»
6 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Very very weak pretests on problem B.

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

    Could I add another "very"?

    My solution was 'sorting' the array and I was printing the modified indices and somehow that passed the pretests. In, normal occasions this solution should not even pass the samples.

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

How to solve E ?

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

Что то мне подсказывает, что задачу Б придумал 300iq...

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

One of the worst contests IMO. Very Unbalanced.

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

    Agree that they should have swapped C and D instead, but I think many of the problems require nice insight (like B, D and E).

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

      I think this contest was better for the higher rated participants in Div 2. But for people like me and below, it was hard to get that insight.

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

Ok, i don't want to be "that guy", but someone has to say it. I think that there were at least 2 coders who participated in this contest from the same account. And yes, i am referring to the user square1001. Time of submissions B and D are < 3 min , and between C and E is only 5 min. While i think that it is possible for someone to get the idea for them in a few minutes + reading the statement, i really doubt that they can code like this. And anyway, if you are that good, why take order B,D,C,E? Why not straight E,D,C,B? Also, coding styles seems to differ, so yeah, definitely something to look into, beloved admins.

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

    Please do not doubt — I am pretty surprised and happy that I won this round, and I was lucky that ecnerwala participated 30 minutes after the contest begins (if he participated from first, I think I lost).

    So, why did I take order B, D, C, E, A, F? I did pretty strategical.

    - First, opened problem B because I thought that opening problem B is lighter for servers than opening problem A. Then solved in ~3 minutes. It was not so difficult.
    - Second, opened problem C. But updating standings every ten seconds, I found out that problem D is already solved by someone! Hence, I immediately moved to problem D. I have came up with the solution in ~15 seconds, and the implementation was easy, so I solved in like ~2.5 minutes.
    - Then, re-thought problem C. Implementation was not so difficult, but my code bugged so it took ~6 minutes to solve.
    - In this time, the solver of E existed, so I moved to problem E. I had came up with the idea of "we should only care about difference in position $$$i$$$ and $$$i+1$$$ (+ two sides)", 1 seconds after I read the problem statement completely. The implementation was easy, so I could solve in 5 minutes.
    - Then, I moved A and solved easily. I had a pretty difficult time in solving F, because my matrix library is really slow (but the TL is 1 second), so I coded without using own library.

    I am very happy to win in such contest, in contrast to last contest taking 30 minutes in easy Div.2 B.

    P.S. You said that the coding style differs. What pair of problems are you pointing?

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

    I think code for D can be written in 1 min. And if you get the idea straight then it's an easy problem. Just read A. Statement and so many conditions, but still people have submitted in <3 min. Where i found A hard than D to code and understand. So writing code in 2-3 min for D is fine. Even problem E is too easier, if you know the logic. Just count of cut edges and cut vertices. Thinking may take 3-4 minutes. But code can be definitely written in 1 min. So I don't see any kind of cheating. You just go through other good coders' submissions, most of them have solved D, E in <= 5 min.

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

Got my first successfully hack and first system test failed on PB lol

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

What was your approach on last problem F?

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

    You can change the problem into weighted graph that has $$$4Hn$$$ vertices and up to $$$16 \times 4Hn$$$ vertices. Use binary jump (I don't exactly know the formal name of these kind of techniques) to calculate after $$$k$$$ moves in this graph.

    For your information, $$$nHr = n+r-1Cr$$$.

    I couldn't code my idea in last 20 minutes.

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

    not)) this is just boolshit))

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

    Let $$$z$$$ be the number of zeroes in the array. Consider the block of first $$$z$$$ bits: array is sorted iff it's all zero.

    Let $$$dp[i][u]$$$ be the probabilty that after $$$i$$$ steps we will have $$$u$$$ ones in the first $$$z$$$ bits. Then the answer will be $$$dp[k][0]$$$.

    Starting from $$$dp[i][u]$$$ there are three possibilities after the next step:

    • $$$u$$$ didn't change. Either we swapped something inside a block (there are $$$z \cdot (z - 1) / 2 + (n - z) \cdot (n - z - 1) / 2$$$ ways to do that), or we took same bits from different blocks: $$$u \cdot (n - z - u)$$$ ways to take two ones and $$$(z - u) \cdot u$$$ ways to take two zeroes.

    • $$$u$$$ increased by one. This can only happen if we took a $$$0$$$ from the first block and a $$$1$$$ from the second. There are $$$(z - u) \cdot (n - z - u)$$$ ways to do that.

    • $$$u$$$ decreased by one. Then we took $$$1$$$ from the first block and $$$0$$$ from the second. There are $$$u^2$$$ ways to do that.

    You can easily change the calculation of this DP to backward and then use matrix exponentiation.

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

how to solve B?

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

    Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

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

Such a fast editorial. Nice!!

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

Everything so fast...system testing + editorial + rating update...

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

Finally reached Candidate Master. It's sad that I submitted my contest proposal when I was Expert.. But whatever, I am speechless and so happy.

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

the problem C can scare, but in fact easy, the most difficult, thing is to keep track of the overflow, but the python decides everything))

https://codeforces.net/contest/1151/submission/52983378

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

Any hint about C ?

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

    If you want the whole solution, you can read the editorial. If you just want a hint, try to think of a formula by which you can solve this. It's similar to calculating the sum of the first n numbers, you just have to change it a little bit. :)

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

And the statement, I strongly recommend you to read the statements of ALL tasks (and of course, try to solve them) makes sense :P.

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

order of this contest should be A,D,C,B,E,F

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

I got a message that says my submission 52964771 coincides with sandrik398631‘s 52963443. They look really similar. But the problem A is too simple and my coding style is somewhat similar to sandrik398631. How can I appeal? All my submissions are skipped. Is it because of of this?

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

Can B solved by DP?

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

    Yes, B can be solved by DP. You can maintain a DP of size 510*1024, Here dp[i][j], i is the row number and j is the xor of numbers. So, all dp[i][j] values will be 1, if we can have xor j at an ith row, otherwise, the value will be 0. If the value is non zero, store the parent i.e. the element in (i-1)th row which xor with current element will give the xor j.

    Please look at code for more clear representation.

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

I have done following in problem C. Function calculates the sum in set till number n.

ev — next even sequence start od — next odd sequence start

then for each iteration, I calculate start and end of that sequence and calculate their sum by AP. It is giving wrong answer on test case 1 1e18. Is there an overflow ? I cannot find the bug in function calc.

code link

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

I noticed that a lot of D solution only sort using the key a-b, and I wonder why it is acceptable. Rearrangement of the dissatisfaction value $$$a_i(j-1) + b_i(n-j)$$$ gives $$$(j-1)(a_i-b_i) + b_i(n-1)$$$. To minimize the sum of all dissatisfaction, we would assign small $$$j$$$'s with large $$$(a_i-b_i)$$$, when the position of the student does not affect the term $$$b_i(n-1)$$$. What I does not understand is that when various students share the same $$$(a_i-b_i)$$$, the value of $$$b_i$$$ itself should make a difference. However, it doesn't seem to be the case. Am I missing something?

EDIT: After thinking more carefully, I realize that it really doesn't matter. Their dissatisfaction value would be different, but we are not trying to arrange them in order of dissatisfaction anyway.

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

Can someone make links to the editorial and to the contest announcement in the contest page? They do not exist for me here: https://codeforces.net/contest/1151