skhan_org's blog

Invitation to CodeChef Starters 119 (Rated till 6-Stars) — 31st January
By skhan_org, history, 5 months ago, In English

We invite you to participate in CodeChef’s Starters119, this Wednesday, 31st January, rated for till 6-Stars (ie. for users with rating < 2500). This contest is organised by Coding Club, IIT Ropar, as part of Advitiya 2024.

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems 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
  • +48
  • Vote: I do not like it

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

skhan_org orz

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

skhan_org Orz

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

I can get the exact failed test case when the verdict is WA but not when the verdict is runtime error

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

A little tight time limit in my opinion for Guess Who Delivers. int passes the time limit but long long exceeds it.

Code for long long

Code for int

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

    your code template looks delicious.

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    We focused only on the intended simple dfs solution (TL set 3x from model). Lca being on edge is unfortunate but i dont mind it. I am honestly very surprised by how many people found that over the former.

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

      Well, the bounds do suggest that $$$O(N^2+N \cdot M)$$$ should work and a $$$N \times N$$$ matrix to precompute the distances between all pairs of nodes seem to be much cleaner and faster in implementation than implementing LCA.

      I would say $$$1 \leq N \leq 10^5$$$ and $$$1 \leq M \leq 100$$$ would have been better bounds to suggest a $$$O(N \cdot M)$$$ time complexity.

      Edit: My bad, I thought the intended solution was using LCA but it only used simple DFS. Still, I would suggest the above bounds to avoid $$$O(N^2)$$$ solutions. But yes, simple DFS would have indeed equally good in implementation as compared to the distance matrix.

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

Unalike Gcd & Lcm has weak test cases Like below one could be a counter case. (when a bigger prime is X and P too)

counter case:
1
998244353 1
998244353
correct output:
1
incorrect output (from the above submission):
2

Hackable Submission

This line is making it hackable.

155.    if (x > 1) p.pb(x);

Which should have been

155.    if (x > 1) p.pb(1);

Which I corrected in later submission

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it -50 Vote: I do not like it

    Oh cmon, there is no way for any problemsetter to predict such a mistake, especially the way you have coded it without sqrt fsctorization which makes it immune to small tests

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

How to solve Xorred

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

    we can see that bitwise AND doesn't change more than $$$O(log(A))$$$ times with a left end as $$$A$$$. so we can go for every possible bitwise AND in $$$O(NlogA)$$$ and just calculate no of prefixes equal to those bitwise ANDs.

    my submission [works in $$$O(Nlog(max(A, N)))$$$

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

Really enjoyed the problems especially Guess Who Delivers, Submission. Will try upsolving Xorred.

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

idk if this solution for d1B is intended but:

First if $$$P\gt 30$$$ the answer is 1.

So now with memorization of the queries we only need to handle $$$Q\le 30$$$ and $$$P\le 30$$$.

enumerate $$$\gcd(x,y)=d$$$ through all divisors of $$$x$$$. then $$$y=\dfrac{d^{P+1}}{x}$$$. we just need to check if $$$\gcd(y,x)=d$$$. or $$$\gcd(\dfrac{x}{d},\dfrac{d^P}{x})=1$$$. then, enumerate through all prime divisors $$$v$$$ of $$$\dfrac{x}{d}$$$. use quick power to check if $$$d^P\equiv 0 \pmod x$$$ and all $$$d^P\bmod (x*v)\neq 0$$$.

also before enumerating through divisors, we need to just pick out all the divisors that are multiples of all the prime divisors of $$$X$$$. total complexities is $$$O(T\min(Q,30)d(X)\log X\log X)$$$ or sth?

im stuck in this problem for 1h cuz i didn't find out that $$$P$$$ has to be $$$\le 30$$$ at first...

→ Reply