CodeAgon 2023 Discussion

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

Автор srishtik_16, история, 16 месяцев назад, По-английски

CodeAgon 2023 by Trilogy Innovations was held today. We can use this blog to discuss the problems and their approaches. I personally solved 2.5 problems, 1st , 4th and 5th partial (300 points). Would be interested in knowing the solutions for the others.

My Approaches:

Problem 1: Sort the array and find median. Try changing 1st two elements, last 2 elements, and 1st and last elements to the median, and try to find the optimal answer out of these 3 cases.

Problem 4: Solved it with DP,where DP[i] = expected steps for number i, Transistion -> dp[i] = (sum of (dp[div] + 1) for all divisors of i except 1) / count of divisors of i. The required answer is sum of dp[i] for all 1 to n, divided by n.

Problem 5: Did it partially with approach similar to this Problem.

Would love to hear your approaches too.

Thanks.

srishtik_16
16 месяцев назад
38

Комментарии (36)

Показать архивные | Написать комментарий?

Aquanox

16 месяцев назад, # |

Is there an easy way to solve the second problem? I do not have the screenshot, so describing the problem here:

Спойлер

Also, can someone share the 6th problem and the approach?

→ Ответить

srishtik_16

16 месяцев назад, # ^ |

How many did you solve?

→ Ответить

Aquanox

16 месяцев назад, # ^ |

I was able to solve 4 fully, wasted much time on that expected value problem becoz of my dumb mind that ignored a very important line to read. I feel like 2nd problem is solvable, but 6th is way out of my reach.

→ Ответить

yash_daga

16 месяцев назад, # ^ |

+20

1)For a particular sequence of $$$I, I+B, I+2B...$$$ It is optimal to put the elements in sorted order so that the sum of differences is equal to max-min.

2)If we separate the sequences {$$$0, B, 2B...$$$}, {$$$1, B+1, 2B+1...$$$}, once we start giving elements to one sequence it is optimal to first fill the all the indices of this sequence (assuming we fill in sorted order), before we start filling another one.

3)So the final answer would be equal to max-min-(the differences b/w consecutive elements where one sequence ends and other one begins)

4)We can subtract exactly B-1 differences but once we take one the next one can be only after we complete taking an entire sequence.

5)There are exactly $$$(N \bmod B)$$$ sequences with size $$$\lceil \frac{N}{B}\rceil$$$ and the remaining sequences have size $$$\lfloor \frac{N}{B}\rfloor$$$. Just apply $$$B^2$$$ dp where $$$dp[x][y]$$$ is the state where you have taken x sequences of size $$$\lfloor \frac{N}{B}\rfloor$$$ and y with size $$$\lceil \frac{N}{B}\rceil$$$.

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

Were you able to pass this solution with a 2-d dp array? I had to solve it iteratively filling the array diagonally as with recursive implementation I got MLE.

→ Ответить

yash_daga

16 месяцев назад, # ^ |

I took a global 5000*5000 array and it passed.

→ Ответить

Aquanox

16 месяцев назад, # ^ |

Nice solution, thanks.

→ Ответить

CodeWithSunny

16 месяцев назад, # |

I solved two problems, two operations and a treasure hunt completely. I just need to know the logic of the intersection of segments. I came up with the idea of a disjoint set union but I'm not able to implement it correctly.

→ Ответить

srishtik_16

16 месяцев назад, # ^ |

What was your approach for treasure hunt? Thought of doing it with djikstra but couldn't give it much time due to wasting time on 2 and 5. 5th looked really easy initially and then kept getting harder.

→ Ответить

CodeWithSunny

16 месяцев назад, # ^ |

Apply the Dijkstra algorithm from each node.

Code

vector<long long> Solution::solve(vector<long long> &A, vector<int> &B, vector<vector<int> > &C) {
    int n = A.size();
    
    vector <pair <long long, long long>> adj[n + 1];
    vector <vector <long long>> dist1(n + 1, vector <long long>(n + 1, 1e18));
    vector <vector <long long>> dist2(n + 1, vector <long long>(n + 1, 1e18));
    
    for(auto& edge : C){
        adj[edge[0]].push_back({edge[1], edge[2]});
        adj[edge[1]].push_back({edge[0], edge[2]});
    }
    
    for(int i=1; i<=n; i++){
        priority_queue <pair <long long, long long>, vector <pair <long long, long long>>, greater <pair <long long, long long>>> pq;
        
        dist1[i][i] = 0;
        pq.push({0, i});
        
        while(!pq.empty()){
            auto p = pq.top();
            pq.pop();
            
            long long d = p.first, v = p.second;
            for(auto& u : adj[v]){
                if(d + u.second < dist1[i][u.first]){
                    dist1[i][u.first] = d + u.second;
                    pq.push({dist1[i][u.first], u.first});
                }
            }
        }
        
        dist2[i][i] = A[i - 1];
        pq.push({A[i - 1], i});
        
        while(!pq.empty()){
            auto p = pq.top();
            pq.pop();
            
            long long d = p.first, v = p.second;
            for(auto& u : adj[v]){
                if(d + u.second + B[i - 1] < dist2[i][u.first]){
                    dist2[i][u.first] = d + u.second + B[i - 1];
                    pq.push({dist2[i][u.first], u.first});
                }
            }
        }
    }
    
    vector <long long> ans;
    for(int i=1; i<=n; i++){
        long long curr = 1e18;
        for(int j=1; j<=n; j++){
            if(dist1[i][j] != 1e18 && dist2[j][i] != 1e18){
                curr = min(curr, dist1[i][j] + dist2[j][i]);
            }
        }
        
        ans.push_back(curr);
    }
    
    return ans;
}

→ Ответить

hackerbhaiya

16 месяцев назад, # |

I solved 5 full and partial in a direct Dijkstra problem C (166/300). Most probably there was an overflow issue due to the usage of int, I noticed it at the end, but could not correct it till the end :(
Really disappointed after missing one of the easiest problems.

Can someone post the images of the problems? I will share my approach.

→ Ответить

Aquanox

16 месяцев назад, # ^ |

Problems

→ Ответить

tanmay.raj.29

16 месяцев назад, # ^ |

What was your time complexity?

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

Not sure :(

→ Ответить

kaichisaki

16 месяцев назад, # ^ |

Can you share your approach for 5th problem (Intersection of segments).

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

Shared Here: https://codeforces.com/blog/entry/111126?#comment-990209

→ Ответить

Nathan_McKane

16 месяцев назад, # ^ |

What was your approach for the 6th problem?

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

https://codeforces.com/blog/entry/111126?#comment-990209

→ Ответить

gupta_gopal

16 месяцев назад, # ^ |

← Rev. 2 →

How did you check that you got 166/300 points. hackerbhaiya

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

At the bottom it was written Partially Correct : 166/300

→ Ответить

dontcopy32

16 месяцев назад, # ^ |

Did it come as Correct Answer even after passing only 166/300 tests?

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

It came as Partially Correct: 166/300
Also, there were some lines above it mentioning something about inefficiency and overflow issues.

→ Ответить

18o3

16 месяцев назад, # ^ |

Hey I also had the same partial score on problem c. I had a logical error in my code. I was not considering the cases when we go using one path and come back using another.

→ Ответить

hackerbhaiya

16 месяцев назад, # ^ |

Oh F!!! I thought that the problem was to comeback using the same path (basically 2 times the path used to reach destination ) :(

→ Ответить

YPK

16 месяцев назад, # |

Can anyone explain the problem statement for C?

→ Ответить

tanmay.raj.29

16 месяцев назад, # ^ |

For each vertex u, we want to find minimum cost to get a treasure located at some vertex v. Cost to get treasure is, A[v] + (edge weights while going to v) + (edge weights while returning to u) + (number of edge while returning to u) * weight of treasure).

→ Ответить

tanmay.raj.29

16 месяцев назад, # ^ |

I got partial marks in this problem. Could not see exact marks as test finished :|

O(n^3 * log(n^2) Approach

→ Ответить

18o3

16 месяцев назад, # ^ |

For dp2 we don't really require the cnt part.The minimum price to reach v from u can be found by running dijsktra on a graph where each edge weight=edge weight+B[v].

→ Ответить

tanmay.raj.29

16 месяцев назад, # ^ |

Were you able to get AC on this?

→ Ответить

18o3

16 месяцев назад, # ^ |

Yes.

→ Ответить

NextThread

16 месяцев назад, # |

this contest is a lil bit harder than the previous one! ig

→ Ответить

18o3

16 месяцев назад, # ^ |

I found it easier. Last year the problem involved topics like small to large merging on tree,lazy segment tree,staircase nim and one tough bitmask optimization.

→ Ответить