For the first time in the history of Indian ACM ICPC, a mirror contest will be hosted on CodeChef for Amritapuri regionals at http://www.codechef.com/AMR15MOS.
Time: 21st December 2015 (1000 hrs) to (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your Time zone.
Details: http://www.codechef.com/AMR15MOS/
Registration: It will be a team contest. You need to register your team here
New users please register here
You can view the live blog here and a live scoreboard here.
the scoreboard seems to have become static.Whenever I refresh it always shows "time left:3:49 :53".Is anybody else also facing the same issue? further no updates have been there on the twitter blog for the last 40 minutes whereas previously it was updated every 10 minutes.
Yes, the judge had some issues. The actual contest is now being shifted to CodeChef.
Thanks for the update.
What about live scoreboard?
Stay tuned for a while. An announcement will be made soon!
I can't submit problem AMLPALIN — "submit" button moves me to the very same page.
Also there are only 8 problems in online mirror, while there are 10 of them in live standings.
Thanks, it seems that now everything is fine.
404 error now , cant load page
Onsite: https://www.codechef.com/ACM15AMR
How to solve Magical Matrix?
Check out editorial for this problem: http://mirror.codeforces.com/problemset/problem/364/E
Who Won in the regionals ?
Is there going to be an editorial?
How to solve Similar Strings?
DP[i][j] — number of pairs of similar strings where first string has length i and second string has length j.
Create another table S[i][j] — number of pairs of similar string where first string has length at most i and second string has length at most j (it will be partial sum over DP table).
Now you can say that DP[i][j]=S[i-1][j-1]*25+26 — you can either pick pair of equal strings where first string has length at most i-1 and second string has length at most j-1, and add same letter at the end of both strings (25 comes here because added letter should be different from last letter of these strings), or you can pick pair of strings consisting of single character (26 ways, depending on character you are going to use).
After precomputing both tables you can answer query in O(1) — result will be simply S[N][N].
This problem can also be solved using pure combinatorics.
Notice that for each string of length 'n', the length of reduced string (say 'i') lies in the range from 1 to n (1 <= i <= n).
Number of reduced strings of length 'i' = 26 * (25 ^ (i-1) ). (26 choices for the first character, and 25 for every other position, because every character has to be different from the last — follows from the definition of reduced string).
Number of strings (of length 'n') reducing to a reduced-string of length 'i' is the same as distributing (n-i) identical objects among i boxes = C[(n-i)+i-1][i-1].
Square this value (remember we have to count number of pair of such strings), multiply with 26 * (25 ^ (i-1)) and add to ans[n] for each 1 <= i <= n.
Maintain an accumulated sum array, and you are good to go! Code for reference.
COPRIMES is a great problem :)!
How do you solve it? I can't even think how to solve it if we need to find the answer for a fixed L,R
Step 1: Use standard method of inclusion-exclusion over square-free numbers to solve this problem: http://main.edu.pl/en/archive/pa/2011/lic (this problem is basically equivalent to one query in this problem).
Step 2: We definitely need to solve this problem offline. Assume that K is fixed for all queries. Think about how can you apply Mo's algorithm.
Step 3: Think how can you deal with changing values of K. How can we omit iterating over all square-free numbers for every query?
Can you explain how to do the step 3, in the contest we had got the ideas for the first 2 steps but couldn't come up with any good method for varying k as the time was running out.
Let i be a square-free number and cnt[i] denote the number of elements in current interval which are multiplies of i (you have probably already defined that in step 2). Let cnt_cnts[i] = sum_{cnt[x] = i} mu(x). How can you use that array to retrieve an answer. What is the sum of all values of cnt[i] and how can you use that to make suggested approach fast enough?
Oh, thank you. I got it.
For step 2 I was thinking of the following approach but don't think it is fast enough:
When adding/removing an element 'x' during Mo's algo, for each square free number 'i' that divides 'x', I update cnt[i] i.e. number of numbers divisible by 'i' in the current range.
When adding/removing an element, the answer for the new range will be old_ans +/- C(sum(cnt[i]*mu(i)), k-1) where i is a square free number that divides 'x'
But since a number <= 10^5 can have as many as 64 square free factors, it suggests a worst case complexity of 64*N*sqrt(N)
What is your approach?
You can find a short description + solution in C++ here
So is the final complexity is
?
If yes then why do you say "So we have achieved O(Q*B*2^d) solution here, which won’t pass in time yet"
In the final answer, the complexity is O(Q*B*2^d) additions + O(Q*B) multiplications. In the former solution number of multiplications itself were O(Q*B*2^d).
Generally multiplications are much slower (around ~20 times, maybe) than additions.
Ahh I see, thanks! :)
Step 1: Use standard method of inclusion-exclusion over square-free numbers to solve this problem: http://main.edu.pl/en/archive/pa/2011/lic — Can you explain how to solve this using inclusion exclusion?
http://stackoverflow.com/questions/24807128/counting-coprimes-in-a-sequence
I am the setter of this problem, Thanks :)
Is problem cat and mouse a graph problem + binary search?
Yes. Binary search + bipartite matching.
Great! Now, all I have to do is learn what in good heavens bipartite matching is !! :/
I learnt from this.
http://www.slideshare.net/KuoE0/acmicpc-bipartite-matching
Could you elaborate further?
Sure. We binary search on the answer. Assume that you have some value "limit" (which is the mid in your binary search) which is the maximum distance between any (cat, mouse) pair in your chosen set. Now you have to verify whether it is possible to select a set of animals of size at least k and satisfying max distance <= limit.
Construct the graph as a bipartite one, with cats and mice on either side. For a particular cat vertex, add an edge to each mouse vertex if the distance between them is >= limit. Basically, an edge denotes an incompatible pair (for each edge, you can select atmost one of its endpoints, never both). Now the max no of animals you can select in this case is the maximal independent set of this graph. But MIS = total vertices — min vertex cover.
Total vertices = 2*n and Min vertex cover = max bipartite matching (Konig's theorem)
So for each value of "limit", you check whether it is possible or not and you adjust the low and high of the binary search accordingly.
That was very helpful! Thanks!
Thank you so much! I couldn't have thought this up.
How to solve the problem COINS?
how to solve jump on buildings?? any hints??
Between indices i (starting pt.) and j (2nd point on which we jumped) store the maximum no. of jumps you can make in dp[i][j].
dp[i][j] = ( Hi>Hj ) ? ( 1+dp[j][i-1] ) : 0
Answer for any index i will be max(dp[i][k] where k varies from 1 to n)
To ensure sub state of dp has been calculated for calculating answer for any state ... compute the answer in ascending order of heights of building i.e first compute dp[i][j] for j=1 to n and i as the index of height of smallest building and so on !
Logic for approaching git problem ??
Some hints :
Build trie for simulating the entire directories.
Use dynamic programming
[current_node][0/1]. 0 means the node is excluded, 1 means it is included.Do DP from the leaf.
Ok thanks Will go learn tries and try implementing
Didn't get the rule --"There will be no file — directory conflict. e.g. consider /a/b/c and /a/b. Here b is both a file and a directory."
what should be the ans for foll: (if such a case fits the rule)
stage /a/b stage /a/b/c unstage /a/b/d unstage /a/b/e
Any hints on how to solve the problem: Jump on Buildings. I have O(N^3) solution but that would timeout.
Thanks
If anyone is still searching, it is explained here