Hello from Bangalore, India! We have 38 teams participating this year from across the globe for Snackdown's Onsite Finals.

I'll be giving live updates here. If you have any questions related to the contest, please ask them in the comments.

The mirror contest has begun. You can see the problems on the mirror contest page — https://www.codechef.com/SNFL19MR/

Public Ranklist — https://www.codechef.com/public/rankings/SNCKFL19

Participating teams — https://www.codechef.com/snackdown/2019/finalists

10:30am — Contest has begun.

10:39am — login228 (LHiC and V--o_o--V) gets the first accepted submission of the contest on problem CATS.

Several other teams have submitted a solution for the same problem within the next minute.

10:52am — login228 solve their second problem of the contest — MTRXOP They currently lead the ranklist.

10:55am — 24 teams have solved at least one problem.

10:56am — Team havkapapstvo (Egor and pashka) solve the 3rd distinct problem of the contest (MAGARR), their team's 2nd solved problem.

11:00am — Team End Time (dotorya and zigui) solve their 2nd problem and lead the ranklist.

11:05am — moofest (xiaowuc1 and desert97) solve CIRCBIN.

11:10am — 9 teams have solved 2 problems so far. Team pastry (tourist and qwerty787788) are currently at rank 3.

11:15am — We now have 4 distinct problems solved in the contest.

11:22am — All school teams have solved 1 problem so far. Antipr00 (AsleepAdhyyan and RestingRajarshi) lead on the basis of time penalty.

11:27am — pastry solve their 3rd problem (XYPRESQ) and lead the ranklist. havkapapstvo solve their 3rd as well. They are now at rank 2 with a time penalty difference of 7 minutes.

11:35am — pastry solve their 4th problem — MAGARR

11:40am — contribution (Radewoosh and Swistakk) and osass (jiry_2 and jqdai0815) solve the 6th distinct problem of the contest — RAFFLE

login228 (LHiC and V--o_o--V) solves RAFFLE as well and moves to Rank 2.

A few glimpses from the arena:

12:00pm — login228 solve their 5th problem — pastry is no more at rank 1.

Dandelion (Um_nik and Merkurev) have solved 5 problems and are now at rank 2. pastry is no more at rank 2.

12:15pm — Pastry solve RAFFLE and they're back at rank 1.

12:41pm — login228 solve ORDNCHS.

12:42pm — Pastry solve CIRCBIN. They are only 2 minutes ahead of login228 in time penalty.

12:49pm — login228 and pastry have made submissions within a gap of 12 seconds of each other.

login228 solve MAGARR with 7 penalties.

pastry solve ORDNCHS

pastry is now leading with 7 problems solved and a lead of 1+ hour in time penalty.

Egor

Radewoosh and Swistakk

1:30pm: contribution (Radewoosh and Swistakk) solve KSUFFIX.

1:31pm: contribution solve CIRCBIN within 1 minute of their previous AC submission!

1:42pm: osass (jiry_2 and jqdai0815) solve their 8th problem — CIRCBIN and move to the top of the ranklist!

pastry follow them at rank 2 and Dandelion at rank 3 with 7 problems each.

2:20pm: pastry solve their 8th problem and move back to rank 1.

2:30pm: Scoreboard is now frozen.

The top 3 teams have solved 8 problems each. Only 1 team has solved STRSUM and no team has solved RIVERLND. Stay tuned to know the final results!

Some information about what the teams are doing at the moment:

2:59pm — osass seem to be coding STRSUM.

Radewoosh from contribution is coding up a solution too but I am not sure what problem it's for.

3:04pm — Dandelion seem to be debugging STRSUM.

3:13pm — havkapapstvo (Egor and pashka) seem to be debugging RAFFLE.

3:18pm — login228 seem to be coding KSUFFIX

UPD: The contest is over. Congratulations to the winners!

1. pastry (tourist and qwerty787788)
2. Dandelion (Um_nik and Merkurev)
3. ovuvuevuevue enyetuenwuevue ugbemugbem osas (jiry_2 and jqdai0815)

Top school team: zscoder<(_ _)> (zscoder and kasumi_utako)

Top all-women team: 别看我只是一片五花肉 (AbstractKangaroo and _noname)

I am trying to estimate the upper bound of the time-complexity of this solution by ksun48. Currently, I am assuming the upper bound on the number of divisors of N to be based on this codeforces blog, but that fact doesn't simplify the calculation of time complexity here.

• Is there a simple way to estimate a good upper bound for this solution?
• Is there some literature around formally calculating time complexity in such scenarios?

When I opened Codeforces today, I saw that all the UI elements on the right side of the page — Top Rated contestants, Top contributors, etc. were all missing. I wonder why that's happening. Strangely, everything works fine in Incognito.

MIT's Design and Analysis of Algorithms Course from Spring 2015 has some interesting topics which may be useful for programming contests, like:

• Convex Hull
• Advanced DP
• Max Flow, Min Cut
• Matching
• Linear Programming, Simplex

I hope this can be useful for many people :)

For a problem that I am solving, I need to sort in descending order all edges by weight and keep removing edges till the graph becomes disconnected.

I am performing DFS after removing every edge, to check if the graph is disconnected. So, the time complexity of this method is O(NM).

Is there any way in which I can perform the above task faster?

The schedule for Google Code Jam 2015 is out!

The onsite finals will be held at Seattle, Washington.

Schedule

Problem Link — https://www.hackerrank.com/contests/csindia14-er1/challenges/fill-the-tank

Given an array of positive integers, find whether a particular sum can be made using the array elements. There were Q queries, Q<=10^5.

How is this problem supposed to be solved?

Apparently, a bug has been found in bash and that has made servers using bash shells vulnerable.

(Read more here and here).

CF Server Shells should be upgraded, as fixes are being made.

The following problem appeared in a local programming contest in my city. The problem is as follows:

There is a string S that consists of lowercase English alphabets, Two players — A and B are playing a game. In one turn, a player can choose either the character at the leftmost end or the character at the rightmost end. Suppose the player chose a character C, then all C's are removed from the string. Player A plays first. The player who removes the last characters of the string wins, i.e. if on removal of a certain character the string becomes empty, then the player who removed those letters wins. If both players play optimally, find out the player who wins.

EDIT: When the characters are removed, the player gets as many points as the number of characters that are removed. If both players play optimally, find the winner. (Both players try to maximize the points scored)

Given two strings, what is the best method to find the longest common palindromic substring?

This problem was asked in a local programming competition in my city, constraints were not specified.

Can someone please suggest websites where teams can train for ACM ICPC by participating in contests similar to those in the Codeforces Gym?

Q. Given an array of N positive integers, find all pairs (a_i, a_j) such that Gcd(a_i, a_j) > 1.

1 ≤ N ≤ 10⁵

How can this problem be solved?

GCD Recruit — HackerEarth

Problem Link

Given an array of numbers, output the answer to Q queries:

Each query if of the form L, R, X — Find the number of occurences of a[i] in the range [L, R] such that a[i] XOR X is minimum for any i in [L, R]

1 <= N <= 10^6

1 <= X, a[i] <= 10^9

1 <= l <= r <= N

1 <= Q <= 50000

Hello everyone!

The National Computing Contest (NCC) will take place on Thursday, May 15 — 21:00 IST. This is the first time asdoc and I have set problems, and I hope not the last :D

The contest will be held on CodeChef.

To be eligible to win prizes, you need to fill in the Registration Form.

Here is the Contest Link.

Gl & hf ! :)

P.S. -

1. This contest will be somewhat like a Div 2 contest.

2. Prizes worth Rs. 5k are to be won.

3. We will be giving prizes only to Indians.

Q: Given an array of n integers, find the maximum value of GCD for all possible pairs.

Sample Test Case- 1 2 3 4 5 Output: 2

2<=n<=10^5

Given a set of n points and m transformations that are to be applied to each of the points, how can I perform the transformations in < O(nm)?

I tried to understand the solution to this from an article on e-maxx.ru/algo/binary_pow (its English translation), but I was unable to understand the method. Can someone help me out?

For a given sequence of binary numbers {a1, a2, a3, ... , an}, {c1, c2, ... , cn} indicates the sequence of cumulative xor upto the i'th number. How can I find the cumulative xor of a subarray ai...aj using the sequence of cumulative xors?

I got Denial of Judgement as the verdict for 5346681, while solving Sereja and Anagrams (Codeforces Round 215 (Div. 1)). Is it because I declared an int array of size 10^9-1 ? The program is giving me the correct output on my computer, though compilation takes a slightly longer time (about 1.5 — 2 seconds).

I started learning Dynamic Programming today from Topcoder's tutorial. The following was put up as a Practice Problem:

Given an undirected graph G having N (1<N<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesn't exist.

My question is, 1. How does it matter, whether the graph is directed or undirected? 2. I can apply Dijkstra's algorithm directly on the graph, so what's the use of Dynamic Programming to solve this question?

Consider the abcissae x1, x2, x3, ... , xn. Make pairs (A,B) for all x(i),x(i+1) such that: A=min[x(i) and x(i+1)] and B=max[x(i),x(i+1)] Now, consider 2 segments (P,Q) and (R,S).

P ---------------------- Q

'R' can lie either within PQ or outside it.

If R lies outside,

R---P--------------Q

S can either lie outside or inside. If S lies inside PQ, then there is an intersection, else there is not.

R---P------S-------Q

or

R-S-P--------------Q

R---P--------------Q---S

If R lies inside PQ,

P -------------R-----Q

If S lies Outside PQ, then there is an intersection, else there is not.

P -------------R-----Q-----S

P -------------R--S--Q

So, it is just 2 cases we have to check, if we make a min/max pair.

The solution is of time complexity O(n^2).