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

Автор wuhudsm, история, 2 недели назад, По-английски

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
Разбор задач TheForces Round #37 (Brute-Forces1)
  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

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

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

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

    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 недели назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 недели назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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://codeforces.me/gym/105491/submission/290413088

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

    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 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

"It will posted after the first solve or tomorrow"

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