awoo's blog

By awoo, history, 23 months ago, translation, In English

1766A - Extremely Round

Idea: BledDest

Tutorial
Solution (BledDest)

1766B - Notepad#

Idea: BledDest

Tutorial
Solution (awoo)

1766C - Hamiltonian Wall

Idea: BledDest

Tutorial
Solution (awoo)

1766D - Lucky Chains

Idea: BledDest

Tutorial
Solution (adedalic)

1766E - Decomposition

Idea: BledDest

Tutorial
Solution (BledDest)

1766F - MCF

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +77
  • Vote: I do not like it

| Write comment?
»
23 months ago, # |
  Vote: I like it +50 Vote: I do not like it

ratttttttttttttttttttttttttttttttttttttttttttttttttttttting plz

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

    LOL, why so many downvotes.

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

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

    I had a dream, not being newbie when attending Turkish Junior National Olympics in Informatics but because of the slowest rating update ever,i can't

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

When will the ratings update? :(

»
23 months ago, # |
  Vote: I like it +34 Vote: I do not like it

It is the first time that I will have a oringe name. I really want it could update rating as quickly as possible.plz

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

I didn't read B properly and thought that $$$n$$$ could take on values other than the length of the input. I thought I needed to implement a complicated LCP+Suffix Array method than ran in $$$O(n*log(n)^2)$$$ to greedily compute the minimum number of operations needed to produce the resulting string, which I wasn't able to do during the contest.

Here's my solution which actually computes the minimum number of operations: 185016918

»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

In A why 184918763 got TLE?

  • »
    »
    23 months ago, # ^ |
      Vote: I like it -49 Vote: I do not like it

    That's why you are grey.

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

    Because you are iterating from 1 to n in each case. So the time complexity would be O(t*n) which would give TLE. You have already calculated if each i is extremely round or not. Just construct a prefix sum array which would tell how many extremely round numbers are less than i. Then you can answer each case in O(1).

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    Your algorothm takes n (n = the given integer) iterations of the loop for each test case. At worst, your algorithm will have to do $$$999 \ 999$$$ iterations of the loop for each test case. A test set can contain up to $$$10^4 = 10 \ 000$$$ test cases. Your algorithm might need to do $$$10 \ 000 \cdot 999 \ 999 = 9 \ 999 \ 990 \ 000 \approx 10 \ 000 \ 000 \ 000 = 10^{10}$$$ iterations of your loop. C++ can do around $$$10^8$$$ operations on average in one second. Each iteration of your loop contains 4 fast operations: i<=n, f[i]==1, ans++ and i++. Even though these are simple and fast operations, c++ can't execute that many of them in under 3 seconds.

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

      I mean what you meant is codeforces, or his pc doesn't have computation power to execute it. c++ is just a language

»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

For D, we can consider only prime divisors of $$$y-x$$$ because to minimize the answer, if it's possible to get $$$\gcd(x,y) \neq 1$$$ for a certain composite $$$d$$$ s.t. $$$d|(y-x)$$$, it's definitely possible for some prime $$$p < d$$$ and we can reach multiples of $$$p$$$ at least as soon as we reach a multiple of $$$d$$$.

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

state transition graph for 1766E([i] represent for a sequence end with i)

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

    This state transition is sufficient enough to arrive at the intended solution.

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

Nice round. I think D and E are the best problems I've ever seen.

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

Video Editorial of Problem C : Hamiltonian Wall Link : https://youtu.be/p4-bUeGfs48

»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

E is simply brilliant.

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

    It would have been more brilliant if the states have been around 10000000000000000000000000000000000000000000000000000000000000000 and transistions ended at russia and started at your brain

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

The complexity given for B is wrong. It is O(1). There are 26^2 possible unique 2-letter strings. Any string longer than 26^2+1 will have at least one repetition due to the Pigeonhole Principle.

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

    You have to read the string, so it is $$$O(n)$$$. And even if you read it character by character, in order to go to the next test case, you still have to read the whole string.

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

I still don't understand why we need all the prime divisors of each number in C. Don't we only need the smallest prime divisor to know the earliest point when the chain will stop?

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

    Yeah correct, knowing the smallest is sufficient

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

      No, take the example (4,19), y-x = 15 and the smallest prime factor is 3, however the smallest k that ensures gcd(4+k,19+k) = 3 is k = 2, but with a prime factor of 5, we find the smallest k ensuring gcd(4+k,19+k) = 5 is k = 1. That's why we run over all prime factors and take the minimum k for each.

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

        actually knowing the smallest is suffice because you can iterate x /= least[x] then update the answer, which is a bit faster. My solution during contest: 184938325

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

          Yeah I solved it that way too but I took the OP's question as "why can't you just use the smallest prime alone"

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

if anyone wants the O(1) solution for A, here it is :)

184929564

»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What will be the expected rating of the first 3 questions?

»
23 months ago, # |
  Vote: I like it +12 Vote: I do not like it

when will the rating be updated???

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

    Perhaps the program of calculating rating change has crashed and CF stuffs are calculating manually

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

      what, manually???

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

        I cannot come up with any other idea why rating has not been updated yet now

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

          manually? are you sure there are that many of them during the war?

»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why this submission passed problem 2? Surely it's complexity is O(n^2) Your text to link here...

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

    There are only 26^2 = 676 patterns of two successive characters.

    It means that this loop will end within at most approx.700*|s| times, and is enough fast to pass.

    This is called Pigeonhole principle.

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

      I think any string longer than 704 will always be YES, and I guess the string below might be the longest one that can be NO.

»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

The contest which made me master! 139 is a happy number.

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

    It made me blue! (perhaps back to cyan tommorrow)

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

Problem- E:- Can anyone tell, which case they where missing while they where getting WA at test case 16.

expected: '1476747', found: '996573'

How to correct it.

Thanks in advance :)

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

The B solution is wrong: Try this testcase: - t=1 - string='abcdabef' - n=6, - the answer is yes according to solution but it's wrong becuase: - 4 operations for 'abcd', - then 5th operation for copying and appending 'ab' string, - then 6th and 7th operation for 'ef', - so number of operations exceed n.

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

Is the concept "smallest prime factor" (minD) a well-known thing?

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

the pair contribution dp thing is something i've really only seen in digit dp problems, interesting to see it works with subarrays as well :)

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