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

Автор Um_nik, история, 3 месяца назад, По-русски,

I want to apologize once more for queue problems. It has also aggravated some tight ML/TL issues which probably would be not so big otherwise. I hope you enjoyed the problems nevertheless.

Tutorial is loading...

38799778

Tutorial is loading...

38799800 — logs
38799811 — case analisys

Tutorial is loading...

38799824

Tutorial is loading...

38799831

Tutorial is loading...

38799840

I hope that Petr is not mad at me for my joke.

Tutorial is loading...

38799850
38799853 — completely different solution with complexity O(6n / 2)

Tutorial is loading...

38799873

Tutorial is loading...

38799881

I hope that DarthPrince is not mad at me for my joke.

Tutorial is loading...

38799887

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
 It is clear that we will run DFS exactly once for each connected component of original graph.

Can u explain this?

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

    Let's look at strongly connected components of new graph. Each connected component of old graph lies inside one strongly connected component of new graph, and you can't go from one such strongly connected component to another. So we will run DFS from each that strongly connected component once.

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

Hihi Quang Dien brought me here.

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

In Div1 B, isn´t it easier just to transform one permutation into the other and count the number of steps it takes?

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

    That's another way to count parity

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

      But, isn't it possible to swap the same pair more than once?

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

        Yes, we can swap the same pair more than once. But notice that it must take an even number of swaps to preserve the order, hence the parity and the answer will not be changed.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
          Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

          Ah, So, NicolasCassia should compare the parity of the number of steps with the parity of 3n or 7n+1.

          Thank you very much :)

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

            If from a given permutation the original can be reached with an even number of steps, why can not it also be with an odd amount?

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

              I understand this truth, but don't know how to explain it other than like following:

              After any number of distinct swaps, if I want to return to the previous case (before those swaps) I need to do the same number of swaps I have done before (and this can be understood by testing). So, the number you need to return to a previous case starting from this case is even.

              So, if a permutation P1 can be reached from a permutatuon P0 with n number of steps, and you did s number of additional steps (anywhere between P0 and P1) and still end in P1, then this s is even. So, n + s has the same parity as n. Thus, if n was even, then any number of steps between P0 and P1 will be even, and vice versa.

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

                Can you explain significance of 3n and 7n+1?? I am unable connect the dots here.

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

                  The setter want to obtain two number which are surely different in the parity.

                  Firstly, we should know the following two rules (or observations):

                  odd * even = even,

                  odd * odd = odd,

                  odd + 1 = even,

                  even + 1 = odd.

                  Then, let's discuss the two case of n:

                  If n is even, then 3n is even and 7n + 1 is odd.

                  If n is odd, then 3n is odd and 7n + 1 is even.

                  And this difference in parity is necessary to solve the problem.

                  Hope I understood your question and answered it.

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

                  Yeah, i got that. I am referring to the coded solution above. (ans^=1 and why "ans=1" implies Um_nik... "ans=0" implies Petr).

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

                  Oh, I understood you now, and really don't know what's happening in the code you referred to XD. Sorry for that.

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

      any prove?? for odd swaps will definitely give odd parity and even will even

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

      Hello Um_nik Can you tell me why do you say to count the number of inversions because in the sample case of:

      5

      2 4 5 1 3

      The inversion count is 5 whereas the number of steps necessary to arrive at the correct permutation is only 3 . Also i have applied the inversion count using mergesort, But it is still giving wrong answer. Can you help me with it? link:

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

38770498

I can't understand this solution. Can someone explain this? Thanks.

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

    Because it's a wrong solution, this is counter-test. True answer is "Um_nik", but this solution returns "Petr".

    The authors of the problem did not assume a probabilistic solution, so there are no tests against them.

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

      You are right. But this solution can get Accepted. Emmm... Your test case is randomly generated data ? Maybe this solution based in some randomly theory?

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

        Well, yes, this solution uses that tests are randomly generated and it is correct for big n. However for n = 1000 + eps it has not very good probability of being correct. But I had very few (4 to be precise) tests with small n and it happened to be correct on all 4.

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

        This test is specifically directed against a probabilistic solution.

        For example and fun, I can generated tests when this solution will be Accepted:

        srand(123456);
        cout << (rand() % 1 ? "Petr" : "Um_nik");
        

        But this will not be a complete set of tests for this problem.

        You can use this method of solution if you do not need to solve the problem completely (on some olympiads give a few points per each test).

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

Edit: I didn't see that the editorial mentions the solution with logarithms in the first two lines. Later it talks about getting the solution in integers which is nice.

If someone got confused in Div2B by seeing the editorial like me, here is a easier(imo) solution.

Case1: xy < yx

Take logx both sides

logx(xy) < logx(yx)

y < x logx(y)

y < x log10(y) / log10(x)

You can do the same for other cases and it's similar. If someone is thinking it's too much case work, here is the solution.


long double x,y; cin>>x>>y; long double kk = (x*log10(y))/log10(x); if(y<kk) cout<<"<"; else if(y>kk) cout<<">"; else cout<<"=";
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D Getting TLE in D could anyone Help?

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

    for each good store vertices which produce it(in a vector).now run BFS for each good(reinitialzing the dist/vis array) and keep pushing back into a vector(answer vector) the dist(which is obviously minimum due to unweighted graph) from the vertices producing the current good.After that sort for each vertex its ans vector and sum up the first s elements and print it.

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

 Look here: 38736740 And what I should do with that?

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

can someone give python code for binary fft

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

For Div2B, during the contest I came up with this approach:

For any two positive integer numbers a and b:

ab = ba if (a = b), else

ab < ba if (a = 1), else

ab > ba if (a < b).

But got WA on pretest 5.

Today, I checked for the test I failed in and saw it was (2 4), then treated this test, but got WA on this test (2 3), then treated this and got AC.

Is really this last approach is correct for all a and b, or it just passed the tests?

BTW, it was easy to come up with this last approach because (2 4) and (2 3) are easy to think about.

38781062

.............

UPD: Sorry, I have just seen that what I wrote above had been discussed in the editorial. I apologize for my fault.

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

    I got AC with similar solution: brute forced everything where a && b is small, otherwise using your logic.

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

I did exactly what the tutorial says in div2C, and during the contest as well, but it gets TLE on test 11. Tried searching for similar solutions in python 2 but no one AC, can someone tell me what I got wrong?

38782761

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

    Submit it on PyPy interpreter

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

    You need to relearn python bro. Use xrange instead of range. And why are you wrapping map with list? That's not needed in python 2. On the other hand, there is indeed a speed limitation with python. You might need to submit in pypy if your code is already optimized and TLEs. Sometimes, the reverse situation happens as well. So take note of this.

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

Why are some problem names written in russian instead of english in english version of editorial ??

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

I would like to just note that problems B from Div2 and D from Div1 have a lot in common. Solution to Div2B basically tells you how optimal sum looks like in Div1D ;). I don't know if it is intentional, but if not then it is funny coincidence.

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

    Yeah, I noticed it too. But it wasn't intentional :) Ddiv1 was in my problem bank for long time and easier problems were made up just for this contest.

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

;

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

Why did Div1B set a lower bound on n?

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

This is my solution for Div2 E 38777827

I am counting the number of swaps needed to obtain the permutation in O(nlogn)

how to calculate the number of cycles in permutation in O(n).

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

    Just use a regular array instead of map, the numbers in the permutation <= 1e6.

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

Can someone please explain DIV2F ? I can't comprehend the editorial.

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

May someone please tell, why did my short solution got TLE to the problem Div1-B? Submission link. Is it because of distance function?

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

    Since set does not have a random access iterator distance function takes O (n). Thats what makes it slow. For more see this

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

Can someone explain how i get AC by usingthis solution on problem Div2-D

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

    Do multisource bfs k times , for every color and note down the distances you get , the for each node sort the distance values and take first s values , you get the answer

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

Can anybody tell how to solve Div2 -D in O(s*(n+m))

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

For div1D, 3^i always looks like 100000....000 (with i 0s) in base 3. So, why don't we just convert n (or n/2, or n/4) to base 3 (In O(LlogL)) and compare it with 3^i (in base 3)?

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

38793607 Getting TLE in problem D from Div. 2. Not sure what I'm doing wrong here, could anyone help?

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

    In the bfs Don't push a node unless their cost will be updated and update the cost

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

      Thanks! I made this change and got AC. But I don't understand one thing:

      Earlier I was pushing the nodes irrespective of whether the cost would be updated; I was performing this check at the time of popping and stopping the BFS from a popped node if the cost is not to be updated. So basically in the BFS in my earlier submission, all the nodes were being operated on 2 times instead of 1 time (first time when it's pushed onto queue and second time when it's popped and I check for cost update). So this would be an optimization, right? The time complexity is the same? Please correct me if I'm wrong. Thanks again!

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

        Nvm, I understood my mistake.

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

        Actually a node will be pushed as many times as it's degree here ! Moreover, you might run into a cycle which will take you into an infinite loop !

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

How to solve Div2 E with mergesort ?

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

    Merge sort here is used to calculate the number of inversions of a permutation to find the permutation's parity.

    Suppose your permutation is 4 3 2 1.

    Divide it into two parts. 4 3 and 2 1.

    Now, what are the number of inversions created due to 2? (number of pairs where a[i] > a[j] and i < j and a[j] = 2)

    It's the number of elements larger than 2 in 4 3.

    You can easily find that in the merge process of merge sort. When you are inserting 2 during a merge, the number elements left in the other half of the array is the number of elements larger than 2, isn't it?

    So, for 1, when you have divided original array into 2 parts, you are adding 2 to number of inversions.

    When you further divide 2 1 into 2 halves i.e. 2 and 1, you are adding another 1 to number of inversions.

    This is just a basic gist, you can find details by googling about finding number of inversions using merge sort.

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

I had used the logarithmic approach as discussed in the editorial but I am getting the wrong answer for x=y (where x and y are very big) but it is working fine on my local system. I am not able to figure out the exact reason why it is behaving differently on CF judge and my local system. Can someone please help me out to understand it?

Thanks in advance.

my solution

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

Links to authors submissions are added.

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

    Not available. Looks like something with the rights

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

    If I remember correctly, you should submit by hitting an airplane submit button next to a problem in the problemset list:

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

      Looks like the important part is "the problemset list". If I submit it in the contest, it is not visible because I'm manager of the contest. Anyway, thanks.

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

    Well, the authors submissions links are not working properly. Please fix the problem, thanks. [UPD] I'm sorry for the unnecessary post too. I'll think before I post:)

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

    [UPDATE] — Its working now. Sorry for the unnecessary post.

    Your solution link is not working.

    It keeps on saying,"You are not allowed to view the requested content"?

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

    Should be fixed now.

    Last two comments are not helping.

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

For Div.1 E,can somebody elaborate the fenwick tree on euler tour tree or introduce some tutorial on it? How does it calculate the sum of on path to root in O(logn) time? Thanks a lot!

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

    keep l[x] = starting time of x in euler tour, r[x] = ending time

    If you want to set value of node x = val, then with fenwick you modify l[x] to val, and r[x] to -val.

    Now say you have 2 nodes x, y and x is ancestor of y

    The range of query will be l[x], l[y]. Every node on path from x to y will appear Exactly once on this path. And nodes that aren't on path appear twice, so they cancel out by the way we set values in fenwik tree.

    So basically sum from root to x is query on (1, l[x])

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

    Also we can do that without fenwick tree at all. Just do dfs and keep sums to the root in the global array. In this case for each query we need to calculate sum sumx + sumy - sumlca(x, y) - sumparent(lca(x, y)). That will be solution.

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

can anyone provide links to more problems like Div1-B,Div2-E.. Thanks :)

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

Can any one help me with solving Three displays problem using dynamic programming(DP)?

The states for the DP I visualised are current display label(1..N) and number of displays(1..3). For each display label I minimise and choose the best cost of one display, the best cost of two displays and the best cost of three displays.

I'm getting Wrong Answer. The case I'm missing is where I don't get the best cost of three display at any display labels. So now I'm kind of feeling stuck on how to re use the sub-problem's solution here? Can anyone help me with formulating the DP ?

My submission link contains my DP idea.

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

    I solved it with dp. It might help if you look at my solution. I think it is easier to understand. http://codeforces.com/contest/987/submission/38737422

    Hope I helped. Have a nice day!

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

      Can you please tell the logic to solve using dp?or some material to study from these kind of problems...

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

        rahul9707 Say i is the index of first display board, j is the index of second display board and k is the index of third display board of our answer, where i<j<k, We keep track of the best cost of two display boards cost(i)+cost(j) at dp(j) if font_size(j)>font_size(i). Then for each k we try to pair it with dp(j)[which holds the best cost of two boards already] if font_size(k)>font_size(k).

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

      Thanks a lot for the idea.

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

      Now if we increase the constraint, say length of the array is 10^5.

      Can we arrive at an O(N) dp for the problem ? That was what I as trying to do in my initial submissions for this problem.

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

please explain O(6^(n/2)) approach for AND graph. thanks

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

I am getting TLE for Div2D in Java even though I used the same algo as the editorial. Someone suggested that using ArrayList in graphs in Java is inefficient. Does anyone has links to some articles that explains the alternative well?

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

Dear Um_nik,

Please explain your second solution to F with complexity O(6^(n/2))

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

Continuously getting TLE in problem Div2D with Java solution . I dont understand whats wrong.

(http://http://codeforces.com/contest/987/submission/38820851)

If anyone can help :(

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
  1. In problem C And Graph, why do we have to consider the second class of edge (x,2)-->(x|(1<<k),2)?
  1. In case of third class of edge (~x,2)-->(x,1) , the AND of (2^n-1-x)&x is zero , so we can keep this edge, but x&(x|(1<<k)) is non zero so why keep this edge,though this edge might be useful in leading to some y such that x&y=0, how does it actually work?
  1. Also, many submissions I saw used transition from x--> x^(1<<k) if kth bit is set, where x^(1<<k) is the subset of x if I'm not wrong(I read it in SOS DP). What is the difference between going from a. x--> x^1<<k if kth bit is set and b. x--> x|1<<k if kth bit is not set, can someone please explain me the whole thing correctly im too much confused. Thanks;)
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Here is my editorial to problem F. I think it's easier to understand. Let me know if you have any doubts. :)

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

      First, Thanks for an excellent editorial, very nice I understood what I was missing , thankyou so much;)

      I used the same approach but I am getting runtime error- stack overflow, I use java.

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

        Hey, thanks a lot :) ... I don't know why it's getting RTE. Try removing the variable arr you'll reduce the amount of memory consumed that way and try again.

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

      Thanks! This is a very good explanation :)

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

      can someone explain me why am i getting WA in test case 14 (F. AND Graph Div 2)?

      i am using dsu to solve the problem

      http://codeforces.com/contest/987/submission/38892597

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

        Didn't understand your logic ... Please explain it clearly

        You can read the blog link I posted to understand my approach.

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

          a < b and if a&b = 0

          then i will change the vale of ane[b]=ane[a] it means b is connected with a so ane[b] != b

          if c < b and b&c = 0 so if c is not connected with a graph but b is connected with a so i will change ane[c]=ane[b]

          and in the end if(ane[c]==c) that means c is not connected with any prw graph so i will add 1 in my ans...

          Ex.

          4 3 1 3 4

          so we see than in first loop (for i=1 and j=3,4)

          1&3 != 0 (no cnange ) ane[4]=1 | ans=1

          in sec loop (for i=3 and j=4)

          now 3&4 == 0

          but ane[4]=1 so i will change ane[3]=ane[4]

          in sort i am just checking if a or b is prw. connected or not

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

            So, does each vertex have only one edge in your approach ?

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

              yes we can say that

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

                i think there can be 2 edges... assume some p and q and r S.T p<q<r among many possibilities we can say that p&q=0 and q&r=0 will be true and thus there are 2edges for q.

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

                  nup in this case first pair is (p,q) and at that time ane[q]=p

                  now for q loop ane[r]=ane[q]=p

                  so in your case its is not true

                  if a<b<c<d

                  a&d=0 , b&c=0 , b&d=0 so we can say that b has two edge

                  Ex.

                  5 12 17 32

                  but i realize that it's O(m^2) so its will not work for this problem

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

                it also means that the upper bound will only N/2 as each vertex has only one edge.

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

                *******DELETED******

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

      Damn dude how did you make such a hard problem into a piece of cake? :D. Nice solution and very easy to understand.

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

      Hello ghoshsai5000 First of all your editorials are superb.Thanks a lot. I have a problem with question E :Petr and permutations, i have solved it differently and it is quite short code. Can you look at it once and tell me where i am wrong? Here is the link: (https://codeforces.com/contest/987/submission/39357325)

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

        Thank you for your compliments :)

        You are not counting the number of inversions correctly. Give me some time to give a counter example to show why that way of counting is wrong. :)

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

          ok thank you but please do help :-)

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

          Please tell me bro....

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

            Take 2341

            So you would do

            1. 3241
            2. 3214

            But you need three swaps !

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

              Thank you...

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

              Can you tell me what we have to do after counting inversions and why? I have counted inversions using mergesort but it is showing wrong answer on test case 3.....link

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

                The idea is to count the number of swaps you need to arrive at the current permutation. Check the parity of the number of inversions.

                I know how to do it with segment trees and cycle decomposition, but I don't know how to do it with merge sort. I think there's some mistake in that part.

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

                  Can you tell me the condition(or formula) to check after counting the number of inversions? Like when will the ans be Um_nik and when Petr...

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

                The parity checking is correct. The parity of number of inversions should be equal to parity of number of operations.

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

What is the O(s(m + n)) solution to D ?

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

Inspite of the controversy surrounding this contest over the delayed queue length and the tight memory limits, I actually enjoyed this contest quite a lot ! I loved the problems and 3 of them inspired me to write blog posts.

Here is the repository of all my solutions to problems of this contest, along with explanations.

All my blog posts have some more exposition. Please read them and get back to me with any doubts or corrections. :)

I have written a blog post about B here.

I have written a blog post about E here.

I have written a blog post about F here.

(All the problems were quite beautiful :) )

Note — I have not written a blog post about C, but the repository of all my solutions also contains an O(n log n) solutions to C with segment trees. It's quite easy to understand if you know how to count the number of inversions using a segment tree. It's the same idea. First we sort elements by font size, and keep track of every elements cost and position. Then, one by one, we insert the elements in ascending order of font size into a minimum tree for cost. When we insert element x, all elements with font size smaller than x have already been inserted, so to know the smallest cost, we simply query the tree from (1, position(x) — 1).

We do the same thing for the right too, except now we insert the elements, one by one, from the largest font size. This time when we insert x, we have already put all elements with a font size greater than font size(x). So to get the minimum cost, we query the tree from (position(x) + 1, n).

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

Can someone explain update complexity in 1E(Prince's Problem).

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

(in div1B)

Why the generated tests have to be generated randomly!?

I mean hacks were disabled and we're guaranteed that input is random, even though the official solution does not rely on randomness of the input!

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

Can I get a hint for solving Div2-D in O(s(m+n))?

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

    Hi~

    Also I don't know the optimum solution, but here is my thought. Hope it help

    When we run BFS for one specific town, we don't need to record all information of k goods. Once get s goods, we get the answer. This is to say, no need to use the sort stuff.

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

For problem F — Oppa Funcan Style Remastered, why can't we use the solution of m >= 3 for m = 2? It seems to fit inside the TL. Am I missing something?

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

    I don't think that even 1 dijkstra on graph of size 3·107 fit in TL, not to say 50 of them.

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

Author's solution for div1E contained a typo (which made it incorrect, of course). There were no tests against this bug in my testset, so even two other solutions didn't help to find it. Now author's solution should be fixed and some stronger tests added. I apologize for this mistake and want to thank Death_Scythe who found the bug.

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

I can't fully understand connection between the number of cycles and parity in 986B. Can somebody explain?

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

Can someone explain how to solve Div2D in O(s(n+m)) time?

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

In problem Div2 E, I don't quite get the part of parity of 3n or parity of 7n + 1. Can someone help me with this?

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

    When n is even, 3n is even and 7n+1 is odd. When n is odd, 3n is odd and 7n+1 is even. Thus, if you know the parity of n and parity of inversions in the array, you can directly arrive at the answer.

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

Can Div2 C be solved in O(nlog(n)) time. If yes, how?

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

Troll solution for a troll problem Div1B
Link to AC soln

int n, p = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
    scan(x);
    if (x == i)p++;
  }
  if (p >= 3 or n <= 5) cout << "Petr";
  else cout << "Um_nik";

(Expected number of fixed points are very different in both approaches)