Hello Everyone!
I am honored to invite you all to August Circuits '19, an exciting contest with 8 amazing problems (7 algorithmic problems and 1 approximation problem). The contest will start on August 24, 15:30 UTC and will run for 7 days.
This time, the problems were prepared by me and imAnik (Anik Sarker). Thanks to Arpa (AmirReza PoorAkhavan) for testing the problems and helping us prepare the problems.
To make the challenge more interesting, problems added to the contest in this order:
- Day 0: Easy, Easy-Medium, Approximation.
- Day 1: Medium, Medium.
- Day 4: Medium-Hard, Medium-Hard.
- Day 6: Hard
As usual, there will be some nice prizes for the top five competitors:
- First place: $100 Amazon gift card + HE t-shirt.
- Second place: $75 Amazon gift card + HE t-shirt.
- Third place: $50 Amazon gift card + HE t-shirt.
- Fourth place: HE t-shirt.
- Fifth place: HE t-shirt.
Hope to see you at the scoreboard!
Good Luck & Have Fun.
Update 1 : Contest has ended. Now you can discuss the solutions. Editorials are ready. We have asked the hackerearth team to upload them. Please be patient.
Update 2 : As it's taking some time to upload the editorial to hackerearth, I am uploading it here. Please have a look and feel free to describe your approach.
Auto comment: topic has been updated by TheFallenOne (previous revision, new revision, compare).
Auto comment: topic has been updated by TheFallenOne (previous revision, new revision, compare).
How to solve Constructive Buildings?
The main observation is that, in a string of n length, there is atmost n distinct palindromes.
So you can find all the distinct palindromes of all the strings and their count in every string using plaindromic tree.
How to solve Moving People ?
The main observation is that after any number of moves, the present people in the grid forms a rectangle. So we can keep track of this rectangle and answer every query in O(1).
How to solve GCD problem?
Try to process the queries offline in non-increasing order of their L.
Another observation is that, there is at most log(A[i]) distinct G.C.D values for F(i,j) for all the subarrays starting from ith position.
You will find better explanation in the editorial. Please wait some time.
How to solve permutations?
Please see the editorial in the post for now.
Auto comment: topic has been updated by TheFallenOne (previous revision, new revision, compare).
Thanks a lot for the editorials.
But, at least for me, editorial for GCD Promblem and Permutation are not understandable. How do you sum up the huge numbers of F(i,j) in time? What type is this "magic" array end, why? How to "Build a segment tree and keep a trie in each node."? Even how to build a trie from an array of int? I know a trie as a strcture to store strings.
"We need to find K − mex in the union of the tries of these nodes." How, in time?
Since I didn't knew about palindromic tree, the explanations to Constructing Building where helpfull to me.
Exactly. I am facing the same issues. Can you please elaborate your editorials a bit :)
As I said in the editorial, when we are xth position, we try to find all the F(i,j) values of all the sub-arrays starting from xth position.
There are atmost log2(ara[x]) distinct gcd values for all the sub-array's F(i,j) value, starting at xth position.Try to understand this observation.
I would suggest you to look at the code. If there is any more confusion, feel free to comment.
Amd for problem Permutation, We will build a segment tree where each node contains a binary trie of all the number in it's range.
An element can be in log(n) nodes in a segment tree.And for every ith element log(A[i]) new nodes will be created in it's corresponding tries.So time and memory complexity : O(n*logn*log( max(A[i])).
If you are not familiar with keeping tries in segment tree have a look at this problem.
Sorry, I completly do not get how that "segment tree where each node contains a binary trie" works. And google does not tell me where to find info about it. The problem link above is... well, a link to a problem. I dont find any tutorial there.
Edit: After some more research I think I understood some parts. Such a trie is simply a binary tree on the single bits of the numbers. (I assume it is wise to use the lowest bit on root node, but not sure about that). However, in the segment tree we maintain for any node such a trie for the numbers in that part of the array that one node stands for. I think it is not hard to find the k-th entry within one such binary trie.
But we need to find the k-th number within a list of binary tries. How to do that?
but what doesn't make sense about this solution is that, because the tries are separated into the nodes of the segment tree, there is no way of ensuring the relative order of elements in different tries...
In the editorial he writes
"To solve our current problem, instead of beginning from a single root, we travel from all the O(log n) trie roots in parallel. In each step, we check if the sum of missing elements in ‘0’ edge child of all the trie is equal or greater than K, then we move to that ‘0’ edge child in all the trie. Otherwise, we move to the ‘1’ edge child."
So there is some way to do that. But I still did not get how.
Also The process of finding K-mex in the union of the tries of these nodes are explained in the editorial.
I solved it using search buckets..in about O(N*sqrt(NlogN)*logN) however it is much faster than that due to cache efficiency. Search Bucket
https://codeforces.net/blog/entry/53925 here mobius inversion, can we solve gcd problem by modifying 2nd question equation and maintaining count of each array element.so we could convert n^2 to n and then using square root decomposition to solve for the queries.
I don't think so. In that example, the values are in a continuous range. But here the values are random.
we can work on continuous range, by maintaining count of array elements.I am not so sure about that, just a thought, would it be feasible.