Hello, Codeforces!

We are glad to invite you to participate in a reverse coding challenge hosted by technical fest Pragyan, NIT Trichy, which will take place on Friday, 23rd February, from 5:00 PM to 7:00 PM IST.

Pragyan, in association with Spider, presents Decode It. A reverse coding and logical reasoning contest on Hackerrank will go live on 23rd February, from 5:00 PM to 7:00 PM. A 120-minute contest to test your logical reasoning and coding abilities.

Think you have what it takes to reach the top? Test your logical and coding skills in a beginner-friendly contest.

CASH PRIZES Distribution (Indian Participants):

• Prize pool : INR 10000.
• Top 3 performers will be awarded cash prizes of INR 5000, 3000, and 2000, respectively.

Contest Date: Friday, 23rd February
Contest Timing: 17:00 to 19:00 IST
Registration Link:Link
Discord link: Link
Pragyan Website link: Link
Duration: 120 minutes

Only Indian college students and registered participants will be eligible for prizes. Please join the discord server for getting regular updates about the event.

We want to thank:

• Problem Setter: ASHWANTH_K, -CODER001
• Problem Tester: ASHWANTH_K, -CODER001
• Development Team: Nanthana2003
• We would also like to thank Don_Wick , rkviswakrishnan for timely help in generating and testing executable files.
• Special mentions to Nikolai_Tesla for giving good ideas about the event.
• Spider (Technical club of NIT Trichy) for providing all required resources and moral support.
  Hackerrank for supporting the event, their invaluable help, and their excellent platform.

Solutions for all the questions will be posted shortly after the contest ends!

https://cses.fi/problemset/task/2174
i am clueless for this problem. please help me .
I have solved the easy verison of problem using O(N) dp.
I have spent a good amount of time thinking but could not find any solution.

It would be nice if i get any hints.. instead of actual solution...

I have given thoughts about matrix exponentiation, or any observation patterns ... nothing seems to workout.

• Problem Link: https://cses.fi/problemset/task/2402
• I have solved this problem using component merging ideas. complexity: $$$O(Nlog^2(N))$$$
• Numbers belonging to the same component are assigned in the same stack.
• One observation I could see was, that if I am able to do an output operation, it's always optimal to output the number as early, without delaying the output operation.
• Another observation, we could maintain currently active numbers, and if any new number $$$X$$$ is added, we could make a component for all numbers < $$$X$$$
• I felt happy to solve this problem on my own, as it had only 73 correct submissions till now.
• I am curious to know if there exists a simpler approach (any mind-blowing observation/ lower complexity) to solve this.

https://codeforces.com/contest/1721/submission/218867337
In this submission, for 4th testcase i get TLE. But 4th testcase participant output is printed, Why is it so...

I will account for good observations and ideas while solving problems in codeforces/CodeChef/atcoder . The proofs of the below statements will not be mentioned here; It's advised to do such proofs on your own for exercise.

• Lets say I have a set $$$S$$$ consisting of integers, denote its $$$lcm(S) = L$$$, I add a new element $$$x$$$ to this set $$$S$$$ , Lets deonte the new set as $$$S'$$$,where $$$S' = union(S , x)$$$ and its $$$lcm(S') = L'$$$. Can we deduce a relation between $$$L$$$ and $$$L'$$$? We can observe $$$L = L'$$$ or $$$L' >= 2*L$$$.
  

  ---

• We want to find two numbers in an array $$$A[]$$$ with maximum common prefix bits in binary representation. It's easy to show that those two numbers always occur as adjacent numbers in $$$sorted(A[])$$$

  ---

• The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $$$log(A_{max})$$$
  

  ---

• Let's say I have a number $$$X$$$, And I apply modulo operation as many times as I wish, i.e $$$X = X \% {m_i}$$$ for some different values of $$${m_i}$$$. It can be shown that $$$X$$$ takes $$$log(X)$$$ distinct values until it reaches to $$$0$$$.
  

  ---

• If $$$N$$$ times $$$abs()$$$ function appears at any problem, maybe bruteforcing all $$$2^N$$$ combinations of $$$+/-$$$ may give way to the solution sometimes. Especially when we need to compute a function of form $$$max(abs(...))$$$
  

  ---

• Prefix Bitwise Or/And can take a maximum of $$$log(max(A[i]))$$$ values.

  ---

• Nested totient function say $$$phi(phi(phi( ... (X) ... )))$$$ will eventually reach 1 in atmost $$$2log(X)$$$ nested functions. Useful for computing expressions like $$$(A^{(B^{(C^..)})})$$$ modulo $$$P$$$. (nested powers).

  ---

• SOS dp may help to compute the number of $$$i$$$ such that $$$A[i]$$$ is a subset/superset/no bits common to a given mask $$$X$$$

  ---

• Partial optimisation of SOS dp leading to $$$3^N$$$ complexity may pass for $$$N <=15$$$.

  ---

• Whenever You want to maximize/minimize bitwise properties among some elements, consider iterating from the last bit and checking its possibility. This greedy assigning from the last bit will work.
  

  ---

• Any counting problem, like counting pairs of elements/counting subarrays satisfying some property: If any common technique, like fixing the L pointer or 2pointer approach, does not work, try to divide and conquer. It may be easy to come up with a solution sometimes. https://codeforces.com/contest/1849/problem/E

  ---

• The contribution Technique impresses me every time. Try this: https://atcoder.jp/contests/abc312/tasks/abc312_g. Hint: number of ways of choosing three nodes in the same tree path can be converted to summating all path lengths in the tree.
  

  ---

• General Technique: For counting problems: try to fix some parameters and iterate on it. It may happen that fixing just one parameter may be difficult sometimes to count properly. So try to do casework and identify which cases can be easily calculated by fixing different parameters. Eg, let's say my problem can be divided into 2 cases, $$$case1$$$ and $$$case2$$$. It can happen that fixing parameter $$$A$$$ can be easy to count distinct answers for $$$case1$$$, and fixing another parameter $$$B$$$ can be easy to count distinct answers for $$$case2$$$. Try this: https://codeforces.com/contest/50/problem/E Hint: case1: rational, case2: irrational roots.
  

  ---

• It's not wrong to complicate ur solution with a lazy segtree. Try this: https://codeforces.com/contest/1553/problem/F

  ---

• Lets take an array $$$A$$$ and let $$$f(x)$$$ be number of subsequence with $$$Xor(subseq) = x$$$. It can be shown that $$$f(x)$$$ is always a power of 2. Strong result: f(x) = 0 or f(x) = f(x1) = f(x2) ...!= 0. More insights on this can be understood well by studying the xor basis technique.
  

  ---

• $$$O(N^2)$$$ may give tle, but $$$O(N^2/64)$$$ will pass. clue: BITSETS

  ---

• Maximum Manhattan distance between 2 points: convert every point $$$(x,y)$$$ to $$$(x',y') = (x-y,x+y)$$$. then $$$answer = max(max(x')-min(x') , max(y')-min(y')) $$$

  ---

• If you find some observation or pattern problem, better bruteforce all possibilities to arrive at observing patterns quicker. https://codeforces.com/problemset/problem/1730/D, I tried brute-forcing all possibilities; it happened that I could figure out some common pattern everywhere, then I proceeded to put claims, and it happened that they were true.
  

  ---

• Any array operation, like adding on an interval, adding $$$+x$$$ on some subsequence of the array, or any other variation, try to think its effect of operations on the prefix sum. This may give a clue to the answer. Eg, https://codeforces.com/contest/1556/problem/E
  

  ---

• https://codeforces.com/problemset/problem/623/B If I remove a subarray of size < N from an array, then either the first element or the last element remains as it is...
  

  ---

• $$$gcd(x,y) = gcd(x-y,y) = gcd(x,y-x)$$$ https://leetcode.com/contest/biweekly-contest-96/problems/check-if-point-is-reachable/

  ---

• Idea: Intuitive Proof of Dijkstra problem. Consider a graph problem where I have to find the shortest distance from source to destination where all edges are undirected and weighted. Additional constraint, all costs of edges $$$ c_i = W $$$ where W is a positive integer. This modified problem with all equal weights can be solved with simple BFS.

• Now consider the real problem of Dijkstra, where I have varying edge weights. I can add dummy nodes at the intermediate of those edges to make all edge weights equal. Example: If $$$w_i$$$ is the weight of the edge between $$$u$$$ and $$$v$$$.

• Then I can add $$$w_i-1$$$ dummy nodes equidistant from $$$u$$$ and $$$v$$$ to make all edges cost $$$1$$$. Now, our problem has a BFS solution with complexity $$$sum(w_i)$$$. But I am concerned only with the original nodes' distance values in the graph.
• I need not calculate my dummy node's distance. So we can fast-forward this BFS to calculate the distance of only the original nodes. This fast-forwarded version of BFS is simply DIJKSTRA.
  

  ---

• Lets say I want to factorize $$$N$$$ , precompute all primes from 1 to $$$sqrt(N)$$$ and check for each prime. Complexity = $$$O(sqrt(N)/log(sqrt(N)))$$$ which is just $$$3500$$$ for $$$10^9$$$
  

  ---

• Lets say U want to compute shortest distances on a graph with many edges (n^2) this would give tle ... but we could seek out some way to reduce the count of edges. lets say node u is conneted to all nodes (L...R) , then we can represent a segtree of these nodes and add edge from node u to only logn intervals. (L...R) can be covered by atmost 2logN intervals . So we can add edge from u to these intervals. Also we can edges from every node to its children in segtree with 0 cost. Running dijkstra on this segtree would solve the problem. https://codeforces.com/contest/786/problem/B practice problem.

I dont know what to put here.... Pls help

Hello Codeforces!

We are glad to invite you to participate in a contest hosted by technical fest Pragyan, NIT Trichy, which will take place on Thursday, 23rd March, from 5:30 PM to 7.10PM IST.

Pragyan, in association with Spider, presents Code Venture. An competitive programming contest on Codechef which will go live on 23rd March from 5:30-7:10 pm. An 100 minute contest to test your problem solving and thinking abilities.

Think you have what it takes to reach the top? Test your programming skills in a beginner friendly contest.

The contest is unrated for everybody and common for all divisions.

CASH PRIZES Distribution (Indian Participants):

• Top 3 performers will be awarded cash prizes of INR 15000, 9000, and 6000, respectively.

Contest Link: CDVN23
Contest Date: Thursday, 23rd March
Contest Timing: 17:30 to 19:10 IST
Registration Link:Link
Google form link: Link
Duration: 100 minutes

Only registered participants will be eligible for prizes.

We want to thank:

Problem Setters

• rxhxn_30,aadarsh_ram,amitkumar2003.edu,ASHWANTH_K,ayushkumarsandil,vvipulpatel,sobhagyaSD

Problem Testers

• narendra_chiku,ayushkumarsandil,shubham_up_47,GR_Bhau,vvipulpatel,vivek_yamsani,sobhagyaSD,e_n_i_g_m_a,Genichiro,lazarus249,mds_108,rebelz123

CodeChef for supporting the event, their invaluable help, and their excellent platform.

Editorials for all the questions will be posted shortly after the contest ends!