natalina's blog

By natalina, history, 2 months ago, translation, In English

1941A - Rudolf and the Ticket

Author: daha.002

Tutorial
Solution
Rate the problem

1941B - Rudolf and 121

Author: Vladosiya

Tutorial
Solution
Rate the problem

1941C - Rudolf and the Ugly String

Author: Mordvin13

Tutorial
Solution
Rate the problem

1941D - Rudolf and the Ball Game

Author: Alexey_Parsh

Tutorial
Solution
Rate the problem

1941E - Rudolf and k Bridges

Author: t0rtik

Tutorial
Solution
Rate the problem

1941F - Rudolf and Imbalance

Author: Vladosiya

Tutorial
Solution
Rate the problem

1941G - Rudolf and Subway

Author: natalina

Tutorial
Solution
Rate the problem
  • Vote: I like it
  • +64
  • Vote: I do not like it

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

I have seen many people code segment tree solutions for E (including tourist).

Can someone please explain how segment tree was used in this question? PS: I understood the solution explained here using dp.

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

    For checking the minimum cost for the previous d cells and the sum of dp starting from the ith row and i+kth row I used a segtree as I had a pretty flexible template and it would pass the TL and be easy to code.

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

      Ooooohhhhh I get it .... That's nice.... thanks for clarifiation.

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

    It is easy to use segment tree just to calculate the minimum in the range where range is D elements before it using segment tree.

    See my code maybe you can understand it easily :- Submission Link

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

    It could be used to find minimum elementsin O(logn), however this is absolutely not necessary, I for exmaple got E with a deque.

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

    is there a way to solve this problem using topdown dp ? I used brute force method checking for each d using top down approach , got TLE .

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

if I want to propose problems to div.3 , how I can do ?

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

Alternate G solution:

Use each subway line as nodes and each station as edges. The trick is to process each station only once.

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

    can you explain more.

    I saw jiangly using the similar technique but can't understand why process each station only once?

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

      Why not read his submission 250862298

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

        How can this solution distinguish between vertices and colors? For example node 1 is connected to node 2 with edge of color 1. Edit : Ok so this is taking two graphs for that one is pointing to the adjecent color and another is pointing to the adjecent nodes.

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

I considered myself a pro at binary search and then problem F happended :/ Nevertheless learned something new. Thanks to the authors.

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

why my state dijsktra to G problem is TLE? 250857953

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

Problem E (Rudolf and k bridges) Video Editorial : Youtube link -- Click here

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

E can be solved in O(n) using deque

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

    Yes, I think it would be similar to maintaining the sliding window minimum over the dp array for each row, storing the minimum costs, and then finally finding minimum sum over $$$k$$$ consecutive costs for the answer.

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

      I did the same and I'm still getting an error in the second test case. Can anyone point out the mistake? 251067871

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

    fax

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

    can E be solved using topdown appraoch without getting TLE ?

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

I really enjoyed solving problem D. I also think that B wasn't suitable for a div 3 B. C, B or maybe D should've been swapped with each other.

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

    maybe, B had a trick that may have been harder to catch than C which is easier to figure out, but harder to implement. Though, this would be splitting hairs. D, though, in my opinion, is significantly harder than B to implement and earned its spot.

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

      respect your opinion but personally, D was very easy.

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

        I agree. D was easy, but generally Div3 A-D are easy for me. Div3 E/F are medium, and Div3G is hard. This contest fits this mold fairly well.

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

Problem C can also be solved with Aho Corasick Automaton. Build a $$$dp[n][m]$$$ where $$$n$$$ is the length of the string and $$$m$$$ is the number of states in the automaton, where $$$dp[i][j]$$$ tells us the minimum number of changes needed to be in state $$$j$$$ of the automaton (which represents some partial or complete matching with some pattern) considering the prefix $$$s[0...i]$$$. It's kinda overkill for this problem, but it's an interesting idea to know. Here's my submission 250707601.

For more details, refer to: CP Algorithms

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

Dislike if you are a ebantuza

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

Oh I solved prob E with just O(n*m) xD

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

    I saw your code but can you explain it to me please ? iam still learning ,thx.

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

      You can calculate the answer for one row in O(m) by using monotone deque (afterward, you can obviously find the minimum amongst all windows of size k in O(n)).

      How to calculate the answer for a row in O(m)?
      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        yeah that's right

        the technique I used in that code is to find the nearest element on the left of i (call it j) which a[j]<a[i]

        and i learned it in cses book (it's free in web and it's pretty nice so i think you should learn in that book) — To Gordon

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

        thanks for explain it to me i understood it now :)

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

    Same, O(m) to find max on bridge, O(n) for each bridge

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

My approach to G was as follows: make a new graph $$$G'$$$ where each node represents an edge in the original graph. There will be an edge between nodes corresponding to $$$(u,v)$$$ and $$$(v,w)$$$, with weight 0 if they have the same color and 1 otherwise. Then I'm doing 0-1 BFS from $$$(b,x)$$$ for all $$$x$$$ which are neighbors of $$$b$$$. Can someone please help me in optimizing the creation of this graph, because currently my method to generate this new graph is giving TLE.

Link to submission — Here

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

Problem E can be solved using deque to calculate the minimum cost of each bridge in O(m), not O(mlogd); so the final complexity will be O(nm) My submission: https://mirror.codeforces.com/contest/1941/submission/250832314

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

ABC — average, div-4 level problems.

D — bad, why set a problem about naive simulation at this level? Also, editorial code has a $$$\log$$$ factor that is not reflected in the complexity analysis. It may not sound like a big deal to you, but beginners regularly get confused by such things.

E — bad, unusual distance definition. Also, the editorial solution has an extra $$$\log$$$ factor for no reason. Finding minimums/maximums in a sliding window is a well-known monotonic queue problem with equally short implementation. Div 3 rounds are supposed to be educational for beginners, please live up to the name.

F — bad, the unusual 2e9 limit was unnecessary. What are you, fishing for overflows? 1e8 was enough to TLE all convolution-based solutions, but you may as well have used 1e18 if you really wanted to avoid anything unintended. And once again, binary search is not necessary. Just sort both arrays and use two-pointers.

G — Good.

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

    What is a convolution based solution ? Can you explain please ?

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

      Consider a polynomial product $$$P(x) = (x^{d_1} + x^{d_2} + \ldots + x^{d_m}) (x^{f_1} + x^{f_2} + \ldots + x^{f_k})$$$. $$$[x^n]P$$$ is nonzero iff there exist $$$1 \le j \le m$$$ and $$$1 \le l \le k$$$ s.t. $$$d_j + f_l = n$$$.

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

    G : lol

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I'm interested in your suggestion to use two-pointers here. Could you explain how that works, when there are two arrays in play?

    EDIT: Rather I am wondering a bit if we can prove that following the two pointers approach will give us the correct answer here.

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

      250732405 When looking for $$$d_j + f_l$$$ as close to some target as possible, increase the sum if it's less and decrease otherwise (in code all numbers are multiplied by 2 to avoid floating-point math).

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

        How can we prove that this will actually give us the closest pair to target as possible? Using binary search it's pretty straight forward but I'm can't prove it for your two pointers approach.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +2 Vote: I do not like it

          Say both $$$d$$$ and $$$f$$$ are sorted in ascending order (wlog all numbers are unique).

          If $$$d_j + f_l < x$$$ then $$$d_{j'} + f_l < d_j + f_l < x$$$ for all $$$j' < j$$$ and hence $$$|(d_{j'} + f_l) - x| > |(d_j + f_l) - x|$$$. Therefore, no pair $$$(j', l)$$$ with $$$j' < j$$$ is optimal. Similarly, no pair $$$(j, l')$$$ with $$$l' < l$$$ is optimal.

          We already considered all pairs with $$$l' > l$$$, so the remaining candidates are pairs with $$$j' > j$$$. Hence we should increment $$$j$$$.

          Similarly, we should decrement $$$l$$$ if $$$d_j + f_l > x$$$.

          Alternatively, you may show that this two-pointers algorithm finds the same indices as your binary searches.

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

    F — ... binary search is not necessary. Just sort

    If sort is O(n*log(n)) and m (2**16) is much bigger than k (2**8):

    Sort m and k, then two pointers:

    2**16 * 16 + 2**8 * 8 + 2**16 + 2**8 = 2**20
    

    Sort only k, then binary search:

    2**8 * 8 + 2**16 * 8 = 2**19
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bold of you to assume that constant factors are the same. std::{lower,upper}_bound is a straightforward algorithm that implements binary search exactly how you do. It also makes a lot of jumps in memory. Meanwhile, std::sort is quite heavily optimized, and two-pointers make no jumps whatsoever.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Slightly less casework required solution for C: count of "map" + count of "pie" — count of "mapie"

  • For D, state DP is better, has better time complexity, and far more braindead (literally obvious to everyone after enough practice?). May or may not require vector.resize() (note to self: CLEAR THE ENTIRE VECTOR BEFORE RESIZING YOU DUMB FUCK)

  • For E, multiset has horrendous constant factor (see: My -9 in that Div3 D several contests ago). Use a priority queue instead. To get the minimum "available" value, just throw every value that could no longer be used out of the pq

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

Can someone explain me jiangly's solution for problem G ? What was the approach and what does dist[{e, 0}] mean?

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

    dist is a map which stores pair<int, int> as key, and int is value

    So "cout << dist[{e, 0}];" means print the value of {e, 0} key

    {e, 0} is a pair, e is first and 0 is second

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

    The technique he used is 01-BFS

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

    As we arrive at some unvisited color we first travel along it, and only then go to adjacent colors. 0 is the nice trick that means "line processed".

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

https://mirror.codeforces.com/contest/1941/submission/250749988 could someone help me figure out why this isn't working?

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

what is wrong in this code : https://mirror.codeforces.com/contest/1941/submission/250787705

Is my logic wrong or am I missing some edge cases. Please Help me . Thank you in advance!

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

    In addition to considering breaking down the maximum difference $$$(a_{i+1}-a_i)$$$, the second biggest difference between $$$a$$$ elements should also be factored in. Consider the test case:

    3 1 1
    1 7 12
    2
    2
    

    Also, when performing binary search (function f in your code), the boolean that it should answer would be: is there $$$d \in D$$$, $$$f \in F$$$ such that $$$max\left(d+f-a_i \, ,\, a_{i+1}-\left(d+f\right)\right) \leq mid$$$.

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

      can you suggest a way to correct the code or is my approach completely. I tried by myself but I am not getting any idea. Thank you

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

        I made modification to your code (251127599) and it runs correctly.

        To elaborate on how to binary search on getting an optimal split between $$$[a_i, a_{i+1}]$$$: for $$$d$$$ and $$$f$$$ we would want to minimize $$$|(\frac{a_i+a_{i+1}}{2} - (d+f))|$$$. For a $$$mid$$$, we seek $$$d$$$ and $$$f$$$ such that $$$a_i + a_{i+1}-mid \leq 2 \cdot (d+f) \leq a_i + a_{i+1}+mid$$$ If res is the minimum such $$$mid$$$ which satisfies, then the required imbalance between newly added problem and $$$a_i, a_{i+1}$$$ would be (a[i+1]-a[i]+res)/2

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

In my opinion the TL on G was very constrained. I had to switch to deque to make it pass. Was an extra logn deliberately disallowed?

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

    Can u please explain me the editorial elaborately.What are the new nodes created and how to make edges between them?

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

      You've got the original nodes (station vertices) and the newly created color vertices (corresponding to all the distinct colored edges possible).

      Now you draw an edge from the two groups (station to color and vice versa). An edge is drawn from station vertex a to color vertex b if and only if there is an edge color b incident to station vertex a.

      Now you perform simple BFS and report the destination distance/2. Note: You consider the edge weight to be 1. Now think why we divided by 2. Also think how this is a bipartite graph.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Problem D: chatGPT solved this question just by entering question statement in prompt

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

    bro leave me happy it was the first time I solve till D :D

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

please anyone can explain the solution of peoblem of B ?

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

can someone explain to me this line of code ? for (string sul : {"mapie", "pie", "map"})

i dont understand the code of the editorial why they alwayes make it hard to read for beginners?

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

    It's a simple combination of range-based for loop and initializer lists. Both are available from C++11 and are very basic.

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

can someone help with problem E ? i get WA 251001023

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

    just remove this line from your sliding window: int yans = ans; declare yans outside the loop.

    refer to my version of this snippet, my win is your yans:

    	win = 0; res = 0;
    	f(i,0,k) win+=costs[i]; res = win;
    	f(i,k,n) 
    	    win += costs[i] - costs[i-k],
    	    res = min(res, win);
    
»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Regarding problem F: It is relatively easy to see that we must decrease the maximal $$$ diff = a_{i}-a_{i-1} $$$, but my question is, what if there are more than 1 such $$$ j's $$$ where $$$ a_{j}-a_{j-1} = diff $$$. How do we choose which difference to take?

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

    if there are more than 1 such that maxDif is same then answer is always maxDif i also had this same doubt during contest and now i feel extremely dumb its over for me

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

For $$$G$$$, I noticed that if a particular vertex has edges of colors $$$(c_1, c_2, c_3 ... c_k)$$$ then the sub-graphs of these colors can be reached by others of this set through at-most 1 different colored edge. So all we need to do is keep track of which "color" belongs which "clusters" (I call each such set a cluster), and vice versa. Then just expand the cloud of visited colors, till we reach a color which is connected to the destination.

As someone who has little math background and is algorithmically weak. I think it is quite intuitive and easier to come up with. Submission-->251004746

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I Have the same idea Like
    for a vertex , find the set of distinct colors it attached to
        What it means is , we can go from a color of this set to any other color of this set
    
    Now , But i do know how i proceed to implement it
    Let me check your submission
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is problem F labeled as two-pointers? Can't think of a solution that uses the two pointers technique.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    We need to decrese the max gap right (the one having max A[i] - A[i-1])
    Now,we can just insert one element (What it would be!!)
        Obviously mid , mid = (A[i] + A[i-1]) / 2
    
    So indirectly , Question transform to  find (i,j) such that D[i] + F[j] is closest to mid
    This is two pointer right,  (Sort D and F and then find it right)
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I would love to contribute problems for Div 3. Is there a way I can do that?

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

Ref B tutorial, What does the following mean

applying the operation to a more leftward element is either impossible or will make some elements less than zero

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

    We are iterating from left to right. We'll apply the operation to i+1th element. Since op=a[i] and a[i]=-op, the elements to the left would already have been 0

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

      So, it's implying to only move left to right. Got it, thanks!

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

Can someone please tell me what's wrong with this (https://mirror.codeforces.com/contest/1941/submission/251042147) approach for 'E'? Why do I get the wrong answer?

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

Very real-life G. In reality the answer is seldom greater than 4,at least in Shanghai, 4 applies to a suboptimal route from Fudan to SJTU: source Fudan U, dest Dongchuan Rd, Fudan U -L18> Jiangpu Park -L8> People's Sqr -L1> Xinzhuang -L5> Dongchuan Rd. But you can choose Zizhu Hi-tech Zone(L15 terminal) as the destination if you want to goto SJTU and reduce the answer to 3.

In Tokyo this answer might be larger

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

I found an interesting solution to the problem G . I reformulate the graph G to G' as follows:

1) Each colour is a node in the graph G'.

2) Each node which is an endpoint of atleast 2 edges of different color is also inserted as a node in my graph. These nodes are special as they "link" 2 different colors. Now for the type (2) nodes I insert an edge E of the original graph , with one endpoint at the node itself and the other endpoint at the color of the edge of our considered type (2) node in the original graph . For example: for the given sample input in the question n = 6 m = 6

(Edge , colour)

1 2 1

2 3 1

5 2 2

2 4 2

4 6 2

3 6 3

In the reformed graph G': Nodes : (color1) , (color2), (color3) , (2) , (3) , (6) Edges : (6->color3) , (6->color2),(2->color1),(2->color2) , (3->color1),(3->color3) Note : 2,3,6 were added as they were part of edges of atleast two distinct colors ,and their edges were added as shown above.

The approach seems long in writing but intuitively its quite simple. Each connected component of a colour is treated here as a SUPER NODE and the other nodes were added to simplify how the colours are connected amongst themselves.

As a multisource BFS is sufficient to find number of minimum colors required to go from set of colors to any particular colors the answer can be found easily.

The link to my submission:251061492

Here for type(2) nodes i insert their negatives , so that they dont collide with the colors. Please excuse me for the messy code.

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

    You can also add half weight in the newly formed graph and then apply dijiskstra

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

E problem was beautiful.

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

https://mirror.codeforces.com/contest/1941/submission/250969634

This is my code for Problem E using memoization which is giving TLE on test case 6 (obviously because Time Complexity is O(n.m.d). I saw various optimised iterative DP approaches used by people with multiset/dequeue/priority queue, but cant find a memoized solution. Can anyone help me out with optimising my memoized approach. Thanks.

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

can anyone please help me (i have read editorial & i m still stuck) my approach is getting WA on testcase 2 https://mirror.codeforces.com/contest/1941/submission/251049209 thanks in advance

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

    There are two problems here

    • the line if (b[i] > md) break; is wrong.

    consider this test

    1
    2 1 1
    1 100
    98
    1
    
    

    here is the answer is $$$98$$$, but your output is $$$99$$$. This happens because your code ignores any other value greater than the mid. However a pair of number might work but their summation is greater than mid, as in the above test

    • you are also getting the mid value wrong. In your code, int md = a[l] + a[r]/2;.

    Consider, $$$l=3, r = 5$$$, here $$$mid = 4$$$ however your $$$md = 5$$$ which is wrong value

    If anything isn't clear please don't hesitate to ask

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

      you are such an amazing person, thank you so much (can thank you enough), you even checked why my answer is not working , thanks a ton mate

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

        nothing to thank for my friend :3.

        Have a great day and keep the good spirit :)

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

D is nice

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

Can anyone pls help me with my solution .idk wht i am doing wrong https://mirror.codeforces.com/contest/1941/submission/251038815

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

https://mirror.codeforces.com/contest/1941/submission/250877308

I implemented this solution but i am getting wrong answer :( i even checked with the editorial its the same :(

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

Could anyone please help me with the Problem 'C'. I am getting a wrong answer for test 2.

[contest:https://mirror.codeforces.com/contest/1941/problem/C]

Please find my submission below: 251308448

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

    Try:

    1
    3
    amp
    

    The answer should be 0.

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

can g be solved by this approach. Basically we will visit the vertices in a bfs fashion firstly at a distance of 1(this includes all the vertices that are connected by the same color of subway line to src). Then we will take all those visited vertices at a distance of 1 and visit the next vertices. Also unlike the trivial bfs we won't mark the vertex visited the 1st time we reach it but only when all the edges incident on the vertex are traversed.

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

This question is pretty similar to https://leetcode.com/problems/bus-routes/description/, one of the most asked questions in Google.

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

help about c++17 in problem G at test 3's wa

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct edge{
	int to,w;
};
vector<edge> e[400001];
int dis[400001];
struct node{
	int id,dis;
	bool operator<(const node &A)const{
		return dis>A.dis;
	}
};
priority_queue<node> p;
bool vis[400001];
void dij(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[s]=0;
	p.push(node{s,dis[s]});
	while(!p.empty()){
		node u=p.top();
		p.pop();
		if(vis[u.id]){
			continue;
		}
		vis[u.id]=true;
		for(edge i:e[u.id]){
			if(dis[i.to]>dis[u.id]+i.w&&!vis[i.to]){
				dis[i.to]=dis[u.id]+i.w;
				p.push(node{i.to,dis[i.to]});
			}
		}
	}
}
int tot=0;
signed main(){
	ios::sync_with_stdio(false);
	int cases;
	cin>>cases;
	while(cases--){
		cin>>n>>m;
		tot=n;
		map<int,int> mapping;
		for(int i=1;i<=m;++i){
			int x,y,z;
			cin>>x>>y>>z;
			if(!mapping.count(z)){
				mapping[z]=++tot;
			}
			e[x].push_back(edge{mapping[z],1});
			e[y].push_back(edge{mapping[z],1});
			e[mapping[z]].push_back(edge{x,0});
			e[mapping[z]].push_back(edge{y,0});
		}
		int b,eu;
		cin>>b>>eu;
		dij(b);
		cout<<dis[eu]<<endl;
		for(int i=0;i<=400000;++i){
			e[i].clear();
		}
	}
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one help me please ,why i am getting WA in F
(https://mirror.codeforces.com/contest/1941/submission/253003605)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D TCx is written n*m however at worst case there can be n elements inserted in set so the complexity should be something like O(m*nlogn) (bcoz insertion in set is log(n)).I am not getting it plz somebody explain.

»
5 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Have anyone managed to complete D using recursion? I tried but I am getting TLE.

Here is my submission: https://mirror.codeforces.com/contest/1941/submission/257239620.

I dont know any other languages as efficiently as python so I tried using python. But IDK how to optimize it further. Can someone help me?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why i got tle in problem number b.

include <bits/stdc++.h>

using namespace std;

define ll long long int

void solve() { long long int n; cin>>n; vectorv(n); for(long long int i=0;i<n;i++) { cin>>v[i]; }

for(long long int i=1;i<n-1; )
{
    if(v[i-1]!=0&&v[i+1]!=0&&v[i]>=2){
    v[i-1]=v[i-1]-1;
    v[i]=v[i]-2;
    v[i+1]=v[i+1]-1;
    }
    if(v[i-1]==0||v[i+1]==0||v[i]<2)
    {
        i+=1;
    }

}

int flag=0;
for(long long int i=0;i<n;i++)
{
    if(v[i]!=0)flag=1;

}
if(flag==1)cout<<"NO\n";
else cout<<"YES\n";

}

int main() { int t; cin >> t; while (t--) { solve(); } return 0; }