Блог пользователя pritishn

Автор pritishn, 4 года назад, По-английски

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

Problem 1

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

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

N,M<=10^5

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

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

N,p<=10^5

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

Problem 3

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

K,M<=10^5

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

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

N,B<=10^5

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

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

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

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

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

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

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

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

  • Проголосовать: нравится
  • +143
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

1st question: Simply double the length of each pre-existing roads. And add N new nodes where ith node is connected with ith city with road distance A[i] . Use multi-source-dikstra and get the answer.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Initial sources for the multi-source-bfs are the newly created nodes ( concert nodes which have distance of A[i] from corresponding city).

      Other edges/roads have lengths multiplied by 2. Because if we travel by a road, we must also come back.

      I guess its clear now?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    I solved it using normal djikstra. The answer for city with minimum cost to have a concert will be the city itself. Then we update the answer for all its neighbours similar to djikstra. Initally the answer for all vertices will be the cost of their concert itself

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      But wouldn't that give shortest cost of all the nodes from the initial minimum cost concert city.. Can u please explain a bit more.. Thanks a lot

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          thanks for the explanation.but i have a doubt that we are doing dijkstra from the source c (the city with the minimum cost) wouldn't that give the shortest cost of all the other node from the source 'c' only..also ans[i] = min(arr[i],ans[j]+2*weight[i][j]) what if there is another edge k such that shotest path is from i-->k-->j and not direct 1-->j.can u please explain me these 2 doubts?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            For the first doubt : We are trying to process the cities in the increasing order of their answers, so when we consider node c we try to update the answer for all its neighbours, but it does'nt mean that the shortest path will be from node c only.

            Let's consider a small graph :
            n = 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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sorry for late response, but the cities j which are visited as 'concert' cities by other neighbor cities will always have ans[j] = arr[j] right ?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Initially ans[i] = arr[i], but after we have processed some cities it's not necessary. Try to dry run a sample test case

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Oh nvm got it forgot about simple counter-examples.

                  I think then it is only guaranteed for isolated nodes and nodes having minimum cost.

                  Thank you for the awesome solution!!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  I think then it is only guaranteed for isolated nodes and nodes having minimum cost.

                  Yes, This is correct. Glad I could help

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    What I did was: 1: Make a multiset ms of pairs storing {A[v], v}

    2: Repeat this until the multiset ms is not 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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried to solve it by first creating the MST and then applying DP on this tree to get the values for each node. It turned out to give me a WA. Can someone please explain why this didn't work?

»
4 года назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

Problem A was copied- Link.

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +17 Проголосовать: не нравится

I solved 4 problems(1-4)

Problem 2 : For each node with depth < p, it is valid to color them either Red/Blue, for the rest of the nodes colors are determined by the nodes with depth < 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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please elaborate on the third problem ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used DFS for problem 2!!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I keep getting MLE until I switched to bfs

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Same.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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> ());
          }
          
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        When I created a global adjacency list and implemented DFS, it gives me MLE, but it got accepted when I created the adjacency list in the solution function and passed it by the 'call by reference'. I think this is due to test cases.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Same bruh, but later i realised I just had to do a[i].clear() for all i till n in the start of function

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I too got MLE when I was performing DFS. It was a simple bug though that caused my code to go into an infinite loop. Instead of checking if the current child is the parent of the current node, I was checking if current node was a parent of itself (stupid thing to do). I fixed it and it worked. And FIY, the adjacency list was declared globally with a size of $$$10^5$$$.

        But technically it should have been a TLE. I guess the infinite loop caused the stack to fill up rapidly and thus the judge gave a MLE.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Could you tell how you optimized your approach for problem 3,

    As we have to calculate for every n from (1 to m), and for every n we have to traverse n times

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      For each $$$n$$$ we only require $$$phi(d)$$$ where $$$d|n$$$ and some powers of $$$k$$$ and $$$k-1$$$ which can be precalculated, Now we can just perform sieve like process

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      You need to traverse on number of divisors of $$$n$$$ whose sum for $$$n = 1..M$$$ is $$$O(M*log(M))$$$, overall complexity being $$$O(M*log^2(M))$$$

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    I received a few messages and my solution to P3 was a bit different. So, let me leave it here. If the problem was on a random array instead of necklace, the answer is easy to derive. Its (n^k-(n-1)^k)/(n^k) where k is size of array. Now, answer of random array is basically sum of answer over all divisors for random aperiodic arrays. So, we apply mobius inversion and get answer for random aperiodic array. Now, a necklace is basically composed of a few random aperiodic arrays. So, we use these and we are done. Overall complexity is O(N(logN+logK))

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

4th Just put Max number at Bth position.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

My previous experience with CodeAgon has been very deadly like last year so I didn't give it this year thinking a great waste of time. One of my seniors (Orange on Codeforces) was selected on 6/6 and one of the seniors (Violet on Codeforces) was not selected on 5/6 and I sat for the intern test and was blown away!!..

CodeAgon was I think is meant for 2000+ rated. You can see the selects of last year, most were 2200+ rated

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved 4, how many did you solve? also this was my first codeagon so do you know what is the cutoff?

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Short editorial for Concert.

1. Ans for the city X with the cheapest concert is same as cost of concert in X.
2. For all cities C which are neibhours of the cheapest city update the cost of concert as:
	Minimum of:
		a) actual cost of concert in city C.
		b) 2 * (cost of going to X from C) + cost of concert in X.
3. Delete X from the graph and goto 1.
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I solved $$$3$$$ problems

  • The first problem. I doubled the weight of each edge and then conducted multiple source BFS to find out the closest concert for each city.
  • The second problem. The entire tree is uniquely determined by the colouring of vertices who’s level is at most $$$P$$$. Count the number of such vertices and raise $$$2$$$ to that power.
  • The fourth problem. $$$[1,2,... B - 1, A, B, B + 1, ... A - 1]$$$
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Do we get a ranklist?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

Can anyone share approach for F problem ? We were given an array A and some value 1<=B<=N , where N is size of array ( 1<=N<=10000) we need to find minimum number of changes we need to make in order to make XOR of all segment (continuous subarray) of size B equal to zero .

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Do anyone how to solve problem F.

»
4 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

For problem 3:

Let F(n,k) denote the number of distinct necklaces of n beads that can be made with at most k colours.

Let $$$X_i$$$ be an Indicator Random variable which is equal to 1 if the $$$i^{th}$$$ colour is included in a necklace. So for a given necklace number of distinct colours = $$$\sum_{i=1}^{i=k}{X_i}$$$.

We need to calculate $$$E[\sum_{i=1}^{i=k}{X_i}] = \sum_{i=1}^{i=k}{E(X_i)} = \sum_{i=1}^{i=k}{P(X_i=1)} = k*P(X_1 = 1)$$$.

Now $$$P(X_1 = 0) = \frac{F(n,k-1)}{F(n,k)}$$$

$$$ Ans = k * (1 - \frac{F(n,k-1)}{F(n,k)})$$$

The value of F(n,k) can be be found here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

How to optimize the 5th(xor problem) problem? I got 255/500 points after implementing n*1024 dp with 1024 extra iterations for each state.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Instead of iterating from 0 to 1023 just iterate on given bucket which contains element which are present at same remainder index.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, will you please describe what was your verdict more precisely? I used the same approach, but I am not sure if I got those 255 points.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

    Spoiler
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

        I think it will be $$$n*1024$$$ only.

        Because total no of states = $$$k*1024$$$ as array will be k-periodic and for each state we will be making at most $$$n/k$$$ iterations

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Actually I did the exact same thing.

      My assumption : If say at the ith position, none of the elements rom the set can be placed, then i can always place xor(A[1]...A[K-1]) ^ A[i] making the xor of 1st K elements 0.

      Please correct me if I am wrong.

      If my assumption is true, then can I add xor(A[1]...A[K-1]) ^ A[i] in the set for thr ith position as well ? If no, then can you kindly say why

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am not sure if I understood your question properly. There can be multiple values for A[1], A[2], ... A[K-1] right? which ones would you be choosing for adding in the ith set?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      could you explain about leaving blank, cause I might leave blanks for multiple indices, and at the end I have to check if xor is zero or not and while returning I will add up costs...

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -24 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How sliding window?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится -28 Проголосовать: не нравится

        I'm not really good at explaining stuff, but I'll give it a try.

        Notice that the final array has to be periodic with a period of k. This means that For a fixed i, all A[i+j*k] (for every j in 0 to i+j*k<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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

            It does actually. Once you have the most frequent elements pre-calculated, all you have to do is iterate over all i in(0,k) and just assume that you are going to change this number to make the xor zero. Calculate the result for all i in (0,k) and take the minimum.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I had the same idea. But I don't think this is going to give you the minimum answer always. I am not sure.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          there can be multiple frequent elements

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Your approach will be wrong when there is same frequency of multiple values.

          I did the same thing. But it didn't showed any partial points. Can someone pls tell that where did they showed partial points?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Same, I implemented it in O(2048*k) but got 250/500 only and k was <=10000. No idea why it didn't pass

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

has anybody solved last question -6 ???

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      Why won't you ping him? XD

      amnesiac_dusk , did you solve all 6?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +69 Проголосовать: не нравится

        Yes, afaik kal013 also solved all.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +48 Проголосовать: не нравится

            I did dp[a][b] which basically represents the answer with the condition that no c zeros or c ones can be merged. Now, let us try to find the answer to it, we are basically forming some n-digit base c fraction, now at each digit of the fraction we will assign some 0s and 1s there which will represent the digit there let us say we assigned u 0s and v 1s then u+v==c-1. And we can call dp[a-i][b-(c-1-i)] to compute this value. Dp[a][b] is initialized by 1 wherever a+b==c and a>0 and b>0. Now, let us compute answer to original problem we can merge c 0s or 1s at whatever level and it results in same thing. So, we just do sum dp[A-i*k][B-j*k] where k=c-1 for all valid values and this is our answer. Although there seems to be A*B states and O(C) transition actually only states where (A+B-1)%(C-1)==0 will be relevant. So, final complexity is O(A*B(+C or smth like that maybe))

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      How many did you solve?AGRU

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can we do A using the rerooting technique? If not, I wonder why it doesn't work? I tried it, but failed on the main tests.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah! I calculated the answer for each connected component separately. For each of them:

      I once called dfs on any node in it and calculated the answer for that root node(say x) by:

      dp[root] = min(cost[root], dfs(child)+2*edgeWeight.

      Then I call a second dfs function by changing the root to the child, and filling answers for them.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It doesn't work because it's a graph and not a tree. Let's say A-B and A-C denote the optimal paths from A to B and C respectively. When we move from A to B, I can't claim that B-C = B-A + A-C, and that's because it's a graph (there might be a shorter path that doesn't involve A at all).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    elements k distance apart must be same , for each number from 0,1,2....k-1 I made a frequency counter of numbers present at that index%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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        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)

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

5th ques can be solved using simples obs, array should be periodic with periodicity k.use dp to check answer without changing any element,if we have to change, then it is optimal to change only one among i from 1 to k.As that element can simply be xor of all other elements.This can be calculated in linear time using freq array.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          only first k elements matter, ith element belongs to imodk bucket.Only one element from each bucket should be selected, and xor of all selected element should be zero. So standard bit masking dp,calc the cost of choosing an element in a bucket, i.e rest of elements in the bucket shud become chosen element,so freq array can be used.dp state wud be bucket number and xor so far.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            What are you referring to as "bucket" ?

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              All the elements belonging to same i%k value.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              element with index i is put into bucket with index imodk, there are k buckets with bucket id from 0 to k-1

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            .

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I have not heard abt it

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                How are you calculating the cost for each bucket? 7,31,7 (Bucket 0) 29,16,16,16(Bucket 1) 26,16,24,16(Bucket 2) 16,24,24(Bucket 3) 8,24,0(Bucket 4)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  say I choose 7 from bucket 0 then all other elements should change to 7, that will be the cost(1), it can be implemented with freq array of map. Insertion will be like freq[i%k][a[i]]++

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            What all values are possible for the ith bucket? According to your dp state, if you choose all possible values at the ith bucket, then the time complexity would be multiplied with 2^10 ig.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              There will be k buckets. Dp state would be bucket index, xor so far. Time complexity would be O(N*MAX)

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Why we are not taking values other than (N/K) elements of ith bucket? It may be possible that choosing these values for all K buckets may not lead xor to 0

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  yes it may,so we are introducing a new element to a bucket in that case all elements inside the bucket should change.It's enough to change only one bucket as that new element can be constructed as xor of the chosen elements in other buckets.So we can check that for each bucket.For other buckets its optimal to take the maximum occuring element

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    So what was your solution's time complexity. Mine was O(2048*k) but it fetched only 250 points for me. I doubt it may be because I coded in java

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Mine was O(N*Max) and I got correct answer upon submission, how did you do it in O(K*2048)?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        The first observation was that elements at k distances must be same. eg if k=3, then array should be something like ax ay az ax ay az ax.... So we need to choose elements for the first k positions. At each location i<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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          yeai get it now,obv it shud give TLE, Every time you are checking 1000 numbers, so complexity wud be K*1023*1023. I think you used recursion dp,if you had implemented iteratively complexity would be evident.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

Why does CodeNation ask so difficult problems? What use do they have solving such weird and stupid problems in real life? Its just plain discrimination for students who don't like CP but are forced to do it. Abomination of a company indeed. I couldn't touch any one problem even.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    They pay a really hefty salary too. It's their choice. If they want to take Master+ only, then we can't do anything about that.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -82 Проголосовать: не нравится

      Being Master+ doesn't mean they are good software engineers also. Probably they can traverse a weird graph in a weird way but they are mostly ignorant of technologies and internals of softwares.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +78 Проголосовать: не нравится

        What if they dont need software engineers at all?
        Probably they just need some cpers to create problems for hiring more cpers next year who inturn can create more problems for hiring more cpers next next year who inturn ......

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Geeksforgeeks Multisource bfs

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i read that but can we do it in the similar way for weighted graph also using djakstra.. can u explain how to use this concept in the first question of codeAgon .... plz plz ... thanks for help

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        We have to run a simple dijkstra but instead of taking only one node in priority queue in the beginning just take all the nodes with their initial distance equal to Ai.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Was it a hiring test conducted by codenation?

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

On how many questions does one get an interview call?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Any chance of getting an interview on solving 4.5 problems ?

»
4 года назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

Upvote if solved 5 or more.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Think of it this way.
    There are concerts in every city, and one person in every city who wants to attend the concert. The concert costs A[i] bucks in each city.
    Every person, has a choice to either watch the concert in his own city, or travel to any other city and watch it there.
    You will obviously not watch the concert in your own city, if it is more expensive than travelling to another city + watching concert + coming back.
    (cost of travelling is weight of edge)
    So now for each resident, you need to find the minimum cost you have to pay for him to attend any one of the N concerts.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Any updates on when the ranklist will be released?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

did anyone solve E? can you tell if this code would work or not?(xor problem)

int n;
cin>>n;
int k;
cin>>k;
vector<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 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there any update for the results?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.