saarang's blog

By saarang, history, 4 months 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)

1627B - Not Sitting

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

1627C - Not Assigning

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

1627D - Not Adding

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

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

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

saarang orz

»
4 months 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!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    Yeah, everyone did. Now stop pulling the "as a tester" tag out of your ass everywhere. One time's enough, idiot.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      ok

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      real id se aao

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        Please refrain from using any language other than English on this site. It makes it harder for others to understand.

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +38 Vote: I do not like it

Editorials with Hints listed first are best :)

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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?

  • »
    »
    4 months 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.

»
4 months 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?

  • »
    »
    2 months 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!

»
4 months 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 ( ;

»
4 months 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...
»
4 months 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).

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

nice problems. )) solution of problem C is third test case in example test. I think many, including me)) solved the problem thanks to this test case.

Input
7
1 2
1 3
3 4
3 5
6 2
7 2
Output
-1
»
4 months 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...

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

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

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

        • »
          »
          »
          »
          »
          4 months 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.

    • »
      »
      »
      4 months 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

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

    same here T__T

»
4 months 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?

»
4 months 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.

  • »
    »
    4 months 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})$$$.

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

      Got it. Thanks!

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

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

      • »
        »
        »
        »
        4 months 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.

»
4 months 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

»
4 months 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

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

grid-Forces

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice contest

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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

  • »
    »
    4 months 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++;
        }
    
    • »
      »
      »
      4 months 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}$$$

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me by explaining the proof of the editorial of problem D.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solved c shortly after the contest :(

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 months 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

»
4 months 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

»
4 months 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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is possibly the most amazing editorial I've seen gosh dam

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this code is accepted 142893345 after the contest (also passed the pretests during the contest) but the exact same code gave me a runtime error when the contest ended 142863080

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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 :(

»
4 months 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?

»
4 months 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.

»
4 months 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$$$.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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!

  • »
    »
    4 months 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)

    • »
      »
      »
      4 months 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.

»
4 months 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.

»
4 months 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

  • »
    »
    4 months 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.

»
4 months 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.

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

    Hey, Can you please share any resource about this concept of finding gcd or about what exclusion DP is?

    Thank you!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I managed to solve B in O(n*m). I took all the center cells, initialized them with the distance (the corner cell) and ran a bfs, which would increment distance by 1 on each level. The code is quite messy, but it works :) 142914956

»
4 months 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://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"; } }
  • »
    »
    4 months 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.

»
4 months 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

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

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

»
4 months 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.

  • »
    »
    4 months 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).

»
4 months 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.

»
4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest!! Thankyou!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

fastest editorial!!

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

B: O(mn) using BFS 142943120

»
4 months 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..

  • »
    »
    4 months 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))$$$

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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))$$$.

        • »
          »
          »
          »
          »
          4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E ,I used CHT in every row twice one from left to right other from right to left and stored answer in 2d matrix but getting WA link

»
4 months 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

»
4 months 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

  • »
    »
    4 months 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

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hey Everyone!

Can anyone point out why I am getting a memory error in problem C? Here is my submission : 143317279

Thanks in advance!

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem E be solved using djakstra ??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1627/submission/142841460 Can someone please explain behind the logic of dfs(u, p, c). And, also I was confused, because on iteration of adj[u], dfs(nxt, u, !c) will again execute even the for loop hasn't completed.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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://codeforces.com/contest/1627/problem/D solution — https://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"; }
»
4 months 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://codeforces.com/contest/1627/submission/144133636

»
4 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be solved using BFS ?

»
3 months 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