Igor_Parfenov's blog

By Igor_Parfenov, history, 10 days ago, translation, In English

2040A - Game of Division

Editorial
Solution C++
Solution Python

2040B - Paint a Strip

Editorial
Solution C++
Solution Python
Notes

2040C - Ordered Permutations

Editorial
Solution C++
Solution Python

2040D - Non Prime Tree

Editorial
Solution 1
Solution 2 (zap4eg)
Notes

2040E - Control of Randomness

Editorial
Solution
Solution (Notes)
Notes

2040F - Number of Cubes

Editorial
Solution Phi
Solution DP
  • Vote: I like it
  • +104
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it +49 Vote: I do not like it

can someone hack my submission for D, it works purely on hopes and dreams. 295631816

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +106 Vote: I do not like it

    who are we to ruin ones hopes and dreams?

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why all of you say “hopes and dreams”?what is the meaning of it?

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        undertale reference

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    My submission for D was literally hopes and dreams (I just chose random valid numbers until it was no longer possible.)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Same

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Hey, can you tell me how did this even come to your mind to generate random numbers and then brute forcing all the available remaining numbers, did you not think that it may give TLE? Just curious to know why so many people applied such a random approach of generating random numbers.

      • »
        »
        »
        »
        7 days ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        I was running out of time and couldn't think of a sophisticated way of doing it, and the number of composite numbers >> the number of prime numbers so I'd figured I'd probably be able to allocate a number within a few tries. As for why random numbers instead of just iterating starting from the next number, I thought that there was a decent chance that I'd end up with a bunch of allocated numbers close together that I would have to iterate over and waste time, so random numbers were probably safer than that option. Plus, I always have a soft spot for cool approaches and randomization definitely qualifies. :) In hindsight it was probably not necessary but it was fun nonetheless.

        Sorry for rambling, but that pretty much exactly represents my thought process within the contest.

        Edit: it turns out randomization was necessary for my approach. I submitted a solution without randomization, just using the fallback I had of iterating over all unused elements in order (using a set so it wasn't totally inefficient), and I TLE'd.

»
10 days ago, # |
  Vote: I like it +19 Vote: I do not like it

fast editorial

»
10 days ago, # |
Rev. 2   Vote: I like it -72 Vote: I do not like it

Problems like C add nothing to the knowledge of the participants. They just test IQ.

Also, it is exactly same as this problem: https://codeforces.me/contest/513/problem/B2

Edit: I understand that many of you had fun solving the problem. But there are several participants who just recognized the pattern for smaller n's and hoped it work for larger values of n as well. Isn't it unfair to the people who really come up with and proved their solution?

I mean the testers create randomized cases just to ensure that makeshift solutions do not pass and here anyone who recognized the "pattern" for n <= 6 could get an AC!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Is this the reason for so many ACs on C?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    the fact that it already exists is cringe and they should've checked for that. But I struggled on it for an hour, and when I managed to solve it, I think it really did add to my knowledge, and I think it's a great problem. I believe I learned a lot more from it than from D, where I literally just guessed the solution without proving it actually works

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is because you are one of the few people who solved it like it should be. Many participants just observed the pattern for small n's and hoped that it will work for bigger values of n as well. Something similar happened for D also.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well, not "hoped", but it's much easier to prove a pattern than spot a pattern without seeing the permutationa

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

      how to solve problem c? i could not understand the solution.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Nahh man,I think apart from the fact that it was an existing problem I felt that it was a nice constructive algorithm problem which didn't rely on prior facts or knowledge.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Agree 100%, really annoying that it was a previously done problem, since I had a lot of fun solving it (and it's probably the hardest problem I've ever solved, so I'm happy about that)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Me, the author, and the testers didn't know about this problem, and it didn't come up in my searches :( (maybe because the formula is an image...)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I feel that getting the permutation even after knowing the fact (which can be easily verified by a brute force), the construction isn't trivial. The editorial seems incomplete without it.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    welp that's the average div. 2 C unfortunately

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    i think C is a pretty cute problem Tbf, aside from the fact that it existed before the contest

    it felt much nicer solving C since i was able to see what was happening and wasn't making any guesses

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    They just test IQ

    If so, all constructive problems on arrays are testing IQ.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      to an extent, yes

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Isn't competitive programming a huge IQ test? If someone doesn't like IQ tests, I would advise against CP...

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think recognizing the pattern is a good thing. It takes skills to be able to recognize the pattern and take advantage of the pattern to solve the problem. Dynamic programming is also about recognizing the pattern.

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

    I had fun solving this task myself (after contest). But yes, I confirm, it's EXACTLY same.

    My solution for 513 B2

    And for this contest

    I didn't participated in round, so I don't care, it's rated or not. But rules should be for everybody. FYI Igor_Parfenov

»
10 days ago, # |
  Vote: I like it +4 Vote: I do not like it

oh wow, super fast editorial before system testing, thank you.

»
10 days ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for the really interesting problemset. It's satisfying to see that even E can be implemented so simply without need for advanced data structures.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

E can be solved offline in O(Q log^3 N) by using parallel binary search and HLD.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what techniques/knowledge is required for E? i am clueless on how to even begin solving it

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The easier solution to E does not need any of this. Naive O(NQlogN) works just fine.

      Under the constraints, this approch is only a little faster than the official one.

      This problem has the same general idea and requires this approach.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    isn't that a bit over kill?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can also solve in O(Q log N) with PST walking

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    No need for $$$\log^3$$$, you can get a simple offline $$$(N + Q) \log N$$$ using Fenwick trees: 295645729

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

everyone failed E because they misread the constraints

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    And almost everyone missed E because they were stuck in C and D.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruh I had no idea how to solve B.

Then I remembered, "If nothing makes your solution work, put it in a binary search" — me

So, I tried binary searching on how many of 1st type operations would be used.

And I got wa. But I will try to solve it using binary search

»
10 days ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Here is the 2e5 version of problem E for python. It passed the test, and run within 1s with randomly generated cases on my local machine.

295640041

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 days ago, # |
Rev. 4   Vote: I like it +15 Vote: I do not like it

My solution of D with the proof:

  1. Find the center of the tree, do dfs that starts from it.
  2. Sort all vertices by (depth, dfs_visit_time) descending order as $$$v_1, v_2, \cdots, v_n$$$.
  3. Assignment $$$a_{v_i} = 2 \times (i + 1)$$$ for $$$v_1, v_2, \cdots, v_{n-1}$$$,and $$$a_{v_n} = 2$$$.
  4. If there is a conflict that $$$v_1 (a_{v_1} = 4)$$$ is a neighbor of $$$v_n (a_{v_n} = 2)$$$,assignment $$$a_{v_1} = 1$$$.

Proof:

Lemma: Since we do dfs from the center, every layer has at least two vertices if the tree has two centers. Otherwise only the layer of the center has only one vertex.

$$$v_i$$$ must be not the neighbor of $$$v_{i+1}$$$ if they have same depth. In the case they have different depth, they can't be adjacent after the sort because the lemma (except $$$v_n$$$ when it's a center). So $$$v_1, v_2, \cdots, v_{n-1}$$$ must be a legal solution.

So we just need to care with $$$v_n (a_{v_n} = 2)$$$. It can only conflict with $$$v_1 (a_{v_1} = 4)$$$. If they are adjacdent, we just assignment $$$a_{v_1} = 1$$$ because $$$v_1$$$ is always a leaf and not about other vertices ($$$v_2, v_3, \cdots, v_{n-1}$$$).

Code: 295631636

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I think another solution used bipartite graph is more interesting, really make me amaze.

    Update: Sorry, it's like official solution 2.

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

B was nice!

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

ok i am dumb i forgot about last 1 after "1"

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

    Place 1s at indexes 1 and 4

    Fill the indexes 1 through 4

    Place 1 at index 10

    Fill the indexes 1 through 10 (This solves your second question)

    Place a 1 at index 20

    Fill the indexes through 1 through 20

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3 from 10: initial: 0000000000 after 1: 1000000000 after 2: 1001000000 query type 2: 1111000000 after 3: 1111000001 query type 2: 1111111111

    20 does the same steps up to there but adds one more initial (3 operations done): 11111111110000000000 after 4: 11111111110000000001 query type 2: 11111111111111111111

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this string: 1001000001 Where the flipped bit are those set using first operation. Now, you can flip the first two bits in between (because there are a total of 4 bits, 2 of which are 1, so the constraint ceil(4/2) >= 2 is satisfied). Then the string becomes: 1111000001 Now, just choose the first and the last bit; l=1, r=10, the constraint ceil(10/2) = 5 >= 5 is satisfied, so we can flip all other bits. Just do it iteratively and you have the solution.

»
10 days ago, # |
  Vote: I like it +14 Vote: I do not like it

E can be solved in O(n^2 + q). Link

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for giving the tutorial too fast like rocket :)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

dreams are illusion or future

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannt problem E be solved with $$$Q \le 10^5$$$ also.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you can precompute a 2d DP and answer all queries in O(1)

»
10 days ago, # |
  Vote: I like it +35 Vote: I do not like it

For problem D my solution simply chooses values randomly for each node of the tree in DFS order, repeating until the difference with the node's parent isn't prime.

This works because when $$$n$$$ is large enough, $$$n \, » \, \frac{n}{\ln n}$$$ (or even $$$\frac{2n}{\ln n}$$$), which means there's always a significant fraction of the remaining numbers that would result in a non-prime difference. During the contest I added some logic to potentially restart from scratch and re-randomize if needed for small $$$n$$$, but it seems like you don't even need that: 295643399

Another benefit of this solution is it will work for smaller bounds such as $$$1.5n$$$ instead of $$$2n$$$.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please further show why it will work?

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, i did the same but used bfs, and for some reason it is giving TLE 296790454

    can you please help?

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can't solve n = 3 with composite differences only (the only option is 4). You need to use 1 as a non-prime difference as well.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nice problems, finally reached pupil!

neat solution to problem C... I found the greedy strategy for problem C but couldn't find a way to implement it other than calculating 2^(n-2), which would not work with the constraints. sad that I could not solve it even after finding the correct logic ;(

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

[For problem C] I am trying to generate the permutation according to the bitwise representation of k. Could anyone please see what's the error?

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n, flag = 0;
        long long int k;
        cin>>n>>k;
        vector<int> a(n, 0);
        if((n<=60) && k>pow(2,n-1)) {
            cout<<"-1\n";
        }
        else {
            int L=0, R=n-1, shift=n-2, value =1;
            while(L<=R) {
                if(((k-1)>>shift)&1) {
                    a[R] = value;
                    ++value;
                    --shift;
                    --R;
                }
                else {
                    a[L] = value;
                    ++value;
                    --shift;
                    ++L;
                }
            }
            flag = 1;
        }
        if(flag) {
            for(int i=0;i<n;++i) {
                cout<<a[i]<<" ";
            }
            cout<<"\n";
        }

    }
}
»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey ladies and gentlemen, this is my code for verifying how the dynamics of the C's solution work https://www.ideone.com/fQB1zU

and following is the submission link of the AC verdict for the corresponding Que' https://codeforces.me/contest/2040/submission/295645589

hope you understand it, if not, ping me back freely!

»
10 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Alternative solution for problem E:

Let us solve the problem where $$$p=0$$$ for all queries. Consider two functions $$$A_v$$$ and $$$B_v$$$ where $$$A_v$$$ is the expected number of moves to reach $$$1$$$ if we are currently in $$$v$$$ and $$$i$$$ is odd and $$$B_v$$$ is the same as $$$A_v$$$ but $$$i$$$ is even. $$$A_1=B_1=0$$$, since we are already at $$$1$$$ so we require zero moves.

If $$$i$$$ is odd, then we move to the parent with probability $$$1$$$, hence $$$A_v=B_{\texttt{pr}}+1$$$, where $$$\texttt{pr}$$$ is the parent of $$$v$$$.

If $$$i$$$ is even, then we move to any neighbor vertex with the same probability, hence $$$B_v=\sum\limits_{u \in N(v)}\frac{A_u}{deg[v]}+1$$$. Let us simplify this formula as $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{A_u}{deg[v]} + 1$$$. Notice, that $$$A_u=B_{\texttt{v}}+1$$$ from the $$$A_v$$$ recurrence, hence $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{B_v+1}{deg[v]} + 1$$$ The sum does not depand on $$$u$$$ anymore, so we have $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\frac{deg[v]-1}{deg[v]}\cdot (B_v+1) + 1$$$.

Solving this equation for $$$B_v$$$ we have a formula $$$B_v=A_{\texttt{pr}}+2\cdot \texttt{deg}[v]-1$$$.

We have formulas for $$$A_v$$$ and $$$B_v$$$ that depend only on the parent of $$$v$$$, so can run a simple dfs to compute the values for all vertices. The answer for the query is $$$A_v$$$, since we start from the odd $$$i$$$.

But in the original problem we have some amount of coins. The solution doesn't change at all, we just add another parameter to our functions that responds to the number of coins we have, $$$A_{v,p}$$$ and $$$B_{v,p}$$$. The transitions are the same, but we can also spend a coin when updating $$$B_{v, p}$$$, so $$$B_{v, p}$$$ may be $$$A_{\texttt{pr}, p-1}+1$$$.

Precomputing $$$A_{v,p}$$$ and $$$B_{v,p}$$$ for all $$${v,p}$$$ takes us $$$O(n^2)$$$ and answering the queries $$$O(1)$$$.

Implementation: 295642233

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Back to pupil!!! Thanks for this contest.

Totally blanked out at C :(

»
10 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

C was tragic for me, I actually found the "left or right " construction, I just couldn't get it to work properly, i need to work on constructives

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Damn, in D I thought that 1 is considered to be a prime number...

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Hell nah. My master dreams are ruined by this fact. I almost went crazy not understanding why my solution wasn't working.

    I need to retire from cf to save my hair and eyes :)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am failing to understand E, if anyone could help me understand it in easier way. Thanks before hand

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

problem E: I thought to build a vector of expected values $$$d$$$, where $$$d_N$$$ is the expected number of moves from a node with $$$N$$$ neighbors to go up (towards vertex 1) of exactly one step, so the parent, when the current counter parity is even. So:

$$$d_N = \frac{1}{N} + \frac{N-1}{N} (2 + d_N)$$$

the first term is the case in which the robot is lucky and goes up, that takes 1 step with probability 1/N; the second one is the probability of going down to one of the $N-1$ below standing children, than going up (2 moves) and the expected value $$$d_N$$$ itself. So, at the end the expression for $$$d_N$$$ is:

$$$d_N = N\frac{2N-1}{N-1}$$$

But it is not correct. Can someone explain me why please?

UPD: the first equation is correct, the final computation is not. As harsha_.05_ sais:

$$$d_N = 2N - 1$$$
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    d[n] = 1 / N + (2 + d[n]) * (N - 1) / N;
    d[n] * N = 1 + (2 + d[n]) * (N - 1);
    d[n] * N = 1 + 2 * (N - 1) + d[n] * (N - 1);
    d[n] * (N - N + 1) = 2 * (N - 1) + 1;
    d[n] = 2 * N - 1;
    

    Your initial equal is correct. Somehow you must have done some mistake in calculation. I have used the same equation in my submission.

    295662501

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

On C I calculated the S(p) up to n = 8 to see the pattern. I did realize that the smaller numbers always ended up in one of the ends of the array and that they had a sort of logarithmic behaviour, like, the permutation changed based on powers of 2.

Though I had no idea how to enumerate them, and to realize afterwards that you can just decompose K into bits and just decide the position based on that is just crazy. Awesome problem, even if it costed me my Specialist.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    literally same, i found the pattern, not by proof, but in a sort way where i was like, the more big stuff on one side the better, this is probably right and we cant make both sides big for each number, and in a notes document i wrote: "case on dropping to the left or the right, left makes smaller, right makes bigger." however, when I went to check it against samples for "4 6" i considered binary 6 instead of binary 5, so it wasnt right, I gave up on the idea, bricked my mental, and failed the contest

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    295648314. Coding this is also simple.

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

For Problem C I printed set of all permutations and tried to recognize a pattern. But Had a very difficult time imaplementing it, and also totally overlook that n is large and I cant use 1<<(n-1). That was my first experience handling such tricky constraints... Really learned so much in this single problem!!!!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, I was just speaking about this point, but I think I handled it in a different way and yes I didn't have time to finish my work in the contest coz of this trick and another trick

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C in a different way, I just generated all of the permutations with the score of the maximum and the score of the maximum is the score of this permutation that you put the highest one in the middle then on its left the next maximum the on its right the next maximum and so on, so something like this will happen if n = 7

1 4 6 7 5 3 2

then this gave me this result when used n = 5

(1, 2, 3, 4, 5) (1, 2, 3, 5, 4) (1, 2, 4, 5, 3) (1, 2, 5, 4, 3) (1, 3, 4, 5, 2) (1, 3, 5, 4, 2) (1, 4, 5, 3, 2) (1, 5, 4, 3, 2) (2, 3, 4, 5, 1) (2, 3, 5, 4, 1) (2, 4, 5, 3, 1) (2, 5, 4, 3, 1) (3, 4, 5, 2, 1) (3, 5, 4, 2, 1) (4, 5, 3, 2, 1) (5, 4, 3, 2, 1)

and from here I saw they are being repeated by powers of 2 until they reach n

look at the first item in the first 8 places it is 1 and then the others will be 2 in the next 4 perms

and so on, so I coded this pattern

then any number less than n will be printed by just looping from n to 1 and add any not-added-yet numbers

My Submission

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E I can't figure out what is wrong with my approach. I see the editorial did something different, but I cam up with geometric distribution to solve it, and it gets till test case 4 and fails on the 138th query.

submission

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You have a problem with dp. When you have several paths to the state, you set the value from the last path. Instead, assign the minimum value.

    Change dp[u] = dp[v] + x to dp[u] = min(dp[u], dp[v] + x)

    Also, you don't need modulo here, as the answer is always $$$\le$$$ n.

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

      That worked, I was so close with my approach, instead of treating each movement as odd-even step, I just tracked the parity in the dp states, and the possible transitions based on the the current parity.

»
9 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Honestly i have no idea when my first time meet C but i suddenly realize that this is a similar question to this 1450D - Rating Compression 295345001 The key idea is the current minimum number is always occur in the side of the interval,for example let think about for n=4 how we can get the maximum answer?We can do greedily first which is put the large number at the first,the 2nd largest number at the second and so on we got 4,3,2,1,and after that what should we do next move?Let us think about what times 4 appear in subarray,[4] only right?Then what time for 3?[3],[4,3] right?Do you found the pattern 4 appear 1 times,3 appear 2 times,2 appear 3 times,1 appear 4 times,If you found this you already solve half of the problem.What is the usage of the previous observation?I found that when 4,3,2 and 1 appear [1,2,3,4] times respectively will give us maximum answer in otherword if the permutaion cannot give us the corresponding number appear times then this permutation will definitely is not a answer,for example [4,1,2,3],4 appear 1 times,2 appear 2 times ,3 appear 1 times and 1 appear 6 times,the appear for 4,3,2,1 is [1,1,2,6],obviously the 1 appear times from 4->6 and the total number times is a constant because its is the total number of possible subarray which is n*(n+1)/2 so now the problem become how we can make sure number appear times of our permutation is same as the optizimed appear times,we do it step by step,initially imagine you have n box there are lie in one line and set the current minimum number become 1,so in [1,n] what place should i place the 1 such that 1 will appear exactly the optimized times,the answer is in leftmost or rightmost,from the previous observation in n=4 1 should be appear 4 times so obviously according to our constructed method when n=5 1 also will appear 5 times in other word ,1 will appear n times in optimized answer,so why leftmost or rightmost will provided optimized answer?Assume that i place 1 at rightmost(same for leftmost) then it will be 1xxxxxxxxx...xxx(exactly n-1 x) and how many subarray will form by above array,just use a simple combination,it will be n right?Because the current empty box(does not place any number) is n-1 then will form (n-1)+1=n,so after place 1,2 is my new current minimum number and after i place 2 i have n-2 empty box,and let us recall what is the appear times of 2 we need?n-1 right,so n-2 empty box will form (n-2)+1,the +1 is because itself can also form a subarray,after this you can constructed the number step by step, and the complexity will become O(n) below is my submission 295604272

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why (1<<(x-2)) ? why not x-1 ? I dont understand this . can you explain this part why x-2 ?

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For example n=3,there will be 3 position we need to place.Initially we will have 3 emply box and current minimum number is 1 then we have 2 option to place 1 which is either left most or right most (1 or 3) so there is two ways,and after that our current minimum become 2 now we have 2 box ,when we have 2 box there only two way because when we put 2 at the 2nd box then 3 must in 3nd box or we put 2 at the 3nd box then 3 must in 2nd box,so when we left 2 box there is only 2 way,so ans=2*2 so you can see that when n=3 there is 2*2,similarly to n=4 there is 2*2*2,so if the current box left is x after i put the current minimum number there will be x-1 box and x-1 box will have 2*2*2...*2 (x-2)times according to the previous observation.

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

    Thanks a lot, can you also elaborate on how you calculated the k-th permutation?

    Edit: got it now

»
9 days ago, # |
  Vote: I like it -11 Vote: I do not like it

in E how can d[v]=2+1d+1⋅d[u]+dd+1⋅d[v], whence d[v]=d[u]+2⋅(x+1) i dont understand

»
9 days ago, # |
  Vote: I like it +10 Vote: I do not like it

In the Editorial of D:

$$$\text{We will write the values } n\cdot 2,n\cdot 2−1,n\cdot 2−2,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$

Maybe it is a mistake and should it be:

$$$\text{We will write the values } n\cdot 2,n\cdot 2−2,n\cdot 2−4,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest is quite standard. At first, when solving problems A and B, I thought there had to be something really tricky, but after reading the constraints, this is the first time I've found problems A and B to be this easy

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hi newbie here i just wanted to know about problem b lets consider n=5; now 1st operation change at 1st index 0 to 1 2nd operation change at 5th index 0 to 1 (5-1+1)/2 is 2 in programming so why the output is 3 instead of 2

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, could I check why in the first if block for C we must check for n <= 60? I'm unsure of the intuition behind it.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because for n>60 ,2^n will always be greater than k, so ans will always exist. So there is no need to compute 2^n for n>60 and also it will give integer overflow even in long long int.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Every element from 1 to n-1 will be having 2 choices, either start of array or end, the nth element has only 1 choice, so it is 2^n-1 permutations total, if k is greater than this then we must print -1, but since n is upto 2*10^5, if we just always try to left shift, we will deal with overflow. Since k is 10^12, if (n-1)>=40, choices will be always greater than whatever k is given, so you only need to check for lower n's

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am unable to understand the proof for the given construction in C, can somebody explain that? And even after building the construction I am unsure of how we are calculating the k-th permutation

Edit: got it now

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In B if n=11 and i make arr1=1 and then i make arr5=1 so for now two first type operations are needed and then i apply second type of operation(5/2<=2) and then applying in arr11=1 cant i get it in 3 operations only why the answer is 4 plz someone tell

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    $$$\lceil$$$ and $$$\rceil$$$ represent ceil operator, so $$$\lceil {5 \over 2} \rceil$$$ is $$$3$$$, not $$$2$$$.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It is a bad mistake to try do the problems while in car. Got so dizzy, i cannot even solve problem A :(

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is how I solved problem C. Initially, I made some observations:- How will i get the max S(p)? -> By making the contributions of smaller numbers the least possible. How will i do this? -> starting with the current smallest no(which initially is 1) i can prove that it has to be placed either on the extreme left or to the extreme right of the current empty array. This can subsequently be done for the next current smallest values, all follow the same thing.

So getting the kth permutation:- When will the ans not exist? -> when k > no of perm which gives the max value (2 ^ n-1); As k<=1e12, this is only when n-1<40.

Now for each number in the permutation, we have two possibilities either place it in the first or last of the empty array. When right? -> temp = (1LL<<(n — cursmallest — 1)) if(k>temp) then cursmallest will be at the last and simultaneously update k = k — temp;

Elsewhere cursmallest goes to the left position.

Implementation 295706641

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any way to look that test case like my code is giving wrong ans for test case 3 token 338 ........how can i find that particular testcase can anyone help

»
9 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I just greedily assigned the values to nodes in D using the fact that any difference between any consecutive non-prime numbers would always be <=2.Is this enough to prove that I would be using values <=2*n? cause at max I will just be skipping a single number per assignment.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Appear for the first time and couldn't solved single problem. but I am not gonna give up

»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

The Editorial of problem D contains a typo in my opinion. The second solution should have "n.2, (n-1).2, (n-2).2,..." instead of "n.2, n.2-1, n.2-2,...". Please verify this once Igor_Parfenov

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain C in more detail? i recognized the pattern but don't know how to generate the kth one. these are some first permutations for n = 5

permutations for n = 5

I might've missed some here...

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here are all the permutations that work for n = 5

    (1, 2, 3, 4, 5)
    (1, 2, 3, 5, 4)
    (1, 2, 4, 5, 3)
    (1, 2, 5, 4, 3)
    (1, 3, 4, 5, 2)
    (1, 3, 5, 4, 2)
    (1, 4, 5, 3, 2)
    (1, 5, 4, 3, 2)
    (2, 3, 4, 5, 1)
    (2, 3, 5, 4, 1)
    (2, 4, 5, 3, 1)
    (2, 5, 4, 3, 1)
    (3, 4, 5, 2, 1)
    (3, 5, 4, 2, 1)
    (4, 5, 3, 2, 1)
    (5, 4, 3, 2, 1)
    

    Here are a couple of observations that I made, bolding the ones that were fairly important

    • A reversed permuation has the same score as the original

    • An element can only appear in the final equation at most (max_element-n+1) times, e.g if the permutation was of length 5, 5 could appear at most once, 4 could appear at most 2 times, etc. Therefore, in order to ensure that the sum is maximized, an element must appear the maximum amount of times that it is able to.

    • the first element from the back will be fixed for 1 permutation, the second element from the back will be fixed for 1 turn, third element 2 turns, fourth element 4 turns, and fifth element 8 turns (with fixed meaning up to that point, it's in the same position that it would be if the permutation was sorted)

    • An element will be a prefix or a suffix of the elements up to that point, e.g in the case where n = 5, 4 could either appear before or after 5, so the possible values of that subarray are 4 5 or 5 4, then once we get to 3, it can be 3 4 5, 3 5 4, 4 5 3, 5 4 3

    • Whether the nth element from the back is at the start or end of the elements up to that point depends on if the modulo value of k by 2^n is greater or less than 2^(n-1) (if it's less than 2^(n-1), it should be added at the front, otherwise at the back.

    I hope this helped (sorry if it's hard to understand, I know I'm not the best at explaining)

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      really didn't understand the 5th point. i couldn't make the 4th observation but i had all the work done before that

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'll use the example of n = 5 and k = 9

        Let's start with an empty list (I used a deque in my code, but a list will work to show how it works)

        (I'll mention that I subtract 1 from k to perform the calculations, so k is equal to 8 in my calculations)

        Now let's iterate from 5 to 1 and add the elements to the list

        Since 5 is the first element from the back, we will check if k % 2^0 < 2^-1 (8 % 1 < 0.5). Since it's less than 0.5, we add it to the front, so the list is now [5]

        Now let's go to 4, and check if k % 2^1 < 2^0 (8 % 2 < 1). Since this is true, we add it to the front, and the list is now [4, 5]

        For 3, k % 2^2 < 2^1 (8 % 4 < 2) is true, so we add it to the front, and the list is now [3, 4, 5]

        For 2, k % 2^3 < 2^2 (8 % 8 < 4) is true, so we add it to the front, and the list is now [2, 3, 4, 5]

        For 1, k % 2^4 < 2^3 (8 % 16 < 8) is false, so we add it to the back, and the list is now [2, 3, 4, 5, 1]

        Our final list is [2, 3, 4, 5, 1]

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

    lets puts these numbers in boxes. last 2 numbers form a box whose min will be (n-1) last 3 numbers form a box whose min will be (n-2) and so on

    now observe that you can you can only switch position of number in front of this box and put this number at the end of the box. like this:

    [1, [2 , [3 ,[4 ,[5]]]]] here you can switch 4 like: [1, [2 , [3 ,[[5], 4 ]]]] and switch 3 like: [1, [2 , [[[5], 4 ] ,3 ]]]

    this are the only ways you can achieve the maximum value. now to achieve lexicographical sequence just reverse the innermost box. here you have 2 choices.now again move the 2nd innermost box repeating what you did in for previous innermost box giving you 2*2 choices. this goes on till 2^(n-1).Imagine this as bits. A set bit represents that the number should be at the back.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem 2 — Can someone explain me the 4 cuts for n=20? My understanding says we require atleast 5 operations of type A performed on i=1,4,8,16,20.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

fun fact: problem E can be solved without modulus operation.

Submission: 295789260

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Just want to share my submission for C.295812221. The logic is I am keeping the ith highest element within ith position w.r.t highest element.

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How the solution code of C is related to text solution. I couldn't understand, how binary representation is related here.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, why on first operation indexes are (1,4) not (1,5)?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I learned something new from problem F

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem C using recursion and two-pointers. This is the code 296273126 The overall thought process is roughly this, if it helps anyone:

We check if the required index k is <=2^(n-1)/2, or it is more than that. if it is the first case, then we insert the lowest value of the remaining numbers at the first position, else at the last position. why? because if we take any n, say n=5, then for k<=8, 1 will be at the first position, and for k>8, 1 will be at the last position. Continuing this example, once we are done inserting the 1 for n=5 case, we decrease n in the next function call, to get n=4. now there are two steps, first we check if k is larger than 2^(4-1), if yes, we take modulo to bring k in the range of 1 to 8 (for n=4). next, we check whether k<=4 or k>4. if k<=4, we have to insert the lowest remaining number at the first position. it would be like 1 2 _ _ _. else, we insert it at the end,i.e., 1 _ _ _ 2.

We repeat this approach until we get n=1, at which point we insert the last remaining number (which will also be the original n we started with) at the last remaining index.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hey coders,,,

in Problem-C tag, there is bitmask. how can i solve this problem with bitmask. or the binary representation of k-1.what is the reason behind it. and how can i come up with this kind of solution...

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

Does anyone have a good proof for approach 1 of D ?

»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain c in detail