wuhudsm's blog

By wuhudsm, history, 2 weeks ago, In English

A: Niimmm

Idea:Yugandhar_Master

First solve:lonely_forever

tags
solution
code(C++)
Rate the problem

B: K Palindrome

Idea:Yugandhar_Master

First solve:Egor

tags
solution
code(C++)
Rate the problem

C: Pair of GCD

Idea:Yugandhar_Master

First solve:Egor

tags
solution
code(C++)
bonus
Rate the problem

D: Perfect Prefix

Idea:Yugandhar_Master

First solve:Egor

tags
solution
code(C++)
bonus
Rate the problem

E: Any Tree ?

Idea:Yugandhar_Master

First solve:lonely_forever

tags
solution
code(C++)
Rate the problem

F: Permutation via Tree

Idea:Yugandhar_Master

First solve:methanol

tags
solution
code(C++)
bonus
Rate the problem

G: If Sort is Life

Idea:Yugandhar_Master

First solve:

tags
solution
code(C++)
Rate the problem
  • Vote: I like it
  • +21
  • Vote: I do not like it

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

Statement of problem E is misleading. I was thinking about arbitrary values of the nodes but not the indexes of the nodes.

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

    Yes but anyway still doable, given E was nothing but value of node i is i. But coming to the misleading I didn't mentioned special values of nodes in the Statement and in sample tests too so I thought no one will confuse. But sorry for that inconvenience

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

The complexity of problem C should be $$$O(nlog(a_i)+t(D(a_i)+f(a_i)))$$$, where $$$f(a_i)$$$ is the complexity for factorization. Using Pollard's rho algorithm C can be solved with $$$a_i\leq10^{14}$$$ (or $$$10^{18}$$$ even if $$$t\leq100$$$). Is there any way to solve it in faster than this time complexity (e.g. with the original constraint of $$$t\leq1000$$$ ? I don't think that fits in the 2s time limit.)

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

    You can solve this problem using any data structure which finds range gcd faster (for example sparse table). Take prefix gcd array $$$p$$$ and suffix gcd array $$$s$$$ let's call $$$x$$$ and $$$y$$$ special indices where $$$p[x]<p[x-1]$$$ and $$$s[y]<s[y+1]$$$. Note that these special indices are limited. So you can choose any two special factors and assume that you are changing them, for this purpose you need to calculate range gcd faster. Total Time complexity $$$O((n+β^2)logn)$$$ where $$$β$$$ is number of special indices. The upper bound of $$$β$$$ can be around $$$60 -> log(10^{18})$$$. Which got ACed in around $$$200$$$ s in C++

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Simpler solution for C same idea as MAXIMGCD on codechef, works for values upto 1e18 too, only indices where prefix or suffix GCD changes matter and there are logarithmic of them so brute over them with some range query DS. https://mirror.codeforces.com/gym/105491/submission/290413088

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

    The problem C can be solved more easily using Idea 3 of this post, and this also works for the bonus problem ($$$a_i \leq 10^{18}$$$).

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

Really enjoyed the contest . I hope keep more such contests frequently

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

"It will posted after the first solve or tomorrow"

Well, tomorrow passed 4 days ago and no one solved it...