awoo's blog

Educational Codeforces Round 113 Editorial
By awoo, history, 8 months ago, translation, In English

1569A - Balanced Substring

Idea: BledDest

Tutorial
Solution (awoo)

1569B - Chess Tournament

Idea: BledDest

Tutorial
Solution (Neon)

1569C - Jury Meeting

Idea: BledDest

Tutorial
Solution (Neon)

1569D - Inconvenient Pairs

Idea: BledDest

Tutorial
Solution (adedalic)

1569E - Playoff Restoration

Idea: BledDest

Tutorial
Solution (BledDest)

1569F - Palindromic Hamiltonian Path

Idea: BledDest

Tutorial
Solution (awoo)
 
 
 
 
  • Vote: I like it
  • +108
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -48 Vote: I do not like it

Fastest editorial I've seen

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

nice contest =))

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Lesson learned: Don't use segment trees unless required.

(My segment tree implementation for D gave TLE on system testing.)

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

    Interesting. I used segment trees and maps as well, and the highest runtime was ~1 second.
    My submission 128269298

    → Reply
»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

code and explanation for problem D

Spoiler
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this problem about finding points (in pairs) that lie on either vertical lines, or horizontal lines, because only if 2 points are on vertical lines (no horizontal line in any of them is crossing them), then only its a inconvinient pair.

    Am i right?

    → Reply
»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I am facing some difficulty in understanding the equation in Problem C: $$$A_n^{n-k-1} = \frac{n!}{(k+1)!}$$$ What is $$$A$$$ here and how did we get $$$\frac{n!}{(k+1)!}$$$?

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

    $$$A_x^y$$$ is the number of ordered ways to choose exactly $$$y$$$ different objects from $$$x$$$. So, it's like a binomial coefficient $$${x}\choose{y}$$$, but with also considering the order in which we choose the object. Hence the formula for $$$A_x^y$$$ is $$${{x}\choose{y}} \cdot y! = \frac{x!}{(x-y)!}$$$: there are $$${x}\choose{y}$$$ ways to choose exactly $$$y$$$ objects out of $$$x$$$, and $$$y!$$$ ways to order them.

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

      Okay, so it's a permutation. Thanks for your help ^_^ !

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      PLEASE DISREGARD THIS COMMENT.

      Hi, how do you go from $$$A_n^{n-k-1}$$$ to this $$$\frac{n!}{(k+1)!}$$$? I would've thought the denominator to be (n-k-1)!. What am I missing here? Thank you.

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

      what is the error in the bellow analogy of problem C

      let the largest element be x and second largest element be y = x-1;

      if we fix the first position for x and and fix any position for y after it ,then we have (n-2) remaining element. Thus for this elements we have permutation (n-2)! and for y we can have (n-1) different position which are after x. so in total we have (n-2)!*(n-1) different good permutation when x is in the first position . and when x is in the second position then we have (n-2)!*(n-2) different permutation. So the math goes like this: (n-2)!*(n-3) , (n-2)!*(n-4) and so on.

      if we do the math : (n-2)!*(n-1) + (n-2)!*(n-2) + .... + (n-2)! = (n-2)!* ( (n-1)*n/2) but surely it isnt give the correct answer.

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

        I thought of a similar line but there's a problem with that. First, there can be multiple occurrences of y as well so we cannot simply write (n-2)! for the remaining. Secondly, there can be multiple occurrences of x as well and in that case, the answer will be n!. I tried handling these 2 cases but it became very complex. The editorial's approach is quite simpler than that.

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

      why to select n-k-1 from n we know which elements are n-k-1( n-k-1 elements are those which are not equal to ax or ax-1,where ax is the maximum element);

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is like considering the positions; instead of the elements. There are in total n positions. We wish to pick n-k-1 positions among them for the n-k-1 elements. There will be k+1 gaps after that. The last gap is fixed for the max element. The rest of the k elements goes k! ways into the rest of k gaps. I was also confused at first. Hope this helps.

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

    nPr formula is n!/(n-r)! where nPr represents permutating r numbers in n places. It is basically n p (n-k-1).

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

      is it true? nPr= rAn ? bcoz n should be greater than r.

      → Reply
»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Problem C : if (cmx == 1) ans = (ans — sub + MOD) % MOD; I don't know why we need plus MOD. I thought we just need : ans = ( ans — sub ) % MOD Thanks for someone explain this (^^)

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

    I think when $$$(ans-sub)$$$ is negative, (ans-sub)%mod will also be negative. In that case, the correct answer should be mod-(ans-sub) which could be better written as (ans-sub+mod)%mod (handles both positive and negative cases).

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

    It's because ans and sub are both %MOD, and if (ans%MOD — sub%MOD) < 0, so ( ans — sub ) % MOD will be < 0 too, that's because the % of negative numbers is also negative.

    for example, if MOD = 1e9+7, sub = 5 and ans = 1e9 + 8 (but in your code ans = 1, because you do ans%= MOD): ans = (1 — 5)%MOD = -4%MOD = -4

    But if you add MOD this never you be negative, because sub < MOD.

    I hope you understood and sorry for my bad english, I'm not fluent.

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

      I get that you are doing this because ans-sub can be negative but how does MOD+(ans-sub) give the right answer when ans-sub is negative. Is this a property of MOD?

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

        The "taking value modulo MOD" operation basically tells you the distance between your number and the previous number that divides MOD. So in case of negative numbers (in range (-MOD; 0)) you need to find the distance between -MOD and your number. If you shift both values by adding MOD it becomes the distance between 0 and (your number + MOD) which is of course (your number + MOD).

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

    By the way, answer can be simplified to n! * k / (k+1). That way you don't need to subtract modulo MOD :)

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

    I can't understand why we have to do this? Why can't we just do ans-(ans/(k+1))

    Moreover, I cannot understand the meaning of this line What's happening here

    Spoiler
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it -7 Vote: I do not like it

      You can't just divide $$$n!$$$ by $$$k+1$$$ because of here $$$n!$$$ is actually modulo of $$$n!$$$, so either don't include $$$k+1$$$ while calculating $$$n!/(k+1)$$$ or use multiplicative modular inverse of $$$k+1$$$ for division. Hope this helps you.

      → Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

In problem C my approach giving the wrong answer on test 2 but I couldn't understand why it is giving this error.

My Solution
Code

I tried to explain it well. I hope you got it and you can help me.

UPD: I added accepted solution so you can check my solution to understand the problem.

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's because of this int x = (fact(n) / fact(mp[maxi] + mp[maxi-1])) % mod;

    fact(n) is divisible by fact(mp[maxi] + mp[maxi-1] if you don't use mod, but with mod it doesn't, for example:

    16 is divisible by 8 but if i use mod 3 (16%3 = 1 and 8%3 = 2): 1 isn't divisible by 2

    To fix this we can use module inverse, you can see it here or here

    I hope you understood and sorry for my bad english.

    upt: I don't know if the rest of your solution is correct

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

      Thanks for your answer I got it. I didn't consider errors about mods.

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A you can use two pointers.

Spoiler
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Is it worth ?

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

      The first idea that came to me was to use two pointers. We need to shift the pointers until we find the desired substring, so we find the longest balanced substring in $$$O(n)$$$. This algorithm is not the simplest one, but why not give it a try?

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

    There are 4 methods for this question. 1. O(n) — simple traversal as described in editorial. 2. O(n^2) — brute force — generating all subarrays 3. O(n) — using two pointers. 4. O(n) — using traversal + map used to store sum till particular index

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

      What about finding count of 'a' and 'b' for each range using segment/fenwick trees ? Isn't that useful ?

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a different implementation for E , I am traversing on 1 match per function call by finding the people who haven't lost yet . It was giving TLE until I figured out ( yes figured out , because I didn't Google it ) how to traverse on Only set bits of a number in a given range ( range of bits ) . My submission

→ Reply
»
8 months ago, # |
  Vote: I like it +17 Vote: I do not like it

I think there exists a method for question D that is a little faster than the tutorial. The method used in the tutorial is to enumerate points, but I think it would be faster to enumerate edges. We divide the points into two groups, on x and on y, and discard the ones that satisfy both, since they cannot be composed. This way a pointer can be used to model the points that are between the two edges. Here the practice of my idea link

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Your codes for D/E/F are soo looooong

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Easy D approach -

Count no of points between each adjacent vertical lines. Let this count be n. Total no of pairs will be n*(n-1)/2. Subtract those pairs which lie on same horizontal line. This can be easily done using map.

Do the same for each adjacent horizontal lines

128428875

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, Can anybody please explain what does (1<<(1<<k))-1 represent in problem E??

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

    It means $$$2^{2^k}-1$$$. The << (bitwise shift) operator shifts the bits in the left number by the right number of times.

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

[deleted]

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

    Both $$$m$$$ and $$$n$$$ can be upto $$$2e5$$$. So yes, $$$O(mn)$$$ will exceed both memory and time limits.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi I was upsolving the C problem, can someone tell me why this wont pass the second test case? Thanks in advanced! my solution

→ Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi The solution shared from problem A

for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			print(i + 1, i + 2)
			break
	else:
		print(-1, -1)

Does it produce the output as shown in https://codeforces.com/contest/1569/problem/A ?

I am getting the output as

-1 -1
1 2
1 2
1 2

instead of 

-1 -1
1 6
3 6
2 5

Am i missing something?

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

Thanx for the editorial. I'm practicing now and I think i've misunderstood the logic of the tutorial for problem B. why the answer is "NO" if there are only tow players of the second type? like the following test:

n : 2
s : 22
answer is NO
but I think it could be as follows:
X+
+X

there are tow matches here, in the first one player one can win, and in the other match player tow can win, and then they are both pleased. could anyone explain it for me please.

my submission 129265572 in my submission, I replaced each player of the second type who win at least 1 match by character '0', and a player of the second type win a single matchm and this when he face a player whose value is not '1'.

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

    They cannot both win against each other. If one wins, the other automatically loses

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with my solution for problem C. So I came up with the same idea as the solution that a nice permutation must have at least 1 pair of i, j that i < j, a[i] is the largest number of the array and a[j] = a[i] — 1. I will call the largest number M. So using that, I will choose 2 position for M and M-1 , so there will be n*(n-1)/2 ways to place M and M-1. Suppose there are k number equal to M-1, there will be k*n*(n-1)/2 such ways. The remaining element can be placed anywhere so there will be (n-2)! ways. So in total there will be k*n*(n-1)/2*(n-2)! pair of nice permutation. But this formula gives the wrong answer for the 4th example test. I haven't known what is wrong with my solution yet so I hope u guys will help me with it. Thanks in advance!

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

There is a typo in the last line of paragraph 5, 1569D. strret->street :D @awoo

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, this line of code if (cmx == 1) ans = (ans - sub + MOD) % MOD; Why do we use mod like this: (.. + MOD % MOD)? We already calculated 'ans' and 'sub' under MOD, why do we use it again in the if statement?

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

    you need to +MOD because ans-sub may be a negative number , you need to %MOD because if ans-sub is non-negative , the former +MOD will give a value greater than ( or equal to ) MOD so you have to modulo again

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone identify the error in the bellow analogy of problem C

let the largest element be x and second largest element be y = x-1;

if we fix the first position for x and and fix any position for y after it ,then we have (n-2) remaining element. Thus for this elements we have permutation (n-2)! and for y we can have (n-1) different position which are after x. so in total we have (n-2)!*(n-1) different good permutation when x is in the first position . and when x is in the second position then we have (n-2)!*(n-2) different permutation. So the math goes like this: (n-2)!*(n-3) , (n-2)!*(n-4) and so on.

if we do the math : (n-2)!*(n-1) + (n-2)!*(n-2) + .... + (n-2)! = (n-2)!* ( (n-1)*n/2) but surely it isnt give the correct answer.

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

First problem can be solved with closedform solution

let x and y be weight resp. \begin{equation} x*3^n > y*2^n \newline 3^n/2^n > y/x \newline 1.5^n > y/x \end{equation} take log on both sides (with base 1.5) \begin{equation} log(1.5^n) > log(y/x) \end{equation} divide with log(1.5) to covert to base 1.5 \begin{equation} log(1.5^n)/log(1.5) > log(y/x)/log(1.5) \newline n > log(y/x)/log(1.5) \end{equation} now we can use this to compute n for any x and y. \begin{equation} n = floor(log(y/x)/log(1.5))+1 \end{equation}

→ Reply