You are not logged in. Please login at www.codechef.com to post your questions!

×

Invitation to International Coding League 2018- External Rated Contest

7
3

Hi Codechef community,

Computer Science Association & Association of Computing Machinery, BITS PILANI, Pilani Campus presents you their flagship contest, "International Coding League 2018". It is being organised as a part of our annual technical fest, Apogee.

The contest will be External rated contest and will be of 2.5 hours.

Contest Link : https://www.codechef.com/ICL2018

Start Time : 20:00 IST, 27th February' 2017

Prizes: Worth Rs 20000 (10k + 6k + 4k) for top 3 Indian winners.

Also top 5 Global winners and top 5 Indian winners will get 250 laddus each.

The contest consists of 5 algorithmic problems of varying difficulty. The problems have been set such that even beginners can attempt a few problems and even the best coders find tough job ahead at the hard ones. It is advised to read every problem in the contest. The detailed editorials of all the problems with the Setter's & Tester's code will be uploaded immediately after the contest so that you may benefit from it.

The setting and testing panel includes me, akulsareen, ankit, divesh, priyank and vibhav. I would also like to thank Arjun arul from Codechef team for going through the problems and improving the statements as well.

To participate in the contest, you just need a Codechef handle and then just click on the link mentioned above for participating for the contest.

I hope you enjoy the contest and Happy Coding :)

You can find the link of last year contest here

asked 27 Feb '18, 11:16

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 27 Feb '18, 21:51

Contest starts in 20 minutes.

(27 Feb '18, 19:42) likecs6★

Short Editorial of first 4 problems:

Problem 1 — Matrix Game Greedy solution applies and Matrix has no rolw in the problem. Just consider the numbers and at each moment of time every person tries to take the largest available number. Find the sum they can accumulate after this process and print answer accordingly.

Problem 2 — Stingy Strings Again greedy solution applies in the sense that we replace all occurences of a given character by its corresponding number or replace none of them. Next part is to modify the cost function as "length — 2(count of numbers) + (sum of numbers)/k". Using this, we can say that we replace only those ccharacters with numbers whose value is greater than or equal to 2k.

Problem 3 — Maze love

Let number of steps taken in each direction be N, S, E, W. So we have following equations:

N — S = m, E — W = n, Na + Sb + Ec + Wd = P

Replace S, W in last equation, we get N * A + E * B = C, where A = a + b, B = c + d, C = P + mb + nd

The other constraints are N, S, E, W are integers and N >= m, S >= 0 and E >= n, W>= 0.

Solution exists when gcd(A, B) divides C. After this check, we simply brute force over the possible values of N and update answer (i.e. minimum value of N+S+E+W) if present.

Problem 4 — Replace and Substring queries.

Idea is to find the number of substrings with given mask in string B easily. For this, we fix a particular index and find the first point of occurrence of every character on the right and add the corresponding contribution to the mask. For example- In "aabbbbdac" for index 1, "a" occurs at "1", "b" occurs at "3", "d" occurs at "7" and "c" occurs at "9". So number of substring with one endpoint at 1 and having mask 1 are 2, mask 3 are 3, mask 11 are 2 and mask 15 is 1.

One this initial computation is done, we try to handle the queries and updates. For query on string "a", we just need to find the mask of the substring a[l:r] and this requires to compute if a particular character occurs in a range. With updates on string "a", this can be easily handled using fenwick tree or segment tree.

To handle updates on string "b", idea is to first remove contribution of every substring which contains the xth character and then add the contribution back. For finding number of mask of substrings with contain xth character, we see the substring can either end at x, start at x or contain x in the middle. The first 2 are easy to calculate and are similar to the construction by finding first occurrence to the left and right of index x. For the substring which contain "x" in the middle we can visualise them as 2 parts, left and right and their mask being the "OR" of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O(ALPHA**2) we can find their contribution too.

Complexity of precomputation is O(m * ALPHA * log m) and query and update on string "a" is O(ALPHA * logn) and O(log n) while update on string "b" is O(ALPHA * log m + ALPHA**2).

link

answered 27 Feb '18, 22:34

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

In problem 2
Next part is to modify the cost function as "length — 2(count of numbers) + (sum of numbers)/k"
I am not able to get this! Can you elaborate a bit more on this?

(27 Feb '18, 22:41) dishant_184★

Count of numbers + count of characters = n (i.e. length of array). So we replace count of characters in the cost function using the above equation.

(27 Feb '18, 22:47) likecs6★

Won't the length of array change on replacing character to number? Eg: Character : z
Number : 26

(27 Feb '18, 23:02) dishant_184★

solution:https://www.codechef.com/viewsolution/17558988 what is wrong with solution?

(27 Feb '18, 23:04) viralivora4★
1

@dishant_18, don't see numbers literally, try to understand them as single object occupying a position and what value it adds if it was present.

(27 Feb '18, 23:16) likecs6★
1

Can anyone explain this line "For the substring which contain "x" in the middle we can visualise them as 2 parts, left and right and their mask being the "OR" of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O(ALPHA**2) we can find their contribution too.",what does convolution means here and what is ALPHA?any help or reference to any tutorial for learnig such concepts is welcomed.

Thanx in advance!!

(28 Feb '18, 12:10) vivek_19982996★

Thanx a lot!!

(01 Mar '18, 13:50) vivek_19982996★
showing 5 of 7 show all

@vivek_1998299 ALPHA refers to alphabet size, which is 20 here. OR convolution refers to polynomial multiplication where $c_0 x^{p_0} \cdot c_1 x^{p_1} = c_0c_1 x ^{p_0 | p_1}$. To put it simply the coefficients at $p_0$ and $p_1$ affect $p_0 | p_1$ instead of $p_0 + p_1$.

This is relevant here in the following manner: assume you know there are $c_0$ substrings with mask $p_0$ that begin at "x". Similarly there are $c_1$ substrings with mask $p_1$ that end at "x". So there will be $c_0c_1$ substrings with mask $p_0 | p_1$ that contain "x" irrespective of where it lies.

link

answered 01 Mar '18, 13:27

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

Short explanation for last problem: Raid Systems

The first idea of the problem is to see that files on xth hard disk can be retrieved using files on hard disk 1. The file indices differ by exactly (x-1). For example, if at any moment of time, hard disk 1 has files f1, f2, f5 when n = 5, then hard disk 2 has files f(1+2-1), f(3+2-1), f(5+2-1) i.e. f2, and f3 (f7 is discarding). See the table to convince regarding this observation. Thus, the queries of both type can be handled very easily using binary search only provided we are able to find the files in sorted order on hard disk 1 on any day.

Next thing is to notice is that the pattern of files being stored on hard disk 1 will repeat after some time, to be precise after 2^(ceil(log2(n)). Draw a table for n = 8 and n = 5 to get view of it. Next observation is that total number of files we require for all possible days is bounded by 3^ceil(log2(n)). For example: Consider n = 4

0: f1 1: f1, f2, f3, f4 2: f1, f3 3: f1, f2 4: same as 0 i.e. pattern repeats.

The total number of files stored i.e. slots used is (1 + 4 + 2 + 2) = 9, 3^2. You can see this thing for any general n. Complete the table for n=5 and observe the same. Now, we just need to come up with a 3^(ceil(log2(n)) generation algorithm, which gives us the files in sorted order on any day. The memory complexity will also be the same. Many constructive algorithms can exist and you can try to find your own. My solution uses just one of my finding, idea is again similar to binary search i.e. can be divide the files (in sorted order) in half, calculate the files on left side and use it to calculate the files on right side. Basically, I mean to say that if a particular bit is set in "y" and we calculate the lower half files, then the upper half files are basically the mirror image on the lower half files. You can check my "gen" function in the solution code for details. Code

link

answered 27 Feb '18, 22:41

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

2

This problem is quite interesting and it seems the accepted solutions use various different methods. My solution uses the fact that the queries can be reduced to the form of find the position of the $a^{th}$ odd number in the $b^{th}$ row of Pascal's triangle, due to the pattern that shows up. And it turns out that all the odd numbers are at the positions which are numbers obtained by removing zero or more set bits from the binary representation of $b$ (source).

(27 Feb '18, 23:00) meooow ♦6★
1

I too had got the first observation, that its required to calculate for hard disk 1 only. Noticed the pattern too, but couldn't formulate it in terms of code. Had the idea of binary search, but messed up.

PS: Same pattern of bits occurs in problem codechef.com/SEPT17/problems/WEASELTX

(27 Feb '18, 23:45) taran_14076★

The ranking will be similar to ACM ICPC and the penalty time for wrong submission has been made 10 minutes for the contest.

link

answered 27 Feb '18, 11:59

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

You can find the intended solutions here. I will be uploading the short editorials in a while. Detailed ones will be put up on codechef discuss forum by tomorrow. Hope you all enjoyed the contest.

Any feedback regarding the clarity of problems, time limits, test data being weak/strong etc?

link

answered 27 Feb '18, 22:34

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

For each test case, output a single line containing two space seperated integers a and b such that a / b = Pmax - the maximum possible power achievable after transformation and gcd(a,b) = 1

I don't get this part. Can anyone explain?

link

answered 27 Feb '18, 22:57

ashudeshwal's gravatar image

3★ashudeshwal
302
accept rate: 0%

2

For example after simplifying the function, you find the value as 12/10, So you should print the answer as "6 5".

(27 Feb '18, 22:58) likecs6★

I get it. Thanks

(27 Feb '18, 23:08) ashudeshwal3★

In problem 2

I considered lsum(count of letter) and rsum(-count of numbers + (sum of numbers/K))

So,For each i since sum += 1(count of letter) or -1(count of number) +(val(s[i])/k)

int num = (int)a[i]-96;
if(num/k - 1 > 1)
   lsum += num/k - 1;
else 
   rsum++;

What is wrong with this code. Thanks in advance.

link

answered 27 Feb '18, 23:46

garrykevin's gravatar image

2★garrykevin
263
accept rate: 33%

edited 27 Feb '18, 23:48

you are considering floor division, while the problem requires float division.

Initial answer N/1.

change your condition to (num > 2K) and add (num/K - 2)freq[i] to answer. Handle fractions instead of taking floor division.

(27 Feb '18, 23:52) taran_14076★

I have used double k to do float division.I understand your logic,But what is wrong with my logic. My idea is to either choose letter or convert to number. The cost of one letter is 1 and cost of one number is (-1)+(num/k),so my condition is num/k - 1(cost of number) > 1(cost of one letter) then convert to number else add 1 to sum

(28 Feb '18, 00:36) garrykevin2★

@garrykevin, you are using float arithmetic here which is causing the issue, consider the following testcase where k is 3 and the string is 'j'. since replacing j with 10 gives us benefit we should replace it. Now your solution stores it in rsum in the form 2.333333333 (assuming precision of 9 digits) when you convert it back it converts back to 2333333333/1000000000 though the precise answer should be 7/3 (as the actual value is 2.33 repeating). You are loosing precision while storing it as double. Instead store integer numerator and denominators separately.

(28 Feb '18, 02:39) diveshuttam4★

In problem 1 Can we solve by checking the frequency of each number from 1 to 100 and if frequency of every element is even then there will be "draw" otherwise "cyborg" will win?

OR can anyone can provide testcases were this solution fails https://www.codechef.com/viewsolution/17561707

link

answered 28 Feb '18, 01:31

akash_321's gravatar image

4★akash_321
765
accept rate: 0%

edited 28 Feb '18, 01:42

1

Yes we can, though there is a small problem with your solution, the constraints state that 'A[i][j]' can also be '0' since 0 doesn't count towards the score, its frequency doesn't matter, but you are considering that in your solution. A small change in the last loop of your solution to ignore the frequency of zero gets an ac. https://www.codechef.com/viewsolution/17561899

(28 Feb '18, 02:04) diveshuttam4★

thanks mate.

(28 Feb '18, 12:52) akash_3214★

In problem2. "Geno" can never win.. that's cool observation

link

answered 28 Feb '18, 10:32

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

Sorry for the delays, the editorials are given in below links:

  1. ICL1801
  2. ICL1802
  3. ICL1803
  4. ICL1804
  5. ICL1805
link

answered 03 Mar '18, 19:21

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 03 Mar '18, 20:32

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,285
×95
×29

question asked: 27 Feb '18, 11:16

question was seen: 3,465 times

last updated: 03 Mar '18, 20:32