ACM ICPC 2017 - Kolkata Kanpur Regional

Problem Discussion

• Reached Safely Or Not
• Triangle Count
• Appearance Count
• Club of Riders
• Get The Gold
• Password Riddle
• Raw Power
• Huge Number of Trees
• Secrets
• Palace of King
• Unpredictable Array

Easy

Easy

Easy - Medium

Easy - Medium

Medium

Medium

Medium

Medium - Hard

Medium - Hard

Hard

Super Easy

Reached Safely Or Not

• Accepted: 160
• First Solve: lastTry
• First Solution Time: 00:07:22

​

​

Author: Kazi Hasan Zubaer

​

Reached Safely Or Not

Analysis

�Just keep track of the position and check the end position if it’s dangerous, or relative’s home, or something else.

Triangle Count

• Accepted: 156
• First Solve: SSH, JGEC
• First Solution Time: 00:10:02

​

​

Author: Kazi Hasan Zubaer

​

Triangle Count

Analysis:

The answer is 1 + 2  + 3 + … + (L-K+1). That’s it, plain as simple. Use the summation formula if you wish.

�

Appearance Count

• Accepted: 119
• First Solve: WeAreNoobs, IIT Dhanbad
• First Solution Time: 00:08:43

​

​

Author: F. A. Rezaur Rahman Choudhury

​

Appearance Count

Analysis:

• Number of occurrence of a string in all possible string of length n doesn’t depend on the content of the string. It only depends on the length of the string.
• xxxyyyxxxx
• Any string of length m appears in all possible strings of length n exactly �(n-m+1)*26^n-m times.

Club of Riders

• Accepted: 109
• First Solve: weakMind, BITS Pilani
• First Solution Time: 00:34:13

​

​

Author: Sheikh Shakib Ahmed

​

Club of Riders

Analysis� 1 5

� 1 2 5 6�� 12 2 1 1�

Get The Gold

• Accepted: 32
• First Solve: Supercalifragilistic - IITM
• First Solution Time: 00:45:03

​

​

Author: Dr. Md. Kaykobad

​

Get The Gold

Analysis�

Password Riddle

• Accepted: 8
• First Solve: NeverSettle
• First Solution Time: 03:02:09

​

​

Author: Kazi Hasan Zubaer

​

Password Riddle

Analysis

• All the characters represented by a segments are the same
• The literals will be simply multiplied
• Only 4 primes to consider

�two odd three six matches with C = 666…��len(C) = 2 * {1,3,5,7} * 3

�

Raw Power

• Accepted: 4
• First Solve: TooLazyToPropagate, IITV
• First Solution Time: 02:25:53

​

​

Author: Archit Karandikar

Raw Power

Analysis�

• Binary search on the answer, q
• S : all the intervals sorted according to start point. �E : all the intervals sorted according to end point.
• Claim:�There exist an optimal way where at least one interval remains stationary

���

​

Huge Number of Trees

• Accepted: 1
• First Solve: egglet, IITB
• First Solution Time: 04:51:53

​

​

Author: Anindya Das

Huge Number of Trees

Analysis

• K nodes in previous level

​

​

• N nodes remaining
• D is the minimum degree
• Sn (n, k, d) = k * Sn (n-1, k, d) � + C (n-1, d-1) * Sn (n-d, k-1, d)

​

1

2

3

k

Secrets

• Accepted: 0
• First Solve: --
• First Solution Time: --

​

​

Author: Kazi Hasan Zubaer & Zi Song

Secrets

Analysis

• Your envelope and your best friends envelope are identical
• Number of states: 10!/(2^5)�

Palace of King

• Accepted: 0
• First Solve: --
• First Solution Time: --

​

​

Author: Kazi Hasan Zubaer

Palace of King

Analysis��

Unpredictable Array

• Accepted: 0
• First Solve: --
• First Solution Time: --

​

​

Author: Repon Kumar Roy

Unpredictable Array