wuhudsm's blog

By wuhudsm, 16 months ago, In English

A

code
solution

B

code
solution

C

code
solution

D

code
solution

E

The intended solution is $$$\Theta(n)$$$. However,if your implementation of $$$O(n\log n)$$$ solution is good, it is also possible to pass :)

There're several $$$O(n)$$$ solution.

solution1
code1
Solution2
code2

F

code
solution
  • Vote: I like it
  • +43
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

[Deleted]

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

    You can copy the code from the Editorial and submit it. After you get AC, you will be able to view the test data.

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

      can u explain how to get the d(n),w(n) for largenumbers(like 10^18) in efficient way ? sorry if i am pointless here.

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      In this: You can copy the code from the Editorial and submit it. After you get AC, you will be able to view the test data.

      Then why I'm not able to view the test data of problems A, B? I got AC on both of them.

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

        Sry,it seems impossible to show test data in any gym contests

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

what is w(n) and d(n) in editorial of C?

»
16 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it
Am I wrong or solution for problem B is wrong on this case: N = 15, K = 4.

EDIT: fixed

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

    Answer is YES since 15 can be broken into 3, 3, 3, 6 with gcd = 3 > 1

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 4   Vote: I like it +14 Vote: I do not like it

      I also said answer is YES but solution's(editorial's) answer is NO. Please read the comment carefully before replying it.

      EDIT: fixed

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

        Yes, you're correct. It should N/x >= k in editorial.

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

wasn't A supposed to be the easiest problem? the math was hard. couldn't solve it and get disapointed.

»
16 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Solution for B better than editorial.. It's sufficient to check the condtion for spf only And all test case can be answer in O(1) . Link for code: https://mirror.codeforces.com/gym/104455/submission/211966383

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone explain D editorial is not clear

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

    You can refer to this code : https://mirror.codeforces.com/gym/104455/submission/211985521 First try to find the max possible ans.. which u can think like sum is fixed u have find max product ( which comes at middle) i.e. the max ans possible is ((n/2)*((n+1)/2)) and this will be possible when u will move (n-1)/2 steps downward (say node n1) and considering that node as ancestor connect all left node to its direct child.. And the min ans you can get here is when all node will be connected serial-wise or connected directly to node 1 which will be n-1.. So, if given x lie between min and max value means we can find a tree for x; To find a tree for a particular x we will find the difference between the max possible ans and the given x, then u will be known how much ans you have to decrease.. Accordingly we will connect those node to node 1 directly to reduce the max value. For further u can see the given code..

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can some give example of A for clear understanding, how l1+r1>l2+r2 is answer??

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

Would you please investigate submission 212018133 (I submitted using one of my alts)?

It is copied directly from the editorial but also gets TLE on test6. It seems that we could only pass this problem using C++17, not even C++20, let along Python.

[user:wuhudsm][user:EndlessDreams]

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For problem E:

It is also ok to directly swap $$$a$$$ and $$$b$$$ by symmetry, i.e., replace the line

for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]),swap(b[i],b[j]);

with

for(int i = 1; i <= n; ++i) swap(a[i], b[i]);

But be careful, swap(a, b) would lead to TLE, because it will call

template< class T2, std::size_t N > void swap( T2 (&a)[N], T2 (&b)[N] ); (until C++11)

template< class T2, std::size_t N > void swap( T2 (&a)[N], T2 (&b)[N] ) noexcept; (Since C++11 Until C++20)

template< class T2, std::size_t N > constexpr void swap( T2 (&a)[N], T2 (&b)[N] ) noexcept (Since C++20)

See https://en.cppreference.com/w/cpp/algorithm/swap for detail. So swap(a, b) will run through the whole array and causes TLE.

Code:

Spoiler
»
16 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

My TLE (on test 6) solution during the competition (Using DDP+Segtree) is attached below. It might work if the time limit is looser:

Spoiler
»
16 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Why are the problems deleted? I saw they'd faded away from submissions and also upon clicking on any problem via editorial, it says contest has not started yet.

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

why the contest is restarting?