### pritishn's blog

By pritishn, 5 weeks ago,

Guys please share your approaches for the problems you solved. How many did you guys solve?

Problem 1

There are N cities numbered from 1 to N connected by M bidirectional roads. A concert is going to be held in each city and i_th city concert costs A[i] amount. Travelling through the roads also costs some amount given.

For each city i from 1 to N : find the minimum amount a person from city i has to spend to visit a concert in any of the city and come back to own city.
It may not be guarenteed that each city is reachable from other city.

N,M<=10^5

=====================================
Problem 2

Given rooted tree of N vertices from 1 to N. Every vertex must not have same color as it's p-th ancestor. Every vertex must have either red or green color. Calculate the number of ways to color the tree.

N,p<=10^5

=====================================

Problem 3

You are going to make a necklace of N beads using K different colored beads.
There are unlimited beads of each color.
You need to find the expected value of number of distinct colors used, if every necklace is equiprobable to be made.
Two necklaces are considered same if after some rotation they are identical.
You need to find this value for each N from 1 to M, modulo 1e9+7.

K,M<=10^5

=====================================
Problem 4

Find lexicographically smallest permutation of 1 to N where there are exactly B good indices.
A good index i is one where the element at this index is greater than all it's previous elements(at indices<i).

N,B<=10^5

=====================================
Problem 5

Given an array of length N. You can change any number to anything else. Calculate the minimum number of changes needed to make the array such that every subarray of size K will have Bitwise Xor = 0.

N,K<=10000
A[i]<=2^10-1

=====================================
Problem 6

Indumati has been given an array of A ones and B zeroes.
One operation is:
-> Select any C elements from the array and delete them from the array and append their average (in irreducable fraction from) to the array.
It's guarenteed that A+B-C is multiple of C-1.
Indumati repeats this operation until only 1 number is remaining.

Your task is to calculate the number of distinct values the fraction can take, modulo 1e9+7.

A,B<=2000
2<=C<=2000

=====================================

• +143

 » 5 weeks ago, # |   +9 1st question: Simply double the length of each pre-existing roads. And add N new nodes where ith node is connected with ith city with road distance A[i] . Use multi-source-dikstra and get the answer.
•  » » 5 weeks ago, # ^ |   +1 could you elaborate a bit on the Use multi-source-dikstra and get the answer part?
•  » » » 5 weeks ago, # ^ |   +5 Initial sources for the multi-source-bfs are the newly created nodes ( concert nodes which have distance of A[i] from corresponding city).Other edges/roads have lengths multiplied by 2. Because if we travel by a road, we must also come back. I guess its clear now?
•  » » » » 5 weeks ago, # ^ |   0 got it, thanks!
•  » » » » 5 weeks ago, # ^ |   0 So basically for the answer you are calculating $\forall \ i \in [1,n], \ ans[\text{node that reached i}] = dis[i]$
•  » » » » 5 weeks ago, # ^ |   0 Can you give a prediction of number of problems solved to rank prediction ?
•  » » 5 weeks ago, # ^ |   +12 I solved it using normal djikstra. The answer for city with minimum cost to have a concert will be the city itself. Then we update the answer for all its neighbours similar to djikstra. Initally the answer for all vertices will be the cost of their concert itself
•  » » » 5 weeks ago, # ^ |   0 yeah, i realized later that it's not needed to make extra nodes. XD
•  » » » » 5 weeks ago, # ^ |   0 can you explain how to solve xor question
•  » » » 5 weeks ago, # ^ |   +1 But wouldn't that give shortest cost of all the nodes from the initial minimum cost concert city.. Can u please explain a bit more.. Thanks a lot
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +19 Okay,Let ans[i] = answer for city iarr[i] = cost of having a concert in city iweight[i][j] = weight of edge between i and j Firstly, we need to observe thatans[i] = min(arr[i],ans[j]+2*weight[i][j]) for all j such that there is a edge between i and j,which means that we can either attend our own concert or go to any neighbour j attend some concert from that city and comeback, which is same as the ans[j] with added cost for round trip to that city.But we cannot do this directly, we need to process the cities in a particular order. And another important observation will be that if c is the city with minimum cost to host a concert than ans[c] = arr[c] bcoz going to some other city will definitely increase the cost (try to see this with some test cases).Now since we know the answer for city c than we can update the answer for all the neighbours j with ans[j] = min(ans[j],2*weight[c][j]+ans[c]).We will initialize ans[i] = arr[i] (cost to attend a concert in their own city)Now since the graph is not guaranteed to be connected we will insert all the nodes {ans[i],i} into our set and then similar to djikstra we will remove the vertex with minimum cost and update the answer for all its neighbours.feel free to ask if something is still not clear.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 thanks for the explanation.but i have a doubt that we are doing dijkstra from the source c (the city with the minimum cost) wouldn't that give the shortest cost of all the other node from the source 'c' only..also ans[i] = min(arr[i],ans[j]+2*weight[i][j]) what if there is another edge k such that shotest path is from i-->k-->j and not direct 1-->j.can u please explain me these 2 doubts?
•  » » » » » » 5 weeks ago, # ^ |   +1 For the first doubt : We are trying to process the cities in the increasing order of their answers, so when we consider node c we try to update the answer for all its neighbours, but it does'nt mean that the shortest path will be from node c only. Let's consider a small graph :n = 3edges(u,v,w) (source,dest,weight) : {1,2,40} , {2,3,2}arr = {2,100,4}Here, c = 1 (city with minimum cost) Initially, ans = {2,100,4}elements in set({ans[i],i}) = {(2,1),(4,3),(100,2)} First we will process 1 and update the value of 2 so ans[2] = min(100,2+2*40) = 82 and erase 1Then process city 3 and again update the value of 2 so ans[2] = min(82,4+2*2) = 8So finally ans = {2,8,4}For node 3 the min ans was from node 2 but not with minimum cost node (c = 1). For your second doubt take a sample test case and try to dry run the algorithm.
•  » » » » » » » 5 weeks ago, # ^ |   +8 Thankyou so much man..Really the community is blessed to have people like you.thanks a lot
•  » » » » » » » » 5 weeks ago, # ^ |   0 Glad I could help :)
•  » » » » » » » » » 4 weeks ago, # ^ |   0 thanks
•  » » » » » 4 weeks ago, # ^ |   0 Sorry for late response, but the cities j which are visited as 'concert' cities by other neighbor cities will always have ans[j] = arr[j] right ?
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Initially ans[i] = arr[i], but after we have processed some cities it's not necessary. Try to dry run a sample test case
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Oh right it is not necessary, for all citiesbut if we have city i--->j(may be multiple cities) ...---->k(endpoint)and k is endpoint then for all k, we can say that ans[k] = arr[k] right ?little confused on this logic..
•  » » » » » » » » 4 weeks ago, # ^ |   0 If i understand your doubt correctly, then no it is also not necessary
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Oh nvm got it forgot about simple counter-examples.I think then it is only guaranteed for isolated nodes and nodes having minimum cost.Thank you for the awesome solution!!
•  » » » » » » » » » 4 weeks ago, # ^ |   0 I think then it is only guaranteed for isolated nodes and nodes having minimum cost.Yes, This is correct. Glad I could help
•  » » 5 weeks ago, # ^ |   +3 Thanks for recommending me to try. I got this one during the contest. xD
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 What I did was: 1: Make a multiset ms of pairs storing {A[v], v} 2: Repeat this until the multiset ms is not empty2.1: Let top be the element at ms.begin(), here curr_vertex = top.second2.2: For every neighboring vertex x of curr_vertex, update A[x] = dist[curr_vertex][x] * 2 + A[curr_vertex], if A[x] < RHS and update the same in the multiset.3: Return the vector AThis approach got me full marks!
•  » » 4 weeks ago, # ^ |   0 I tried to solve it by first creating the MST and then applying DP on this tree to get the values for each node. It turned out to give me a WA. Can someone please explain why this didn't work?
 » 5 weeks ago, # |   +54 Problem A was copied- Link.
•  » » 5 weeks ago, # ^ |   -8 Lol.. I didn't expect this. XD
•  » » » 5 weeks ago, # ^ |   0 Me too. I came to know this after the contest. I tried the same but gave WA.
•  » » 5 weeks ago, # ^ |   -9 Wow, didn't expect this!!
•  » » 5 weeks ago, # ^ |   +23 I solved this 3 days back and was surprised to see the exact same problem XD
•  » » 4 weeks ago, # ^ |   0 Problem 3 was pretty similar to last year's CodeAgon's problem: Link.BTW that last year's problem was also copied from a question at StackExchange xD
 » 5 weeks ago, # |   +12 2nd question : Count all the vertices having depth < B . Answer is 2^(number of all such nodes)
•  » » 4 weeks ago, # ^ |   0 Can you please elobrate. How did the answer came?
 » 5 weeks ago, # | ← Rev. 4 →   +17 I solved 4 problems(1-4)Problem 2 : For each node with depth < p, it is valid to color them either Red/Blue, for the rest of the nodes colors are determined by the nodes with depth < pProblem 3 : Using linearity of expectation, fix a color find the total number of valid necklaces which have atleast one bead with this color, finding ways is straight-forward application of Burnside LemmaProblem 4 : Use this construction — (1, 2, 3,..,b-1, n, b, b+1,....,n-1) My sad story — Wasted more than 1.5 hours on P2 because dfs doesn't work, Wasted another 1.5 hour on P3 due to a stupid bug in Eulier totient function
•  » » 5 weeks ago, # ^ |   0 Could you please elaborate on the third problem ?
•  » » 5 weeks ago, # ^ |   0 I used DFS for problem 2!!
•  » » » 5 weeks ago, # ^ |   +3 I keep getting MLE until I switched to bfs
•  » » » » 5 weeks ago, # ^ |   0 Same.
•  » » » » » 5 weeks ago, # ^ |   0 This gave me an MLE. const int N = 1e5+5; vector adj[N]; But this one worked without any error. vector > adj; int fun(){ adj.assign(n+1, vector ()); } 
•  » » » » 5 weeks ago, # ^ |   +5 When I created a global adjacency list and implemented DFS, it gives me MLE, but it got accepted when I created the adjacency list in the solution function and passed it by the 'call by reference'. I think this is due to test cases.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I used the global adjacency list to implement dfs and my solution passed easily, but here many people got MLE, weird..
•  » » » » » » 5 weeks ago, # ^ |   0 they didnt cleared the adjacency list after using it
•  » » » » 5 weeks ago, # ^ |   0 Same bruh, but later i realised I just had to do a[i].clear() for all i till n in the start of function
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I too got MLE when I was performing DFS. It was a simple bug though that caused my code to go into an infinite loop. Instead of checking if the current child is the parent of the current node, I was checking if current node was a parent of itself (stupid thing to do). I fixed it and it worked. And FIY, the adjacency list was declared globally with a size of $10^5$. But technically it should have been a TLE. I guess the infinite loop caused the stack to fill up rapidly and thus the judge gave a MLE.
•  » » 5 weeks ago, # ^ |   +7 Could you tell how you optimized your approach for problem 3, As we have to calculate for every n from (1 to m), and for every n we have to traverse n times
•  » » » 5 weeks ago, # ^ |   +8 For each $n$ we only require $phi(d)$ where $d|n$ and some powers of $k$ and $k-1$ which can be precalculated, Now we can just perform sieve like process
•  » » » » 5 weeks ago, # ^ |   0 Can you please elaborate your solution?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 You need to traverse on number of divisors of $n$ whose sum for $n = 1..M$ is $O(M*log(M))$, overall complexity being $O(M*log^2(M))$
•  » » 5 weeks ago, # ^ |   0 For the third problem, do you have the derivation for the formula for k-aray necklace of size n?
•  » » » 5 weeks ago, # ^ |   +12 Study Burnside Lemma and Pólya enumeration theorem
•  » » » 5 weeks ago, # ^ |   -14 I don't know much about the problem, but during contest, this was little helpful to read.link
•  » » 4 weeks ago, # ^ |   +23 I received a few messages and my solution to P3 was a bit different. So, let me leave it here. If the problem was on a random array instead of necklace, the answer is easy to derive. Its (n^k-(n-1)^k)/(n^k) where k is size of array. Now, answer of random array is basically sum of answer over all divisors for random aperiodic arrays. So, we apply mobius inversion and get answer for random aperiodic array. Now, a necklace is basically composed of a few random aperiodic arrays. So, we use these and we are done. Overall complexity is O(N(logN+logK))
•  » » » 3 weeks ago, # ^ |   0 Could you share your code?
 » 5 weeks ago, # |   +1 4th Just put Max number at Bth position.
•  » » 5 weeks ago, # ^ |   +88 Even better. Just click on that "See Expected Output."
 » 5 weeks ago, # | ← Rev. 2 →   -22 My previous experience with CodeAgon has been very deadly like last year so I didn't give it this year thinking a great waste of time. One of my seniors (Orange on Codeforces) was selected on 6/6 and one of the seniors (Violet on Codeforces) was not selected on 5/6 and I sat for the intern test and was blown away!!..CodeAgon was I think is meant for 2000+ rated. You can see the selects of last year, most were 2200+ rated
•  » » 5 weeks ago, # ^ |   +36 Not getting shortlisted does not mean it was a waste of time
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   -24 I agree with you, you can always do it for learning but whenever you are giving a test with the intention of getting an interview opportunity you should always keep this in mind that you might also have prepared for some other good company interviews. DeShaw pays more than this and has hell easy procedure than this..Just to give you an example. What if I say you stand a much greater chance to get selected in Deshaw, still will you do it only for learning?
 » 5 weeks ago, # |   0 I solved 4, how many did you solve? also this was my first codeagon so do you know what is the cutoff?
 » 5 weeks ago, # |   +11 Short editorial for Concert. 1. Ans for the city X with the cheapest concert is same as cost of concert in X. 2. For all cities C which are neibhours of the cheapest city update the cost of concert as: Minimum of: a) actual cost of concert in city C. b) 2 * (cost of going to X from C) + cost of concert in X. 3. Delete X from the graph and goto 1. 
•  » » 5 weeks ago, # ^ |   +5 I did exactly the same thing :)
 » 5 weeks ago, # |   +3 I solved $3$ problems The first problem. I doubled the weight of each edge and then conducted multiple source BFS to find out the closest concert for each city. The second problem. The entire tree is uniquely determined by the colouring of vertices who’s level is at most $P$. Count the number of such vertices and raise $2$ to that power. The fourth problem. $[1,2,... B - 1, A, B, B + 1, ... A - 1]$
•  » » 5 weeks ago, # ^ |   0 What and where is 'A' in fourth?
•  » » » 5 weeks ago, # ^ |   +1 size of array
•  » » » » 5 weeks ago, # ^ |   0 One more doubt: What about i=0? is it good or bad?
•  » » » » » 5 weeks ago, # ^ |   +3 i = 0 is always good index
•  » » » » » » 5 weeks ago, # ^ |   0 Okay, thanks
 » 5 weeks ago, # |   +3 Solved only 2, I put a lotttt of time on problem 5th, but couldn't converge to an answer.
•  » » 5 weeks ago, # ^ |   0 Same here
 » 5 weeks ago, # |   +21 Do we get a ranklist?
 » 5 weeks ago, # | ← Rev. 3 →   +10 Can anyone share approach for F problem ? We were given an array A and some value 1<=B<=N , where N is size of array ( 1<=N<=10000) we need to find minimum number of changes we need to make in order to make XOR of all segment (continuous subarray) of size B equal to zero .
•  » » 4 weeks ago, # ^ |   0 My approach was let suppose we have one array 1 2 3 4 so basically if we count how many subarrays we have of size k where subsequences of equal partition exist, mean let k=3 we have 1 2 3 and 2 3 4 two subarrays. Now consider 1 2 3 we can divide it into two sets having equal sum, if we were able to do so then this subarray have xor 0 and in 2 3 4, we cannot divide it into two sets having equal sum so we cannot get xor 0 for that subarray of size k.so I count no of subarrays which cannot have an equal partition. and return the count and got TLE after getting the correct answer. I use the sliding window technique with an equal partition algorithm(uses DP for this).complexity — O((N-k)*N*N) got tle due to that much complexity.Can someone please help me where I am wrong either I take the question in the wrong direction or only need some optimization for acceptance?
 » 5 weeks ago, # |   +19 How to solve problem E, I wasted more than an hour but couldn't solve it :/
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 .
 » 5 weeks ago, # |   +18 Just for the getting approximation of rank, how many of you solved 5 or more.
 » 5 weeks ago, # |   +28 Do anyone how to solve problem F.
 » 5 weeks ago, # |   +40 For problem 3:Let F(n,k) denote the number of distinct necklaces of n beads that can be made with at most k colours.Let $X_i$ be an Indicator Random variable which is equal to 1 if the $i^{th}$ colour is included in a necklace. So for a given necklace number of distinct colours = $\sum_{i=1}^{i=k}{X_i}$.We need to calculate $E[\sum_{i=1}^{i=k}{X_i}] = \sum_{i=1}^{i=k}{E(X_i)} = \sum_{i=1}^{i=k}{P(X_i=1)} = k*P(X_1 = 1)$.Now $P(X_1 = 0) = \frac{F(n,k-1)}{F(n,k)}$$Ans = k * (1 - \frac{F(n,k-1)}{F(n,k)})$The value of F(n,k) can be be found here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)
•  » » 5 weeks ago, # ^ |   0 $\sum_{i=1}^{i=k}{P(X_i=1)} = k*P(X_1 = 1)$What happened in this step??
•  » » » 5 weeks ago, # ^ |   +5 $P(X_i = 1) = P(X_j = 1)$ for any i,j because the total no of necklaces that include the colour i = total no of necklaces that include the colour j as both colours are equally likely.
•  » » 5 weeks ago, # ^ |   0 What does E(x) specifies?
•  » » » 4 weeks ago, # ^ |   0 The expected value that the random variable X will take :)
 » 5 weeks ago, # | ← Rev. 2 →   +19 How to optimize the 5th(xor problem) problem? I got 255/500 points after implementing n*1024 dp with 1024 extra iterations for each state.
•  » » 5 weeks ago, # ^ |   +8 Instead of iterating from 0 to 1023 just iterate on given bucket which contains element which are present at same remainder index.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 What if we have different elements at each index?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Did not get your point.
•  » » » » » 5 weeks ago, # ^ |   +3 You are saying that just iterate over those elements whose index's remainder with B is same? Correct me if i m wrong.
•  » » » » » » 5 weeks ago, # ^ |   0 Yeah i implemented that way but it gave 250 points though.
•  » » 5 weeks ago, # ^ |   0 Hey, will you please describe what was your verdict more precisely? I used the same approach, but I am not sure if I got those 255 points.
•  » » » 5 weeks ago, # ^ |   +3 I was getting tle and green tick for correctness.
•  » » 5 weeks ago, # ^ |   +22 Notice that you don't have to iterate through all 1024 numbers per state. SpoilerSay you have to calculate $dp[idx][currXor]$, take the set of elements present in $idx, idx + k, idx + 2k...$ Now in $idx$ if you are putting a value which is not present in this set. Then you might as well leave it blank for now and finally after filling everything else greedily come back to $idx$ and put a value which will make the xor to be 0. So it makes sense to iterate through the elements that are present only in the set. Or leave it blank.
•  » » » 5 weeks ago, # ^ |   0 What will be the worst case complexity for this approach i.e. when we have all the elements different?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +5 I think it will be $n*1024$ only.Because total no of states = $k*1024$ as array will be k-periodic and for each state we will be making at most $n/k$ iterations
•  » » » 5 weeks ago, # ^ |   0 Actually I did the exact same thing.My assumption : If say at the ith position, none of the elements rom the set can be placed, then i can always place xor(A[1]...A[K-1]) ^ A[i] making the xor of 1st K elements 0. Please correct me if I am wrong.If my assumption is true, then can I add xor(A[1]...A[K-1]) ^ A[i] in the set for thr ith position as well ? If no, then can you kindly say why
•  » » » » 5 weeks ago, # ^ |   0 I am not sure if I understood your question properly. There can be multiple values for A[1], A[2], ... A[K-1] right? which ones would you be choosing for adding in the ith set?
•  » » » 5 weeks ago, # ^ |   0 could you explain about leaving blank, cause I might leave blanks for multiple indices, and at the end I have to check if xor is zero or not and while returning I will add up costs...
•  » » » » 4 weeks ago, # ^ |   0 I think you need to leave atmost one bucket blank as it would be sufficient to make xor to be 0.
•  » » 5 weeks ago, # ^ |   -24 Actually, you don't need dp at all, just a normal window sliding would be sufficient.
•  » » » 5 weeks ago, # ^ |   0 How sliding window?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   -28 I'm not really good at explaining stuff, but I'll give it a try.Notice that the final array has to be periodic with a period of k. This means that For a fixed i, all A[i+j*k] (for every j in 0 to i+j*k
•  » » » » » 5 weeks ago, # ^ |   0 This doesn't ensure that the xor of the k-length-window is zero, right?
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -27 It does actually. Once you have the most frequent elements pre-calculated, all you have to do is iterate over all i in(0,k) and just assume that you are going to change this number to make the xor zero. Calculate the result for all i in (0,k) and take the minimum.
•  » » » » » » » 5 weeks ago, # ^ |   0 I had the same idea. But I don't think this is going to give you the minimum answer always. I am not sure.
•  » » » » » 5 weeks ago, # ^ |   +3 there can be multiple frequent elements
•  » » » » » 5 weeks ago, # ^ |   0 Your approach will be wrong when there is same frequency of multiple values.I did the same thing. But it didn't showed any partial points. Can someone pls tell that where did they showed partial points?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Same, I implemented it in O(2048*k) but got 250/500 only and k was <=10000. No idea why it didn't pass
•  » » 5 weeks ago, # ^ |   0 I solved it with some greedy technique and got 250 points.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 5th question(XOR problem) The question can be solved using prefix and suffix dp of 1024*kWhere pre[i][j] denotes minimum no. of changes to get to ith index with resultant xor of prefix j similarly suf[i][j] denotes minimum no. of changes to get to ith index with resultant xor of suffix jNow the key is noting that we will never change two different index entirely i.e. we will take the values already present at other locations as it is with possible exception of at most 1 place.Using this fact while transition during precomp we will only have (no. of distinct values occurring at ith position) * 1024 transitionsSince summation(no. of distinct values at ith position) <= n The complexity is n*1024Final step getting the answer: for each index i lets pre_j be the value where pre[i-1] if minimum and suf_j be the value where suf[i+1] is minimum, we want to set i'th position as pre_j^suf_j the answer would be min over all valid i's pre[i-1][pre_j] + suf[i+1][suf_j] + cost of making ith index pre_j^suf_j
 » 5 weeks ago, # |   +3 pritishn, update the blog with the concise problem statements. It will be helpful for the ones who have not participated.
•  » » 5 weeks ago, # ^ |   0 Ok
 » 5 weeks ago, # | ← Rev. 2 →   +3 1) Can someone rate the problems in terms of CF difficulty ? 2) Also was there no penalty on wrong submissions ?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +7 This guy noticed that problem A is copiedThese are my guesses. This could be wrong also.1. 2000 (same problem https://codeforces.com/contest/938/problem/D)2. 17004. 15005. 2200
 » 5 weeks ago, # |   0 has anybody solved last question -6 ???
•  » » 5 weeks ago, # ^ |   +8 afaik rahul dugar solved all, but I am not pinging him XD
•  » » » 5 weeks ago, # ^ |   +7 Why won't you ping him? XDamnesiac_dusk , did you solve all 6?
•  » » » » 5 weeks ago, # ^ |   +69 Yes, afaik kal013 also solved all.
•  » » » » » 5 weeks ago, # ^ |   +13 Please enlighten with your solution to F. I was clueless even after spending an hour.
•  » » » » » » 5 weeks ago, # ^ |   +48 I did dp[a][b] which basically represents the answer with the condition that no c zeros or c ones can be merged. Now, let us try to find the answer to it, we are basically forming some n-digit base c fraction, now at each digit of the fraction we will assign some 0s and 1s there which will represent the digit there let us say we assigned u 0s and v 1s then u+v==c-1. And we can call dp[a-i][b-(c-1-i)] to compute this value. Dp[a][b] is initialized by 1 wherever a+b==c and a>0 and b>0. Now, let us compute answer to original problem we can merge c 0s or 1s at whatever level and it results in same thing. So, we just do sum dp[A-i*k][B-j*k] where k=c-1 for all valid values and this is our answer. Although there seems to be A*B states and O(C) transition actually only states where (A+B-1)%(C-1)==0 will be relevant. So, final complexity is O(A*B(+C or smth like that maybe))
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 How many did you solve?AGRU
•  » » » » 5 weeks ago, # ^ |   0 Not enough to tell publicly in this blog XD :(
 » 5 weeks ago, # | ← Rev. 2 →   0 Can we do A using the rerooting technique? If not, I wonder why it doesn't work? I tried it, but failed on the main tests.
•  » » 5 weeks ago, # ^ |   0 Can you elaborate upon your solution? And you mean this technique?
•  » » » 5 weeks ago, # ^ |   0 Yeah! I calculated the answer for each connected component separately. For each of them:I once called dfs on any node in it and calculated the answer for that root node(say x) by:dp[root] = min(cost[root], dfs(child)+2*edgeWeight.Then I call a second dfs function by changing the root to the child, and filling answers for them.
•  » » » » 5 weeks ago, # ^ |   0 It doesn't work because it's a graph and not a tree. Let's say A-B and A-C denote the optimal paths from A to B and C respectively. When we move from A to B, I can't claim that B-C = B-A + A-C, and that's because it's a graph (there might be a shorter path that doesn't involve A at all).
•  » » » » » 5 weeks ago, # ^ |   0 Thanks, I understood the mistake now :)PS: My mistake was similar to this
•  » » » » » 5 weeks ago, # ^ |   0 I did the same approach and it works. XD
•  » » » » » » 5 weeks ago, # ^ |   0 atishay127 Can you please explain, because mine failed on main tests?
•  » » » » » » » 5 weeks ago, # ^ |   0 Also there were cycles in the graph..
 » 5 weeks ago, # |   0 Did anyone solve Problem E ?? What is the approach for it
 » 5 weeks ago, # |   0 Can anyone explain how to solve 5th question(XOR) ?
•  » » 4 weeks ago, # ^ |   +3 elements k distance apart must be same , for each number from 0,1,2....k-1 I made a frequency counter of numbers present at that index%kthan used bag like DP ,use old States to compute new one ,each state hold the information of Dp[current xor][cost to get here][cost to get to zero from here]iterate over all i from 0,1...k-1 use frequency counter to compute how much it will cost to move from one state to other .
•  » » » 4 weeks ago, # ^ |   0 should we keep index also as state ? What will be the transitions ?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 you are at some index 0<=I
•  » » » » » 4 weeks ago, # ^ |   0 Thanks.!
 » 5 weeks ago, # |   +15 5th ques can be solved using simples obs, array should be periodic with periodicity k.use dp to check answer without changing any element,if we have to change, then it is optimal to change only one among i from 1 to k.As that element can simply be xor of all other elements.This can be calculated in linear time using freq array.
•  » » 5 weeks ago, # ^ |   0 Did your solution got accepted, I also tried something like this but was unable to get it fully accepted.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I got correct answer upon submitting,did u take min of both answer? dp and greedy ?
•  » » » » 5 weeks ago, # ^ |   0 Yeah please explain the dp transitions. I was unable to think of any efficient dp transition.
•  » » » » » 5 weeks ago, # ^ |   0 only first k elements matter, ith element belongs to imodk bucket.Only one element from each bucket should be selected, and xor of all selected element should be zero. So standard bit masking dp,calc the cost of choosing an element in a bucket, i.e rest of elements in the bucket shud become chosen element,so freq array can be used.dp state wud be bucket number and xor so far.
•  » » » » » » 5 weeks ago, # ^ |   0 What are you referring to as "bucket" ?
•  » » » » » » » 5 weeks ago, # ^ |   0 All the elements belonging to same i%k value.
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 element with index i is put into bucket with index imodk, there are k buckets with bucket id from 0 to k-1
•  » » » » » » » » 4 weeks ago, # ^ |   -6 That's what I did, but it seems bruteforce + prefix sum to me, not dp.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » » » 5 weeks ago, # ^ |   0 I have not heard abt it
•  » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 How are you calculating the cost for each bucket? 7,31,7 (Bucket 0) 29,16,16,16(Bucket 1) 26,16,24,16(Bucket 2) 16,24,24(Bucket 3) 8,24,0(Bucket 4)
•  » » » » » » » » » 5 weeks ago, # ^ |   0 say I choose 7 from bucket 0 then all other elements should change to 7, that will be the cost(1), it can be implemented with freq array of map. Insertion will be like freq[i%k][a[i]]++
•  » » » » » » 5 weeks ago, # ^ |   0 What all values are possible for the ith bucket? According to your dp state, if you choose all possible values at the ith bucket, then the time complexity would be multiplied with 2^10 ig.
•  » » » » » » » 5 weeks ago, # ^ |   0 There will be k buckets. Dp state would be bucket index, xor so far. Time complexity would be O(N*MAX)
•  » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Why we are not taking values other than (N/K) elements of ith bucket? It may be possible that choosing these values for all K buckets may not lead xor to 0
•  » » » » » » » » » 5 weeks ago, # ^ |   0 yes it may,so we are introducing a new element to a bucket in that case all elements inside the bucket should change.It's enough to change only one bucket as that new element can be constructed as xor of the chosen elements in other buckets.So we can check that for each bucket.For other buckets its optimal to take the maximum occuring element
•  » » 5 weeks ago, # ^ |   0 Oh thanks! Everything makes sense now. I couldn't observe that the final array will be periodic.
•  » » » 4 weeks ago, # ^ |   0 Can you explain the recurrence?
•  » » 5 weeks ago, # ^ |   0 So what was your solution's time complexity. Mine was O(2048*k) but it fetched only 250 points for me. I doubt it may be because I coded in java
•  » » » 5 weeks ago, # ^ |   0 Mine was O(N*Max) and I got correct answer upon submission, how did you do it in O(K*2048)?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 The first observation was that elements at k distances must be same. eg if k=3, then array should be something like ax ay az ax ay az ax.... So we need to choose elements for the first k positions. At each location i
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 yeai get it now,obv it shud give TLE, Every time you are checking 1000 numbers, so complexity wud be K*1023*1023. I think you used recursion dp,if you had implemented iteratively complexity would be evident.
•  » » » » » » 5 weeks ago, # ^ |   0 Hey, is your solution like this -> take the elements present at the current bucket, pass on the xor ,if xor is zero at the end then add up the costs.. Also for every bucket you try to assign a number equal to xor of elements at remaining indices ,and take min of these and one calculated by dp, right??
•  » » 5 weeks ago, # ^ |   +3 I did exactly same but I was getting Output = Expected output + 1 for some cases.
•  » » » 4 weeks ago, # ^ |   0 why did that happen? you got the reason or not? if you know the reason then please, explain. I also faced the same problem.sorry for the bad English.
•  » » 4 weeks ago, # ^ |   0 codingkshatriya Can u please say what are the states of this dp
•  » » » 4 weeks ago, # ^ |   0
 » 5 weeks ago, # |   -46 Why does CodeNation ask so difficult problems? What use do they have solving such weird and stupid problems in real life? Its just plain discrimination for students who don't like CP but are forced to do it. Abomination of a company indeed. I couldn't touch any one problem even.
•  » » 5 weeks ago, # ^ |   0 They pay a really hefty salary too. It's their choice. If they want to take Master+ only, then we can't do anything about that.
•  » » » 5 weeks ago, # ^ |   -82 Being Master+ doesn't mean they are good software engineers also. Probably they can traverse a weird graph in a weird way but they are mostly ignorant of technologies and internals of softwares.
•  » » » » 5 weeks ago, # ^ |   +78 What if they dont need software engineers at all?Probably they just need some cpers to create problems for hiring more cpers next year who inturn can create more problems for hiring more cpers next next year who inturn ......
•  » » » » » 5 weeks ago, # ^ |   +12 Who knows, they probably do that with interns. It's an intern-ception...
•  » » » » » 5 weeks ago, # ^ |   0 Codenation employees did not create problems for this contest.
•  » » » » » » 5 weeks ago, # ^ |   0 Than who made the problems, I am curious about this....did interview bit team made the problems?
•  » » » » » » » 5 weeks ago, # ^ |   +13 I don't know, may be hitman623,drastogi21, enigma27 etc
•  » » » » 5 weeks ago, # ^ |   0 Being Master+ doesn't mean they are bad software developer. You shouldn't generalise things quickly.
•  » » » » 5 weeks ago, # ^ |   0 If some Master+ is not good software engineer material then there is high probability of him becoming a good software engineer in a week than you becoming even average software engineer in a year. SpoilerNa gaand hai na chuchi aur baate kare uchi uchi
 » 5 weeks ago, # |   0 is there any article about how multisource dijkstra works... or can some one explain it plz
•  » » 5 weeks ago, # ^ |   0 Geeksforgeeks Multisource bfs
•  » » » 5 weeks ago, # ^ |   0 i read that but can we do it in the similar way for weighted graph also using djakstra.. can u explain how to use this concept in the first question of codeAgon .... plz plz ... thanks for help
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 We have to run a simple dijkstra but instead of taking only one node in priority queue in the beginning just take all the nodes with their initial distance equal to Ai.
 » 5 weeks ago, # |   0 In problem 5 constraints were n,k<=10000 and ai<=2^10-1
 » 5 weeks ago, # | ← Rev. 2 →   0 Was it a hiring test conducted by codenation?
•  » » 5 weeks ago, # ^ |   +3 Yes!!
 » 5 weeks ago, # |   +8 I heard that a similar hiring event takes place in January as well. What is the difference between the two?
•  » » 5 weeks ago, # ^ |   0 I have heard both are same codenation organise two hiring contest each year one in august and one in january .
•  » » » 5 weeks ago, # ^ |   0 Yes, I know about that. I am asking in terms of difficulty, duration, syllabus, etc.
 » 5 weeks ago, # |   +11 Does anyone have any idea how, where and when the ranklist will be released
•  » » 5 weeks ago, # ^ |   0 I think they might show the rank-list of only top 20 people.
•  » » » 5 weeks ago, # ^ |   +1 So only top 20 people will get a call for interview?
•  » » » » 5 weeks ago, # ^ |   +6 I think people with 4 or more correct solutions get a call for the interview.
 » 5 weeks ago, # |   0 I Didn't understand a single problem during exam
 » 5 weeks ago, # |   0 It was same as Problem No 938D
 » 5 weeks ago, # |   +17 On how many questions does one get an interview call?
 » 5 weeks ago, # |   +3 Any chance of getting an interview on solving 4.5 problems ?
•  » » 5 weeks ago, # ^ |   0 Much more chance than solving 3.5 problems. XD
•  » » » 5 weeks ago, # ^ |   0 you solved 3.5 problems ?
•  » » » » 5 weeks ago, # ^ |   +17 3, I didn't know there was partial points. So i didn't bother to solve 4th problems for 50% score.
•  » » » » » 5 weeks ago, # ^ |   +21 Feel ya man, feel ya.
 » 5 weeks ago, # |   -38 Upvote if solved 5 or more.
•  » » 5 weeks ago, # ^ |   +5 I solved 5, but I accidently downvoted instead. Remember to add 2 to the final tally :p.
•  » » » 5 weeks ago, # ^ |   +14 lol
•  » » 5 weeks ago, # ^ |   +9 Man why downvotes I just wanted a projection of my rank.
 » 5 weeks ago, # |   +2 I still don't understand the first question concert can anyone explain in detail
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Think of it this way. There are concerts in every city, and one person in every city who wants to attend the concert. The concert costs A[i] bucks in each city. Every person, has a choice to either watch the concert in his own city, or travel to any other city and watch it there. You will obviously not watch the concert in your own city, if it is more expensive than travelling to another city + watching concert + coming back. (cost of travelling is weight of edge) So now for each resident, you need to find the minimum cost you have to pay for him to attend any one of the N concerts.
 » 4 weeks ago, # |   +14 Any updates on when the ranklist will be released?
 » 4 weeks ago, # |   0 did anyone solve E? can you tell if this code would work or not?(xor problem) `int n; cin>>n; int k; cin>>k; vector v(n); map mp[k]; for(int i=0;i>v[i]; mp[i%k][v[i]]++; } int dp[k][1000]; int abhitak=0; for(int i=0;i=0 ? dp[i-1][j^(k.first)] : 0) + (cc-k.second)); } dp[i][j]=min(dp[i][j],abhitak+cc); temp=min(temp,dp[i][j]); } abhitak=temp; } cout<
 » 4 weeks ago, # |   +5 I am pretty sure like problem 1 (https://codeforces.com/contest/938/problem/D) problem 5 was also copied from codeforces, I remember seeing that before. will UPD if I find the original statement.
•  » » 4 weeks ago, # ^ |   +8 Yeah, please update if you find the problem 5.
•  » » 3 weeks ago, # ^ |   0 Hmm, its been 12 days and you didn't find it yet.
 » 4 weeks ago, # |   0 Is there any update for the results?