IceKnight1093's blog

Invitation to CodeChef September Starters 57 (Rated for Div 3 & 4) — 22nd September
By IceKnight1093, history, 19 months ago, In English

We invite you to participate in CodeChef’s Starters 57, this Thursday, 22nd September, rated for Div 3 & 4 Coders.

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are:

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Unrated for div2 again lol

→ Reply
»
19 months ago, # |
  Vote: I like it +13 Vote: I do not like it

It's quite irritating when you suddenly remove a division(here div-2) from rated participation. I think you guys should judge the contest beforehand to avoid miscommunication because lots of users have to reschedule themselves accordingly!

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

    I just noticed it. Skipped my final exam studies for nothing lol

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Solved TREEDIVS without even knowing the constraint on $$$T$$$ (number of tests)

This is what happens when there is only one tester..

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    "The sum of N across all test cases won't exceed 3⋅10^4" and "N >= 1" implies "T <= 3⋅10^4".

    Agreed that "T >= 1" was missing.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Actually in my AC solution, I am memsetting an array of size $$$10^6$$$ in each testcase, so I thought $$$T$$$ shouldn't have been as big as $$$3 \cdot 10^4$$$, else it would have TLE-d, but seems like I am wrong.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        The largest $$$T$$$ in the testfiles is a bit more than $$$1100$$$, which is also the case where your code took the most time.

        That's still more than $$$10^9$$$ operations, but luckily for you memset is generally pretty fast. I didn't really expect submissions in anything other than $$$\mathcal{O}(N \cdot \text{something})$$$ per test case so I figured providing the sum of $$$N$$$ would be enough, which in retrospect was probably not the best decision.

        → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

How to solve div1 E (treedivs)?

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In probelm Div2 E (TREEDIVS):

I calculated prime numbers upto $$$10^3$$$. Then stored the frequency of the prime factors of the value of each node in a 2D array. Then using a DFS I merged the frequencies of child nodes with parent node. Finally calculated number of divisors for each node using the formula: $$$nod = \prod\limits_{i=0}^{primes.size()}(fr_i+1)$$$ where $$$fr_i$$$ is the frequency of $$$ith$$$ prime

Sadly I got WA :( Any idea why? Or is the approach wrong?

my code

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

    Why is NN 200 in your code? Are you claiming there are only 200 prime factors?

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

      There are 168 prime numbers upto $$$10^3$$$ so I took a slightly bigger number

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        What about the primes greater than $$$10^3$$$ ? A number can have a prime factor greater than the square root. Did I miss anything from your code? Are you considering those?

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

          Ohh you are right!! completely missed it lol.

          thanks for your help! :)

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

how to solve Delicious Queries?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For every prime number $$$p$$$, store the following

    1) Indices for which $$$a[i]$$$ is divisible by $$$p$$$.
    2) Prefix sum of elements at these indices
    3) Prefix sum of the sorted(descending) array of elements at these indices.

    Also store the prefix sum of the original array. On a query, find the last index $$$\leq k$$$ such that $$$a[i]$$$ is divisible by $$$p$$$ using upper_bound on the first array. Now subtract prefix sum at this position and add best prefix sum(descending sorted) at this location.

    https://www.codechef.com/viewsolution/74951342

    → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Tree and Divisors can be solved with small-to-large merging on the tree. Note that if the prime factorization of a number is given by $$$x = \Pi \;p_i^{n_i}$$$ then the number of factors of the number is $$$\Pi\;(1 + n_i)$$$. Here is a blog which I wrote on small-to-large merging a while back.

Blog — https://codeforces.com/blog/entry/103064

Codechef solution — https://www.codechef.com/viewsolution/74799354

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

    I used that but still TLEd on 5/11 test cases. Code

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

      You are iterating over all primes in the subtree of the current node at the end of your dfs. That defeats the whole purpose of small to large. Instead maintain the answer for each subtree and divide and multiply when you insert a new number into it. So it will be better to first find the largest subtree and then insert all numbers into it.

      → Reply