saarang's blog

Codeforces Round #766 (Div. 2) Editorial
By saarang, history, 3 years ago, In English

Thank you for participating in our contest! We hope you enjoyed it.

1627A - Not Shading

Hint 1
Hint 2
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial

1627B - Not Sitting

Hint
Hint Solution
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial

1627C - Not Assigning

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial

1627D - Not Adding

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial

1627E - Not Escaping

Hint
Hint 2
Hint 3
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

1627F - Not Splitting

Hint 1
Hint 2
Hint 3
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Author Notes
  • Vote: I like it
  • +238
  • Vote: I do not like it

Comments Comments (116)
| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

saarang orz

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

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

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

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

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

Editorials with Hints listed first are best :)

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

    They have really done a very good job(Fast editorial,video editorial,good questions)Thank u very much such a good round.

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

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

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

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

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

    just untick the show unofficial checkbox at the top right corner in standings.

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

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?

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

    First of all, orz orz orz.

    But I don't think the solution you linked uses mcfx optimization. AFAICT, mcfx optimization counts the number of times a node has been pushed into the queue, and if it's in $$$[2; \sqrt V ]$$$ then it push_front's otherwise it push_back's. It speeds up your solution from 1637 ms to 343 ms!

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
As far as I remember, problem C is a Google online coding challenge problem. (I am not sure though) But I was not able to solve it at that time and i solved it today, soo...
→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

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

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

    Hey, That is IMPOSSIBLE. Because you must print n*m numbers as answers.

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

      Yep, but it is POSSIBLE to make it a harder problem by querying part of the answers. For example, make the sum of all N + M not larger than 100,0000 and query no more than 100,0000 of different k.

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

        You are right. But I think that will be easy. Emmm, maybe?

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

          Maybe not that easy, I solved problem C and D after contest and it takes me less than 1 hour. Not even longer than the time I spend on the harder problem B that I imagine. But maybe someone else thinks otherwise too.

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

      Or we can print the full answers in a compressed format, it is easy to know that the list of answers can be represented by (Ai, Ci) where i <= N+M which means the next Ci answers are all Ai. In the sample case it is (3, 2), (4, 6), (5, 4).

      Don't limit your creativity bro

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

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?

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

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.

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

    In each iteration, the gcd can only decrease upto log times in total, so the actual complexity is still $$$\mathcal{O}(n + A \log{A})$$$.

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

      Got it. Thanks!

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

      Isn't the complexity of just finding gcd(a,b) O(logb) ?

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

        Yes, but the value of GCD can only decrease log times, so doing GCD $$$n$$$ times with a max value of $$$A$$$ is $$$O(n + \log A)$$$. A way of thinking about this is that most GCD operations will keep the GCD constant, so most operations don't do any actual work.

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

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

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

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

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

grid-Forces

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

Nice contest

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

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

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

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

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

    This part here takes $$$O(mn)$$$.

    for(int i = 1; i < m; i++)
    {
        if(used[i] == 1)continue;
        t = 0;
        for(int j = 0; j < n; j++)
        {
            if(a[j] % i == 0)
            {
                t = gcd(t, a[j]);
            }
        }
        if(t == i)ans++;
    }
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you! But i think its not the case here, because of the first if. I actually misscalculated the number of operations in the worst case, it should have been $$$25*10^{10}*40=10^{13}$$$

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

    Let's say n = (10^6)/2. Then the number of operations n * (1e6 — n) becomes huge.

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

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.

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

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

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

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

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

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

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

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

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

.

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

    You don't need to start from a leaf, you can start from any vertex. The only important thing is to give 2 and 3 (or other prime $$$p$$$ such as $$$p+2$$$ is also prime) alternately to each edge.

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

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

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

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.

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

    Legend has it that Monogon only decided to coordinate our contest to promote his blog.

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

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

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

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?

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

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like 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$$$.

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

    In fact there is no need for mobius (take a look at my submission). The number of pairs with gcd $$$k$$$ is the number of pairs with both elements divisible by $$$k$$$ minus the number of those with gcd $$$2*k$$$, $$$3*k$$$...

    Other parts of your idea still stay the same.

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

      Hey, I looked at your submission for Problem D. And, I have a doubt regarding the same.

      Can you please tell that, why the following loop is being added inside the if condition?

                            if(cnt[i]>=1&&!a[i])
                      {
			res++,a[i]=1;
			for(int j=2*i;j<=(int)1e6;j+=i)
                        {
			  cnt[i]+=a[j];
			}
		      }

      Thanks in advance!

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

    Another interesting way to check if there is a coprime pair within $$$grp$$$ is to randomly take about 300 pairs of integers in $$$grp$$$ and see if any one of the pairs are coprime. (I don't know how likely it will fail though, at least it passed system tests. Would appreciate a lot if someone can tell the probability of my approach failing)

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

      Just uphacked your solution 142857475, though I intended it to be a WA hack but ended up getting a TLE one lol.

      → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
    Soltuion of D:

Brother. I do like
for i,  let some of its multiples are present  k1*i , k2*i , k3*i ....
        Now, i grp all of them like :  (k1 k2 k3 ....)
        __gcd(k1*i , k2*i) = i,  if __gcd(k1 ,k2) = 1
        Now we need to find if there exist two coprime in it or not
        (Without Proof) i take gcd of this group, 
                        if (gcd==1)  then there exist a co prime pair (kx, ky)
         

Can you Prove this that , gcd==1 only if there is a coprime pair??
UPD: I got it why my guess work:
     since i have freedom to combine two number
    (k1,k2)->knew by gcd  (knew,k3)->knew by gcd .....  since i know gcd is decreasing
     at last we have a k' . if this is not one then we are not able to make.
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    Me also,I have also tried to do so the same way but wasn't able to implement in contest but later got AC using bfs.

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

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.

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

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";


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

    Whil taking input if your size of neighbors of x becomes more than 2 you print -1 and return and will not take input of further edges that's why you are getting runtime error. Did the same mistake.

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

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

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

    GOT IT .... MAP MUST NOT BE USED HERE

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

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.

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

    For example consider the edge 1-2 move along it and again come back to 1 (2-1). so you are visiting 1 twice (starting at 1 and ending at 1).

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

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

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

    Tina paints in a cell whose maximum distance to all the four corners is minimum.

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

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.

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

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?

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

    The code for finding multiples is $$$O(A \log A)$$$, not $$$O(n \log n)$$$ since the number of multiples depends on the size of the numbers, not the length of the array.

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

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

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

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

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

    It is correct. You have to sort an array of $$$nm$$$ elements. That's $$$O(nm \cdot log(nm))$$$

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

      I am still not getting it..can you please explain it a little bit more

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

        If you have an array of $$$n$$$ elements, then sorting is $$$O(n \log n)$$$. In this case, we have an array of $$$nm$$$ elements, so the sorting complexity is $$$O(nm \log(nm))$$$.

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

          oh now i got that,was congused in mn.. thanks a lot dear

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

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

143170028

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

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

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

    UPDATED : It got AC when I try to change them to bottom up. It seems I got the problem :

    1. A room can have more than 1 ladder (which in this submission, I haven't handle the case)

    2. Not sure to proof it, but I think it's a flaw from my DP idea :

    • Assume we can reach room $$$U$$$ and have got the minimum cost by moving from $$$U$$$ to the final room. Assume the distance from $$$U$$$ from final node is $$$D$$$

    • But then, there can be more optimal path that might goes through a path that has a lot of ladders (which in this case, we "gain" more health and "lose" $$$X$$$ points, which I will denote this as $$$-X$$$) and eventually we reached back to node $$$U$$$

    • it can be seen that $$$D-X$$$ might be smaller than $$$D$$$ therefore the DP answer can be updated — which I can't do that in top down because once I visited state $$$U$$$, then I will have $$$dp[U]$$$ fixed and never be updated, while in fact it needs to be updated

    Changed to bottom up like the editorial just did and it seems to solve the problem

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

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

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

Can problem E be solved using djakstra ??

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

1627E - Not Escaping why 143474919 wrong answer 23 ? what's wrong?

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

can someone pls tell me what is wrong in this solution I am unable to understand it. problem — 1627D — Not Adding — https://mirror.codeforces.com/contest/1627/problem/D solution — https://mirror.codeforces.com/contest/1627/submission/143931841 @saarang


vi p(1000005,0);
 
void solve(int t){
	int n;
	cin>>n;
	int mx=-1;
	rep(i,1,n){
		int tmp;
		cin>>tmp;
		p[tmp]=1;
		mx = max(mx,tmp);
	}
	int ans=0;
	repi(i,mx,1){
		if(p[i])	continue;
		int cnt=0;
		for(int j=i*2;j<=mx;j+=i){
			if(p[j])	cnt++;
		}
		if(cnt>=2){
			ans++;
			p[i]=1;
		}
	}
	cout<<ans<<"\n";
}
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please check why my this solution for problem E using dijkstra gets TLE on test case 8.I have not used negative edges and used dijkstra for each row separately.

Link to my submission:- https://mirror.codeforces.com/contest/1627/submission/144133636

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

Can someone explain the dp for E? It is not clear to me what are the states and how they are updated efficiently.

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

Why my code TLEs for problem E? Please help I have used shortest path approach using dijkstras algo. I have written comments for easy understanding of code. Complexity for my code is O(klogk) imo. 147170375

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

    If you're naively running Dijkstra's you can have up to $$$O(k^2)$$$ edges with $$$O(k)$$$ ladders from floor 1 to floor 2 and then $$$O(k)$$$ ladders from floor 2 to floor 3. The $$$O(k^2)$$$ edges are all on floor 2

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to D using inclusion-exclusion and some observations related with properties of co-prime

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B is beautiful!

→ Reply