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
=====================================
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.
could you elaborate a bit on the Use multi-source-dikstra and get the answer part?
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?
got it, thanks!
So basically for the answer you are calculating
Can you give a prediction of number of problems solved to rank prediction ?
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
yeah, i realized later that it's not needed to make extra nodes. XD
can you explain how to solve xor question
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
Okay,
Let ans[i] = answer for city i
arr[i] = cost of having a concert in city i
weight[i][j] = weight of edge between i and j
Firstly, we need to observe that
ans[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.
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?
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 = 3
edges(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 1
Then process city 3 and again update the value of 2 so ans[2] = min(82,4+2*2) = 8
So 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.
Thankyou so much man..Really the community is blessed to have people like you.thanks a lot
Glad I could help :)
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 ?
Initially ans[i] = arr[i], but after we have processed some cities it's not necessary. Try to dry run a sample test case
Oh right it is not necessary, for all cities
but 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..
If i understand your doubt correctly, then no it is also not necessary
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!!
I think then it is only guaranteed for isolated nodes and nodes having minimum cost.Yes, This is correct. Glad I could help
Thanks for recommending me to try. I got this one during the contest. xD
What I did was: 1: Make a multiset ms of pairs storing {A[v], v}
2: Repeat this until the multiset ms is not empty
2.1: Let top be the element at ms.begin(), here curr_vertex = top.second
2.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 A
This approach got me full marks!
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?
Problem A was copied- Link.
Lol.. I didn't expect this. XD
Me too. I came to know this after the contest. I tried the same but gave WA.
I solved this 3 days back and was surprised to see the exact same problem XD
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
2nd question : Count all the vertices having depth < B . Answer is 2^(number of all such nodes)
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 < p
Problem 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 Lemma
Problem 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
Could you please elaborate on the third problem ?
I used DFS for problem 2!!
I keep getting MLE until I switched to bfs
Same.
This gave me an MLE.
But this one worked without any error.
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.
I used the global adjacency list to implement dfs and my solution passed easily, but here many people got MLE, weird..
they didnt cleared the adjacency list after using it
Same bruh, but later i realised I just had to do a[i].clear() for all i till n in the start of function
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.
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
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
Can you please elaborate your solution?
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))$$$
For the third problem, do you have the derivation for the formula for k-aray necklace of size n?
Study Burnside Lemma and Pólya enumeration theorem
I don't know much about the problem, but during contest, this was little helpful to read.link
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))
Could you share your code?
4th Just put Max number at Bth position.
Even better. Just click on that "See Expected Output."
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
Not getting shortlisted does not mean it was a waste of time
I solved 4, how many did you solve? also this was my first codeagon so do you know what is the cutoff?
Short editorial for Concert.
I did exactly the same thing :)
I solved $$$3$$$ problems
What and where is 'A' in fourth?
size of array
One more doubt: What about i=0? is it good or bad?
i = 0 is always good index
Okay, thanks
Solved only 2, I put a lotttt of time on problem 5th, but couldn't converge to an answer.
Do we get a ranklist?
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 .
How to solve problem E, I wasted more than an hour but couldn't solve it :/
Just for the getting approximation of rank, how many of you solved 5 or more.
Do anyone how to solve problem F.
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)
$$$\sum_{i=1}^{i=k}{P(X_i=1)} = k*P(X_1 = 1)$$$
What happened in this step??
$$$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.
What does
E(x)specifies?The expected value that the random variable X will take :)
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.
Instead of iterating from 0 to 1023 just iterate on given bucket which contains element which are present at same remainder index.
What if we have different elements at each index?
Did not get your point.
You are saying that just iterate over those elements whose index's remainder with B is same? Correct me if i m wrong.
Just wrote this editorial for the problem yesterday, saw it in an interview. Didn't know it was in codagon until saw this blog in recent actions.
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.
I was getting tle and green tick for correctness.
Notice that you don't have to iterate through all 1024 numbers per state.
Say 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.
What will be the worst case complexity for this approach i.e. when we have all the elements different?
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
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
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?
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...
I think you need to leave atmost one bucket blank as it would be sufficient to make xor to be 0.
Actually, you don't need dp at all, just a normal window sliding would be sufficient.
How sliding window?
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<n ) will have the same value. Now just iterate over all these values and find the most frequent value. It will be optimal for us to replace all the other values to this number. Now Do this for all i in (0,k).This should give the min no of replacements needed.
I don't know if this is approach is totally correct or not, but it gave me 252.5 points.
This doesn't ensure that the xor of the k-length-window is zero, right?
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.
I had the same idea. But I don't think this is going to give you the minimum answer always. I am not sure.
there can be multiple frequent elements
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?
Same, I implemented it in O(2048*k) but got 250/500 only and k was <=10000. No idea why it didn't pass
5th question(XOR problem)
The question can be solved using prefix and suffix dp of 1024*k
Where 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 j
Now 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 transitions
Since summation(no. of distinct values at ith position) <= n The complexity is n*1024
Final 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
pritishn, update the blog with the concise problem statements. It will be helpful for the ones who have not participated.
Ok
1) Can someone rate the problems in terms of CF difficulty ?
2) Also was there no penalty on wrong submissions ?
This guy noticed that problem A is copied
These are my guesses. This could be wrong also.
1. 2000 (same problem https://codeforces.net/contest/938/problem/D)
2. 1700
4. 1500
5. 2200
has anybody solved last question -6 ???
afaik rahul dugar solved all, but I am not pinging him XD
Why won't you ping him? XD
amnesiac_dusk , did you solve all 6?
Yes, afaik kal013 also solved all.
Please enlighten with your solution to F. I was clueless even after spending an hour.
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))
How many did you solve?AGRU
Not enough to tell publicly in this blog XD :(
Can we do
Ausing the rerooting technique? If not, I wonder why it doesn't work? I tried it, but failed on the main tests.Can you elaborate upon your solution? And you mean this technique?
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.
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).
Thanks, I understood the mistake now :)
PS: My mistake was similar to this
I did the same approach and it works. XD
atishay127 Can you please explain, because mine failed on main tests?
Can anyone explain how to solve 5th question(XOR) ?
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%k
than 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 .
should we keep index also as state ? What will be the transitions ?
you are at some index 0<=I<k
T is total number of index congruent to I mod k
let frequency of some X be M
old state:(prev_xor,prev_cost,prev_cost_to_0)
new_state:(prev_xor^X,prev_cost+T-M,min(prev_cost_to_0,M))
tuple represents :(current XOR,cost to get here, cost from here to 0)
Thanks.!
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.
Did your solution got accepted, I also tried something like this but was unable to get it fully accepted.
I got correct answer upon submitting,did u take min of both answer? dp and greedy ?
Yeah please explain the dp transitions. I was unable to think of any efficient dp transition.
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.
What are you referring to as "bucket" ?
All the elements belonging to same i%k value.
element with index i is put into bucket with index imodk, there are k buckets with bucket id from 0 to k-1
That's what I did, but it seems bruteforce + prefix sum to me, not dp.
.
I have not heard abt it
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)
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]]++
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.
There will be k buckets. Dp state would be bucket index, xor so far. Time complexity would be O(N*MAX)
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
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
Oh thanks! Everything makes sense now. I couldn't observe that the final array will be periodic.
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
Mine was O(N*Max) and I got correct answer upon submission, how did you do it in O(K*2048)?
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<k, we can place any number between 0 to 2^10-1(2047) and check how many numbers are not equal to that number at location i,i+k,i+2k...<n(this can be done in O(1)). So with simple recursion we have solution with tc-O(2048^k), with memoization it can be reduced to O(2048*k). It gave TLE and fetched me only 250 points
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.
I did exactly same but I was getting
Output = Expected output + 1for some cases.AjaySabarish Can u please say what are the states of this dp
https://codeforces.net/blog/entry/83100?#comment-703355
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.
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.
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.
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 ......
Who knows, they probably do that with interns. It's an intern-ception...
Codenation employees did not create problems for this contest.
Than who made the problems, I am curious about this....did interview bit team made the problems?
I don't know, may be hitman623,drastogi21, Enigma27 etc
is there any article about how multisource dijkstra works... or can some one explain it plz
Geeksforgeeks Multisource bfs
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
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.
In problem 5 constraints were n,k<=10000 and ai<=2^10-1
Was it a hiring test conducted by codenation?
Yes!!
I heard that a similar hiring event takes place in January as well. What is the difference between the two?
I have heard both are same codenation organise two hiring contest each year one in august and one in january .
Yes, I know about that. I am asking in terms of difficulty, duration, syllabus, etc.
Does anyone have any idea how, where and when the ranklist will be released
I think they might show the rank-list of only top 20 people.
So only top 20 people will get a call for interview?
I think people with 4 or more correct solutions get a call for the interview.
On how many questions does one get an interview call?
Any chance of getting an interview on solving 4.5 problems ?
Much more chance than solving 3.5 problems. XD
you solved 3.5 problems ?
3, I didn't know there was partial points. So i didn't bother to solve 4th problems for 50% score.
Feel ya man, feel ya.
Upvote if solved 5 or more.
I solved 5, but I accidently downvoted instead. Remember to add 2 to the final tally :p.
lol
Man why downvotes I just wanted a projection of my rank.
I still don't understand the first question concert can anyone explain in detail
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.
Any updates on when the ranklist will be released?
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<int> v(n); map<int, int> mp[k]; for(int i=0;i<n;i++) {cin>>v[i]; mp[i%k][v[i]]++; } int dp[k][1000]; int abhitak=0; for(int i=0;i<k;i++) { int temp=INT_MAX; for(int j=0;j<1000;j++) { int cc = n/k; if(i+1<=n%k) cc++; dp[i][j]=INT_MAX; for(auto k : mp[i]) { dp[i][j] = min(dp[i][j],(i-1>=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<<dp[k-1][0]<<endl;I am pretty sure like problem 1 (https://codeforces.net/contest/938/problem/D) problem 5 was also copied from codeforces, I remember seeing that before. will UPD if I find the original statement.
Yeah, please update if you find the problem 5.
Hmm, its been 12 days and you didn't find it yet.
Is there any update for the results?
If anyone wants to practice 5th problem, can do that here.
Explanation, sorry for the plug but explanations on leetcode weren't that helpful, so I wrote one myself.