pritishn's blog

CodeAgon 2020 discussion thread. [Problems added]
By pritishn, 4 years 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

Comments Comments (189)
| Write comment?
»
4 years 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.

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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?

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

        got it, thanks!

        → Reply
      • »
        »
        »
        »
        4 years 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] $$$
        → Reply
      • »
        »
        »
        »
        4 years 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 ?

        → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Thankyou so much man..Really the community is blessed to have people like you.thanks a lot

              → Reply
        • »
          »
          »
          »
          »
          4 years 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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years 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..

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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!!

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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

                  → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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!

    → Reply
  • »
    »
    4 years 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?

    → Reply
»
4 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Problem A was copied- Link.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Lol.. I didn't expect this. XD

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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)

→ Reply
»
4 years 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

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

    Could you please elaborate on the third problem ?

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

    I used DFS for problem 2!!

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

      I keep getting MLE until I switched to bfs

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

        Same.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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> ());
}
          → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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..

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

            they didnt cleared the adjacency list after using it

            → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
    • »
      »
      »
      4 years 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))$$$

      → Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Study Burnside Lemma and Pólya enumeration theorem

      → Reply
    • »
      »
      »
      4 years 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

      → Reply
  • »
    »
    4 years 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))

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

4th Just put Max number at Bth position.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +88 Vote: I do not like it

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

    → Reply
»
4 years 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

→ Reply
»
4 years 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?

→ Reply
»
4 years 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.
→ Reply
»
4 years 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]$$$
→ Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Do we get a ranklist?

→ Reply
»
4 years 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 .

→ Reply
»
4 years 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 :/

→ Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Do anyone how to solve problem F.

→ Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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??

    → Reply
    • »
      »
      »
      4 years 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.

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

    What does E(x) specifies?

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      What if we have different elements at each index?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Did not get your point.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
  • »
    »
    4 years 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.

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

      I was getting tle and green tick for correctness.

      → Reply
  • »
    »
    4 years 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
    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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?

        → Reply
    • »
      »
      »
      4 years 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...

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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.

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

      How sliding window?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

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

          there can be multiple frequent elements

          → Reply
        • »
          »
          »
          »
          »
          4 years 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?

          → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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.

→ Reply
»
4 years 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 ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

has anybody solved last question -6 ???

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +69 Vote: I do not like it

        Yes, afaik kal013 also solved all.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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))

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How many did you solve?AGRU

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

        Not enough to tell publicly in this blog XD :(

        → Reply
»
4 years 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.

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

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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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).

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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 .

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

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

      → Reply
      • »
        »
        »
        »
        4 years 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)

        → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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 ?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

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

            What are you referring to as "bucket" ?

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

              All the elements belonging to same i%k value.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years 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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

                → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            .

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

              I have not heard abt it

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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]]++

                  → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years 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)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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

                  → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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)?

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
  • »
    »
    4 years 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.

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

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

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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 ......

        → Reply
        • »
          »
          »
          »
          »
          4 years 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...

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

          Codenation employees did not create problems for this contest.

          → Reply
»
4 years 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

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

    Geeksforgeeks Multisource bfs

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Was it a hiring test conducted by codenation?

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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 .

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

On how many questions does one get an interview call?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any chance of getting an interview on solving 4.5 problems ?

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

    Much more chance than solving 3.5 problems. XD

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

      you solved 3.5 problems ?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Upvote if solved 5 or more.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I solved 5, but I accidently downvoted instead. Remember to add 2 to the final tally :p.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Man why downvotes I just wanted a projection of my rank.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Any updates on when the ranklist will be released?

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

I am pretty sure like problem 1 (https://codeforces.me/contest/938/problem/D) problem 5 was also copied from codeforces, I remember seeing that before. will UPD if I find the original statement.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any update for the results?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply