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

Автор natalina, история, 8 месяцев назад, По-русски

1941A - Рудольф и билет

Автор: daha.002

Разбор
Решение
Оценка задачи

1941B - Рудольф и 121

Автор: Vladosiya

Разбор
Решение
Оценка задачи

1941C - Рудольф и некрасивая строка

Автор: Mordvin13

Разбор
Решение
Оценка задачи

1941D - Рудольф и игра с мячом

Автор: Alexey_Parsh

Разбор
Решение
Оценка задачи

1941E - Рудольф и k мостов

Автор: t0rtik

Разбор
Решение
Оценка задачи

1941F - Рудольф и дисбаланс

Автор: Vladosiya

Разбор
Решение
Оценка задачи

1941G - Рудольф и метро

Автор: natalina

Разбор
Решение
Оценка задачи
Разбор задач Codeforces Round 933 (Div. 3)
  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

»
8 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Alternate G solution:

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    can you explain more.

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why not read his submission 250862298

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why my state dijsktra to G problem is TLE? 250857953

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

E can be solved in O(n) using deque

»
8 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

E can be solved in O(n) using deque

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      respect your opinion but personally, D was very easy.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Dislike if you are a ebantuza

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)?
      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.net/contest/1941/submission/250832314

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    G : lol

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

          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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • 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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The technique he used is 01-BFS

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please anyone can explain solution of problem B ?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please anyone can explain the solution of peoblem of B ?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone help with problem E ? i get WA 251001023

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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);
    
»
8 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    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
    
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    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)
    
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good One.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain me the intuition behind problem G's editorial?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone please tell how problem D can also be solved using dynamic programing.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E problem was beautiful.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.net/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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        nothing to thank for my friend :3.

        Have a great day and keep the good spirit :)

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

that was good bruh ok let's go

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В проблеме C, что если нам нужно удалить подпоследовательность вместо подстроки?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D is nice

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.net/contest/1941/submission/250877308

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

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

[contest:https://codeforces.net/contest/1941/problem/C]

Please find my submission below: 251308448

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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();
		}
	}
}
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

G просто скопипастили старую задачу с Информатикса. Вот это прикол, конечно

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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

Here is my submission: https://codeforces.net/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?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what's wrong with my code ? 269747920

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice problem E, got my first DP question correct.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I can't understand 4-th testcase for problem D. We have some graph with circle with nodes 1,2,3,4,5. We start at node 1, and go 4 steps in clockwise order so we end up at 5. At 5, we can do 4 steps both clockwise and counterclockwise, so we can end up at 4 (clockwise) and 1 (counterclockwise). So already something is wrong, because the answer is that only nodes 2,3,5 were visited. Where is my mistake? Can someone explain?