tnaveen's blog

Query on Problem C of Codeforces Round 992. How these two things are related?
By tnaveen, history, 3 weeks ago, In English

Problem link I found a pattern in this problem that, for any n. for example for n=7 and k=37. There are 2^(n-1) possible permutations with max value. Here, the nearest power of 2 equal to greater than 37 is 64. so, here lexicographically first 32 permutations 1st digit is 1. then for the next 16, 1st digit is 2 and for next 8, it is 3 and it goes on until 7. note that here the pattern is 32,16,8,4,2,1,1. 1 occurs two times. Here for 37, the first place is of 2 as 37<=32+16. Next 3 will occur 16/2 times. Here for k=37 we got the sequence 2,3..... as for 2nd place in the sequence, 3 occurs 8 times, it falls within 37, for the 3rd place in the sequence 4 occurs 4 times which is not satisfied, 5 occurs 2 times, which is satisfied . The sequence is 2,3,5..... so for the next place it goes on by doing half of the occurence of the previous element, when we find n as an element in the sequence, we can print all the absent elements of the permuation by reversing. Below are the permutations for n=7 and k=31 to k=43. 

1 6 7 5 4 3 2
1 7 6 5 4 3 2 
2 3 4 5 6 7 1 
2 3 4 5 7 6 1 
2 3 4 6 7 5 1 
2 3 4 7 6 5 1 
2 3 5 6 7 4 1 (37th)
2 3 5 7 6 4 1 
2 3 6 7 5 4 1 
2 3 7 6 5 4 1 
2 4 5 6 7 3 1 
2 4 5 7 6 3 1 
2 4 6 7 5 3 1 
2 4 7 6 5 3 1 
2 5 6 7 4 3 1 
2 5 7 6 4 3 1 
2 6 7 5 4 3 1 
2 7 6 5 4 3 1 
3 4 5 6 7 2 1 
3 4 5 7 6 2 1 
3 4 6 7 5 2 1 
3 4 7 6 5 2 1

Now, my question is how this is related to the editorial. In the editorial he simply took the binary representation and traversed in reverse and pushed in two different vectors and reversed the second vector. I couldnt relate this two approaches. If anyone can help, that would be great. My approach seemed correct but it was harder for me to implement in the contest.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tnaveen (previous revision, new revision, compare).

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

you can check my recent submission, it translates to same thing what the author did

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

Yes, I did the same Idea that you were speaking about and got ACC, but after the contest coz it was a bit hard, and then found that nearly no relation with the editorial


def solve():
    cur = 1
    last = 1
    powers = [0]
    cur_power = 0
    
    for _ in range(n - 1):
        if cur <= limit:
            cur += last
        powers.append(cur_power)
        cur_power += 1
        last *= 2
        

    powers = powers[::-1]
    arr = list(range(1, n + 1))
    marked = [0] * (n + 1)
    # print(arr)
    if cur >= k:
        # print("Not Yet")
        ans = []
        cur = 0
        for i in range(n):
            if powers[i] > log2_ceil(k):
                ans.append(arr[i])
                marked[arr[i]] = 1

            else:
                cur += power(2, powers[i], m)
                if cur >= k:
                    ans.append(arr[i])
                    marked[arr[i]] = 1
                    k -= (cur - power(2, powers[i], m))
                    cur = 0
            
            if arr[i] == n: break

        cur = n
        while cur > 0:
            if not marked[cur]:
                ans.append(cur)
            
            cur -= 1
            
        print(*ans)

    else:
        print(-1)
→ Reply