saarang orz

As a rated account on CF, I hope you enjoyed giving this round officially as much as I did testing it!

This was an awesome contest with well balanced problem (Difficulty wise). Really enjoyed the problems. Looking forward to your future contests.

Editorials with Hints listed first are best :)

Can someone share the C++ implementation for problem C?

When hacking solutions, how do I filter out submissions that have been made after the contest has finished?

Something about E:

Most solutions using SPFA fail on test 31. However, using mcfx optimization I can get AC. (142882998)

Can anyone hack this solution?

To put it in the language of problem setter, this contest was NOT BAD ( ;

Auto comment: topic has been updated by saarang (previous revision, new revision, compare).

Problem B actually has a O(N+M) solution, though it is more complicated. I have spent one hour working out this O(N+M) solution because I misunderstood the hell limits of N and M!!!!!!!!!!!!!! Just didn't notice that sum of all N*M does not exceed 1e5 (it really sucks :( Then I have not enough time to submit problem C and I was almost there...

Why in E does a dijkstra not work, for example maintain the state of dp[i]=max health after haveing used ladder i. Are there that much edges, or why does such aporach goes TLE?

Isn't the time complexity of D $$$(n + Alog^2(A))$$$. One log due to iterating over multiples of first A numbers and another due to gcd.

I want to know whether i can use spfa to solve E, i get Time limit exceeded on test 31 o(╥﹏╥)o

Not super exciting because it's silent, but I uploaded a screencast here (I solve all problems & get 15th place): https://www.youtube.com/watch?v=aWAafRRPS2M

grid-Forces

Nice contest

Here are my video solutions for people looking for video format.

I did almost the same in D as in editorial, but it gives TLE.

142886157

My solution does $$$(10^6-n)*n*\log_2 10^6$$$, which is at worst $$$40*10^6$$$ operations.

Please help

UPD: got it, nevermind

Can't F be solved using DP? I couldn't get any mistake after almost 1 hour.

dp[i][j] -> if we have processed first and last i rows of the grid and the last segment (among k+1 segments at every row) is j assuming that all pieces are considered that don't go out of first i, last i rows, and the vertical pieces in ith and (i+1)th row are to be considered. After that transitions are pretty simple.

Where were Anjali when Tina was being so harsh on Rahul.

I had used the DP solution for Problem E but I am getting WA. Can someone tell the test case on which it fails or tell me why it is wrong?

Solution

I had used DP for storing (i,j) state result which is in map m2. map m1 I am using for getting ladders for that key row.

NOte: I used the same approach but without storing state (i,j) and got TLE at 4th Test case. Solution

In problem E I tried using recursion and travelled from one ladder to another and then tried to memoize it by making a HashMap of (string of row and col). I know this might give TLE but why is it giving wrong answer. If anyone knows please help. My submission 142888967

For B i just simulate backward and figure out we will have the max distance to the 4 corners

.

Became Expert after 111 contests. Thanks for the contest. Happy coding everyone.

Seeing as no one has commented about this, we can take advantage of the fact that E has no negative cycles to still run dijkstra on it. We can use the technique of potentials in a graph, see Monogon's blog. We dont need any fancy assignment of potentials based on the edges, the idea that all nodes on floor $$$i$$$ have potential $$$10^{12} - i * 10^6$$$ is enough to get ac.

In-contest submission 142874701 using 'map' TLE's but AC's on using 'unordered_map' 142897768 rest of the code exactly same :(

In E, I didn't think of DP but instead applied dijkstra with the same idea that we need at most 2k + 2 nodes. but It got TLE but I don't know why exactly. Isn't the complexity for Dijkstra O(V+ELOG(V))? with V up to 2k+2 and E up to 2k. shouldn't it work?

This is my submission: 142877138 (I also tried with vectors instead of sets but it got TLE too)

I know weights of ladders are negative but there can't be any cycles since all ladders are in one direction? is there something I'm missing?

So am I the only one who solved B with BFS from corners? Such a shame but at least I got it.

Another (a bit more complicated) solution for $$$D$$$:

Iterate from $$$i=10^6$$$ to $$$1$$$, if $$$i$$$ does not exist yet and it is a gcd of $$$2$$$ existing multiples greater than it, mark it as existing and increment the answer.

To check if $$$i$$$ is a gcd of $$$2$$$ greater exising multiples, get all existing multiples of $$$i$$$ after dividing them by $$$i$$$, lets call this group of values $$$grp$$$, if $$$grp$$$ has a co-prime pair then $$$i$$$ is a gcd of $$$2$$$ greater existing multiples.

To check if there is a co-prime pair within $$$grp$$$ we can get the count of all pairs within $$$grp$$$ with any common divisor > $$$1$$$ using inclusion-exclusion and mobius function, let's call this count $$$cnt$$$, a co-prime pair exists if $$$cnt$$$ is less than the count of all possible pairs in $$$grp$$$.

It's a good contest, but E may be too easy. hope to see a more interesting problem next time.

I've solved B using bfs, there's a pattern in the distance when you go over k=0,1,2...n*m-1 the minimum distance Rahul can achieve starts at the beginning and then it propagates to it's neighbors increasing by one

My solution for Problem D: First I calculate gcd of every pairs in the array using exculsion dp. Then I calculate gcd of every pairs again with the initial array and new gcds (that calculated from the previous step). After doing it 3 times, I found the answer of all the new gcds that can be calculated at most.

In problem C Can someone tell me why I am getting a runtime error in test case 2? My logic is completely right. I am not able to figure out why it's giving a run time error. Please Help !!!!!!!!!!!!!!

Code link:https://mirror.codeforces.com/contest/1627/submission/142916147

#include <iostream>
using namespace std;
#include<bits/stdc++.h>


void dfs(ll i ,vector<pair<int,int>>*adj , bool *vis ,ll c, map<ll,ll>&mp )
{
    
vis[i]=true;
for(auto it:adj[i])
{
    if(!vis[it.first])
    {
        mp[it.second] = c;
        if(c==5)
        {
            c=2;
        }
        else
        {
            c=5;
        }
        dfs( it.first ,adj ,vis,c,mp);
    }
}

}

void solve()
{
ll n;cin>>n;
 vector<pair<int,int>>adj[n+1];

map<pair<ll,ll>,ll>p;
map<ll,ll>mp;
ll deg =0;
ll start;
for(int i=0;i<n-1;i++)
{
    ll x,y;
    cin>>x>>y;
    x--;
    y--;
    adj[x].push_back({y,i});
    adj[y].push_back({x,i});
    if(adj[x].size()>=3 ||adj[y].size()>=3 )
    {
        cout<<-1;
        return ;
    }
}

for(int i=0;i<n-1;i++)
{
    if(adj[i].size()==1)
    {
        start =i;
        break;
    }
}

bool vis[n+1];
memset(vis,false,sizeof(vis));
dfs(start ,adj ,vis ,(ll)2,mp);

for(int i=0;i<n-1;i++)
{
    cout<<mp[i]<<" ";
}


}

int main() 
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{


 solve();
 cout<<"\n";


}
   
}

someone please tell me why I am getting TLE on third test case with almost the same solution as in tutorial for problem D my code

In problem C What is the meaning of this sentence A path should not visit any vertex twice

Can someone please give me an example where a path visit a vertex twice.

can anyone explain me which seats do Tina paint if she plays optimally? I find the solution incomprehensible.

Why the problem D's solution takes $$$O(n+AlogA)$$$? We can see that find the multiples of all $$$1\le x\le A$$$ needs $$$O(AlogA)$$$. And gets the gcd of them needs $$$O(logA)$$$ ,too. So it should take $$$O(n+Alog^2A)$$$ in deed.

Why is the complexity of problem D O(n + AlogA) and not O(nlogn + AlogA) as the two for loops for finding multiples will take upto nlogn and then AlogA extra factor for gcd computations?

In problem E, I use set to save best pairs of {room, cost} for each floor. We iterate over each floor starting from floor 1, and maintain the set by stack-like insertions. 142931555

the time complexity of problem B in edutorial is O((mn)*logmn) but i think it should be O(mn+log(mn)).. maybe a typo..

Problem D can be solved in $$$ O(n + A log log A) $$$ using multi-demension prefix/suffix sum technique

143170028

I use DP for E where each rooms are represented as a single DP state. But seems I got wrong in the implementation part. Any idea what I might be missed?

My implementation : 143189459

Problem can also be solved using breadth first search technique in time complexity of O(NM). My solution: 143357988 Thanks

Can problem E be solved using djakstra ??