Hello Codeforces Community!
I would like to invite you to CodeChef July Challenge 2017. It begins on the 1st Friday of the month and it will go on for up to 10 days. It would give you a good amount of time to solve the problems.
Joining me on the problem setting panel are: abh1906 (Abhinav Jain), kingofnumbers (Hasan Jaddouh), arjunarul (Arjun Arul), PraveenDhinwa (Praveen Dhinwa), Fekete (Ivan Fekete), adamant (Alexander Kulkov), chemthan (Trung Nguyen), Errichto (Kamil Debowski), AlexandruValeanu (Alexandru Valenu).
Editorialist: Pepe.Chess (Hussain Kara Fallah)
Testers: mgch (Misha Chorniy)
Russian Translator : CherryTree (Sergey Kulik)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
Contest link: https://www.codechef.com/JULY17
Please feel free to provide the feedback about the problems in the comments.
There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page).
You will be provided 10 problems.
On top of all it promises to deliver on an interesting set of algorithmic problems with something for all.
Good Luck! Hope to see you participating!!
How to solve MULDIG? Most of the accepted solutions are too long and unreadable.
I wonder how APRPS had the lowest 100 point solutions — it was just Karatsuba optimization to obvious n^2.
My solution https://www.codechef.com/viewsolution/14581848 falls in the unreadable category, but I will try to explain. The table f consists in a summation table except for the last column that is (0,0,0,..1). The last column serves the purpose to identify whether a cell has the number b-1 or not. First you should convert each of the numbers given in a list of zeros and ones with as many ones as the number (unary representation). This can be done with addition of one and the use of the last column repeatedly, so we identify whether the number in a cell is 0, 1, 2, ..., b-1. Once we have two lists of zeros and ones we proceed to multiply all by all of them. Our table is not a multiplication table of 0,1 by 0,1 but it is possible to use the addition tables of 0,1 0,1 add b-3 and use the last column to get the multiplication table. In this way we find a list of 0 and 1 with as many ones as the product. Finally we have to add back to base b the result. The tricky point is to detect the carries. We use once again the last column to detect them.
How to solve APRPS ? I couldn't find an editorial on that problem.
My solution: https://www.codechef.com/viewsolution/14550993
You can guess or prove that the polynomial will have exactly 2^n roots where for each term you can choose the sign + or -. e.g. for n=2 roots are +sqrt(a)+sqrt(b),+sqrt(a)-sqrt(b),-sqrt(a)+sqrt(b),-sqrt(a)-sqrt(b). Suppose you have found f(x) for first n terms and the (n+1)th term is c. Then it will be simply f(x+sqrt(c))*f(x-sqrt(c)) — such elegance!. Expanding each coefficient of the form of (x+sqrt(c))^k and multiplying can be done naively in O(p^2) where p=2^n. So, we have a solution in O(polynomial multiplication time). We just need to optimize polynomial multiplication since shifting i.e. getting f(x+r) from f(x) can be converted to polynomial multiplication. We could have used FFT if mod was friendly. But it was not. So, I used Karatsuba and it passed in O(p^lg(3)).
Wouldn't expanding
take O(k) time? With 2n - 1 terms in polynomial using n - 1 primes, it turns out to be [k + (k - 2) + (k - 4) + .... + 2] ≈ 22n. Am I missing anything? :(
That's what I meant by convert shifting to multiplication.
Let f(x)=sum(a_i*x^i) and f(x+r)=sum(b_i*x^i). Then b_i = sum(C(k,i)*a_k*r^(k-i)). Now if you multiply two polynomials u and v having coefficients u_k = a_k*k!*r^k and v_k = 1/(n-k)! then its (n+i)th coefficient will be sum(a_k*k!*r^k/(k-i)!) from which you can calculate b_i = (u*v)_(n+i)/(i!*r^i). So, shifting = multiplying u and v.
So, the hardest problem reduces to just "multiply two polynomials in the given time limit" :)
Thanks!
Codechef takes ages to upload editorials unfortunately :(.
If anyone finds a good link to the PSHTTR problem's solution or an unofficial editorial can they please comment it over here. I'd be grateful.
PS- I'm a beginner competitive coder, but after some googling what i've understood was that the solution might consist of LCA. Read some tutorials on LCA understood it, still couldn't solve for 100 points. That's why I'd be really thankful if anyone can upload it tutorial on it. (Official or Unofficial). :')
Here is the official Editorial
Thank You so much!! :D
Can anyone explain me how to solve TWO COINS ?
https://www.codechef.com/JULY17/problems/TWOCOINS
My solution: https://www.codechef.com/viewsolution/14522157
Tree DP: dp(x,p1,p2,c) denotes minimum nodes taken in subtree of node-x where p1 and p2 denotes taken or not taken for parent and parent of parent resp. c can take 3 values — 0=no restriction in subtree of x, 1=has to take-x, 2=has to take x or some child of x. There are 2 cases — whether we take x or not and verify that all conditions are met for x — conditions are at the bottom of my code in comments. Final answer = dp(1,0,0,0) except for n=1 in which case answer = -1. For full cases check my dp function(its just one function). From current function, you have to take <=2 childs with c=1 or 2 and all others 0, so you just calculate upto 2 childs which take minimum values. I can explain more if you want.
Time Complexity = O(n*2*2*3).
Thanks for the help!
It's a shame that solutions for the problems are being posted during the contest and codechef is doing nothing about it. See this link
It's false that we are not doing anything about it. We got to know about the issue during the contest and we have contacted the person and asked him to take the content down. If he doesn't comply, we will contact the authorities of his university. We will take possible legal options as final resort. Rest assured we are very serious about these kind of issues.
I'm sorry for claiming that Codechef is doing nothing about it. Forgive me. It's just that this is not the first time that I have come across such malpractices happening during Codechef contests. Same thing happened during June Long. We thought that it wouldn't happen again. It's quite disheartening when you sit for days in order to solve a problem and total rookies get a better rank than you by cheating. I'm sure that you may have seen the high number of successful submissions for the first few problems, which was way more than there usually is. Moreover, it makes users more agitated when admin doesn't respond to any of the discussions related to this issue on Codechef Discuss. Please try to respond to at least some of the discussions related to this matter on Codechef in order to assure the users that action is being taken.
I hope that Codechef takes immediate and successful action, or Long Contests will lose their credibility and popularity.
Could someone please explain how observation 2 for EXPTREE works: link?
I can't seem to visualize the operation that is used to form the tree with N nodes that has only 1 single-child node.