pritishn's blog

By pritishn, 5 weeks ago, In English

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

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

 
 
 
 
  • Vote: I like it
  • +143
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    could you elaborate a bit on the Use multi-source-dikstra and get the answer part?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        got it, thanks!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So basically for the answer you are calculating

        $$$ \forall \ i \in [1,n], \ ans[\text{node that reached i}] = dis[i] $$$
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give a prediction of number of problems solved to rank prediction ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, i realized later that it's not needed to make extra nodes. XD

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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   Vote: I like it +19 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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   Vote: I like it 0 Vote: I do not like it

            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   Vote: I like it 0 Vote: I do not like it

              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..

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                If i understand your doubt correctly, then no it is also not necessary

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for recommending me to try. I got this one during the contest. xD

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +54 Vote: I do not like it

Problem A was copied- Link.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Lol.. I didn't expect this. XD

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Me too. I came to know this after the contest. I tried the same but gave WA.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Wow, didn't expect this!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I solved this 3 days back and was surprised to see the exact same problem XD

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +12 Vote: I do not like it

2nd question : Count all the vertices having depth < B . Answer is 2^(number of all such nodes)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elobrate. How did the answer came?

»
5 weeks ago, # |
Rev. 4   Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate on the third problem ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used DFS for problem 2!!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I keep getting MLE until I switched to bfs

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This gave me an MLE.

          const int N = 1e5+5;
          vector<int> adj[N];
          
          

          But this one worked without any error.

          vector<vector<int> > adj;
          int fun(){
               adj.assign(n+1, vector<int> ());
          }
          
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          I used the global adjacency list to implement dfs and my solution passed easily, but here many people got MLE, weird..

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            they didnt cleared the adjacency list after using it

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the third problem, do you have the derivation for the formula for k-aray necklace of size n?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Study Burnside Lemma and Pólya enumeration theorem

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      I don't know much about the problem, but during contest, this was little helpful to read.link

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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))

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

4th Just put Max number at Bth position.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +88 Vote: I do not like it

    Even better. Just click on that "See Expected Output."

»
5 weeks ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

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, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Not getting shortlisted does not mean it was a waste of time

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it -24 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +11 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

Solved only 2, I put a lotttt of time on problem 5th, but couldn't converge to an answer.

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Do we get a ranklist?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +19 Vote: I do not like it

How to solve problem E, I wasted more than an hour but couldn't solve it :/

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Just for the getting approximation of rank, how many of you solved 5 or more.

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Do anyone how to solve problem F.

»
5 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$\sum_{i=1}^{i=k}{P(X_i=1)} = k*P(X_1 = 1)$$$

    What happened in this step??

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      $$$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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What does E(x) specifies?

»
5 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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   Vote: I like it +3 Vote: I do not like it

      What if we have different elements at each index?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Did not get your point.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah i implemented that way but it gave 250 points though.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I was getting tle and green tick for correctness.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Notice that you don't have to iterate through all 1024 numbers per state.

    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What will be the worst case complexity for this approach i.e. when we have all the elements different?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it +5 Vote: I do not like it

        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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you need to leave atmost one bucket blank as it would be sufficient to make xor to be 0.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Actually, you don't need dp at all, just a normal window sliding would be sufficient.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How sliding window?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it -28 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This doesn't ensure that the xor of the k-length-window is zero, right?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it -27 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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, # ^ |
            Vote: I like it +3 Vote: I do not like it

          there can be multiple frequent elements

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it with some greedy technique and got 250 points.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

pritishn, update the blog with the concise problem statements. It will be helpful for the ones who have not participated.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

1) Can someone rate the problems in terms of CF difficulty ?
2) Also was there no penalty on wrong submissions ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

has anybody solved last question -6 ???

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    afaik rahul dugar solved all, but I am not pinging him XD

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Why won't you ping him? XD

      amnesiac_dusk , did you solve all 6?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +69 Vote: I do not like it

        Yes, afaik kal013 also solved all.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          Please enlighten with your solution to F. I was clueless even after spending an hour.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +48 Vote: I do not like it

            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   Vote: I like it 0 Vote: I do not like it

      How many did you solve?AGRU

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not enough to tell publicly in this blog XD :(

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate upon your solution? And you mean this technique?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone solve Problem E ?? What is the approach for it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve 5th question(XOR) ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 .

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      should we keep index also as state ? What will be the transitions ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        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)

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did your solution got accepted, I also tried something like this but was unable to get it fully accepted.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I got correct answer upon submitting,did u take min of both answer? dp and greedy ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah please explain the dp transitions. I was unable to think of any efficient dp transition.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What are you referring to as "bucket" ?

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              All the elements belonging to same i%k value.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              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, # ^ |
                  Vote: I like it -6 Vote: I do not like it

                That's what I did, but it seems bruteforce + prefix sum to me, not dp.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            .

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I have not heard abt it

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like 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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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   Vote: I like it 0 Vote: I do not like it

                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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanks! Everything makes sense now. I couldn't observe that the final array will be periodic.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +1 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did exactly same but I was getting Output = Expected output + 1 for some cases.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    codingkshatriya Can u please say what are the states of this dp

»
5 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it -82 Vote: I do not like it

      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, # ^ |
          Vote: I like it +78 Vote: I do not like it

        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, # ^ |
            Vote: I like it +12 Vote: I do not like it

          Who knows, they probably do that with interns. It's an intern-ception...

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Codenation employees did not create problems for this contest.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Being Master+ doesn't mean they are bad software developer. You shouldn't generalise things quickly.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any article about how multisource dijkstra works... or can some one explain it plz

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Geeksforgeeks Multisource bfs

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

In problem 5 constraints were n,k<=10000 and ai<=2^10-1

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Was it a hiring test conducted by codenation?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I heard that a similar hiring event takes place in January as well. What is the difference between the two?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have heard both are same codenation organise two hiring contest each year one in august and one in january .

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I know about that. I am asking in terms of difficulty, duration, syllabus, etc.

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Does anyone have any idea how, where and when the ranklist will be released

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they might show the rank-list of only top 20 people.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      So only top 20 people will get a call for interview?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        I think people with 4 or more correct solutions get a call for the interview.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I Didn't understand a single problem during exam

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was same as Problem No 938D

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

On how many questions does one get an interview call?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Any chance of getting an interview on solving 4.5 problems ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Much more chance than solving 3.5 problems. XD

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you solved 3.5 problems ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        3, I didn't know there was partial points. So i didn't bother to solve 4th problems for 50% score.

»
5 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

Upvote if solved 5 or more.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I still don't understand the first question concert can anyone explain in detail

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it +14 Vote: I do not like it

Any updates on when the ranklist will be released?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Is there any update for the results?