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

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

1931A - Восстановление маленькой строки

Идея: myav Разработка: myav

Разбор
Решение

1931B - Сделай равными

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор
Решение

1931C - Снова сделай равными

Идея: senjougaharin Разработка: senjougaharin

Разбор
Решение

1931D - Делимые пары

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор
Решение

1931E - Аня и подарок на День святого Валентина

Идея: Gornak40 Разработка: Gornak40

Разбор
Решение

1931F - Скриншоты чата

Идея: senjougaharin Разработка: senjougaharin

Разбор
Решение

1931G - Одномерный пазл

Идея: senjougaharin Разработка: senjougaharin

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

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

Can anyone explain why for Problem. F this submission gets TLE.

246345877

and this submission gets accepted?

246347175

I don't feel like there's any difference in logic, just the way of implementation is different.

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

    In the second submission there is an optimization of the DFS function: do not run a search if the vertex has already been visited

    My submissions:

    246247300

    246250491

    You can see the difference more clearly here

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

      are you talking about the external dfs optimization from main function or internal dfs optimization?

      I mean the lines

      le(i, 1, n){
      			if(!vis[i]){
      				if(dfs(i)){
      					cout << "NO" << endl;
      					flg = 1;
      					break;
      				}
      			}
      		}
      

      or

      	for(auto c: graph[v]){
      		if(dfs(c)){
      			return true;
      		}
      	}
      
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    In the TLE submission your first loop (to clear graph / vis / dfsStack) will run 10000(t) * 200005(NxM) operations. The accepted one only clears the memory needed for each test case.

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

      so I don't need to initialize it with size NxM? and resize it to n+1 in every test case while clearing it in the end of each test case?

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

    The solution in which you are getting TLE. Coz:

    You are unnecessary initializing array of maxN again and again, even when the Value of N be small.

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

    In the second submission the graph is a array of sets, so when you insert a repeated edge it doesn't get duplicated. In the first submission you are duplicating a lot of edges (because you are pushing them in a vector), and going through all of them during the dfs.

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

      I will try it a little while. Hope it works.

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

      I'm wrong, this still would not cause TLE (the total amount of edges over all tests is less than 2*10⁵), robostac gave the right answer.

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

A different way to do F:

  • Each element (after the 0th element in the kth list) can only be it's current position or its current position+1

  • Store both possibilities in a vector

  • Remove possibilities for elements when they're no longer possible (i.e. the current element's position in the kth list conflicts with the elements position in a previous list)

  • The answer is no if an element has no possibilities, or if its only possibility conflicts with another elements only possibility

  • Otherwise the answer is yes

Code: https://codeforces.me/contest/1931/submission/246250979

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

How was my solution hacked? https://codeforces.me/contest/1931/submission/246212609

I see it was probably due to collisions in the map but does that mean I need a better hashing function for pairs? If so can someone suggest one?

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

can somebody help me understand why this solution got TLE Problem D

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

    probably, for multiset's count function, if I ain't mistaken, it works in O(logn) time

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

    I think it is because of s.count( {cx,cy} ), that is not O(1) but O(count_of({cx,cy}) + log(N)), so worst case in an array with all ones and x=2, you get O(N^2) time complexity. I think in C++ you should be going for a unordered_map<pair<int,int>, int> in which the values are the count so you can do the addition in O(1).

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

Good contest but again I will most likely stay with newbie.

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

Hey, I have submitted a java code for problem C but it gave me error on test case 3 whereas when i submitted the exact same code in c++ it passed all test cases why

java link: https://codeforces.me/contest/1931/submission/246230264

c++ link: https://codeforces.me/contest/1931/submission/246276255

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

In G we don't need to calculate factorials to $$$4 \times 10^6$$$ since the biggest factorial we need in combinations is actually $$$2 * max(c_{i}) \leq 2 \times 10^6$$$

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

i think something wrong in solution code of problem A ._.

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

Thanks for good Round. Good F

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

Why D's solution is correct? It uses a hash table (dict), so is it possible to hack this hash table?

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

A lot of dict/unordered hacks this round. Although I still see quite a lot of solutions not hacked that use the same approach for problem D.

Nice round. Had no idea toposort is available in standard Python library.

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

could any explain why in F , having cycle in graph means there is no logical order of numbers ?

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

    consider the following case

    1 2 3 4 2 3 1 4 3 4 3 2

    the graph would be

    2 -> 3 -> 4 and 3 -> 1 -> 4 and 4 ->3 ->2 if you construct graph for these nodes then there's a cycle. now answer to why does it make sense: we have to follow the order no matter what. here 2 comes before 3 and 4, similarly 3 comes before 1 and 4 but the 3rd one, which creates the cycle, has that 4 comes before 3. it is possible to have 3 before 4 and 4 before 3 in the line simultaneously. so that's why having cycle means no ordering for the data.

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

    consider these two statements,

    1 comes before 2

    2 comes before 1

    they can't be true at the same time,

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

Was I the only one who had an unusually hard time in this round? T_T

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

Nice problems , had fun solving them

I really hope more rounds like this exist

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

why the code of problem A uses the string cur outside loop so I think this isn't true; please anyone can review it?

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

    It's correct because the first triples that it finds is guaranteed to be the minimum, so everything after that affecting the cur variable doesn't matter

    (That also means it doesn't need to continue the loop to find the minimum here and can return immediately when it finds the first triples)

    But I agree that appending to the cur variable after that is definitely unnecessary and the logic is also wrong IF the minimum is not the first triples lol)

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

I still don't understand anything in G, can someone please explain me

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

    This was my thought process when upsolving G.

    The main observation needed is to notice that 1 + 3 = 1 and 2 + 4 = 2, so we can condense all 3 and 4 pieces. However, it is possible to start the sequence with a 3 or 4 piece, so for this reason we can imagine having an "extra" 1 or 2, respectively. Now there are a few cases:

    • No correct puzzle sequence can have consecutive 1's or 2's, so if $$$ |c_1 - c_2| > 1 $$$, the answer is 0.

    • If $$$ c_1 = c_2 = 0 $$$, the answer is 1 if $$$ c_3 = 0 $$$ and/or $$$ c_4 = 0 $$$ and 0 otherwise. This is true because 3 cannot mesh with 4.

    • If $$$ c_1 = c_2 $$$ and $$$ c_1, c_2 > 0 $$$, either 1 or 2 can be used to start the puzzle sequence, so we can fix the first number and calculate the rest of the sequence. Counting the # of ways to condense $$$ c_3 $$$ 3 pieces into $$$ c_1 + 1 $$$ 1 pieces is the same as counting the # of ways to put $$$ c_3 $$$ indistinguishable balls into $$$ c_1 + 1 $$$ boxes, which is $$$ \binom{c_1 + c_3}{c_1} $$$ (this can be visualized with the stars and bars technique). Note that 1 is added to $$$ c_1 $$$ for that "extra" piece, if we fix 1 to be the first puzzle. As such, the answer is $$$ = \binom{c_1 + c_3 - 1}{c_1 - 1} \cdot \binom{c_2 + c_4}{c_2} + \binom{c_1 + c_3}{c_1} \cdot \binom{c_2 + c_4 - 1}{c_2 - 1} $$$

    • If $$$ c_1 = c_2 + 1 $$$ or $$$ c_1 + 1 = c_2 $$$, then we are required to fix either 1 or 2 to be the first piece, respectively. Then it's the same exact idea as the previous case

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

      your explanation is better than editorial, thanks...

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

      Could you clarify why we need to add one? I'm not entirely clear on what you mean by an "extra piece." Could you elaborate further on that point?

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

        We assume that every 3 and 4 piece must be in a sequence of 1333... or 24444.... However it is also possible to place a sequence of 3's or 4's at the beginning of the sequence, without a corresponding 1 or 2 behind it. So adding an invisible 1/2 lets us strictly associate every 3/4 with a corresponding 1/2, which makes calculation easier.

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

Anyone can check my wrong in this code for problem E? It's call wrong in test 3, but i think i have same ideal with propers.. 246215307

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

why my solution TLE on system test.
is unordered_map of unordered_map took significantly more time to find than unordered_map that pair as key?

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

Can some one explain the approach for problem G in detail?

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

Problem G:

Let the four types be denoted by $$$\color{purple}{b_1}$$$, $$$\color{blue}{b_2}$$$, $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ respectively.

Lemma 1: Between any two $$$\color{purple}{b_1}$$$, there must be at least one $$$\color{blue}{b_2}$$$. It is easy to see that one cannot fit only $$$\color{olive}{b_3}$$$ and/or $$$\color{teal}{b_4}$$$ between two $$$\color{purple}{b_1}$$$.

Lemma 2: Between any two $$$\color{blue}{b_2}$$$, there must be at least one $$$\color{purple}{b_1}$$$. It is easy to see that one cannot fit only $$$\color{olive}{b_3}$$$ and/or $$$\color{teal}{b_4}$$$ between two $$$\color{blue}{b_2}$$$.

It follows that between any two $$$\color{purple}{b_1}$$$, there must be exactly one $$$\color{blue}{b_2}$$$. Likewise, between any two $$$\color{blue}{b_2}$$$, there must be exactly one $$$\color{purple}{b_1}$$$. In other words, they must follow an alternating pattern $$$\color{purple}{b_1}, \color{blue}{b_2}, \color{purple}{b_1}, \color{blue}{b_2}, \ldots$$$ or $$$\color{blue}{b_2}, \color{purple}{b_1}, \color{blue}{b_2}, \color{purple}{b_1}, \ldots$$$, with possibly some $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ in between.

Lemma 3: If a block exists to the left of a $$$\color{olive}{b_3}$$$, it must either be another $$$\color{olive}{b_3}$$$ or a $$$\color{purple}{b_1}$$$. If a block exists to the right of a $$$\color{olive}{b_3}$$$, it must either be another $$$\color{olive}{b_3}$$$ or a $$$\color{blue}{b_2}$$$.

Lemma 4: If a block exists to the left of a $$$\color{teal}{b_4}$$$, it must either be another $$$\color{teal}{b_4}$$$ or a $$$\color{blue}{b_2}$$$. If a block exists to the right of a $$$\color{teal}{b_4}$$$, it must either be another $$$\color{teal}{b_4}$$$ or a $$$\color{purple}{b_1}$$$.

Putting everything together, any valid arrangement will be of the form

  • $$$\{\color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \ldots\}$$$ or
  • $$$\{\color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \color{olive}{\{b_3, b_3, \ldots\}}, \color{blue}{b_2}, \color{teal}{\{b_4, b_4, \ldots\}}, \color{purple}{b_1}, \ldots\}$$$

For such an arrangement to exist, it must hold that $$$\mathrm{abs}(c_1 - c_2) \leq 1$$$. Then, the number of valid arrangements is the number of ways to arrange $$$\color{olive}{b_3}$$$ and $$$\color{teal}{b_4}$$$ into the 'slots' between alternating $$$\color{purple}{b_1}$$$ and $$$\color{blue}{b_2}$$$. This can be done using the stars and bars technique.

Submission: 246362383

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

Another idea for Problem F (indeed, what first came into my mind is not the solution in tutorial):

The first screenshot show the main order of users except the one (say, i) to which the screenshot belong. We can use the remaining screenshots to narrow the range of the i's place: if there's only one possible place, good; if there are multiple possible places, just choose one; if there's contradiction, then answer is "NO" directly. Adding i's place to the main order gives the whole order, compare it to remaining screenshots gives final answer (if contradictions exist, then "NO", otherwise, "YES"). Time complexity is OK.

https://codeforces.me/contest/1931/submission/246229823

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

what are the prequesites for G . I didn't understand anything, and why am i still green and i hit the 1400 mark

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

For the problem F, I do understand why existence of topological sort (and therefore absence of cycles) of such graph is necessary condition for existence of the order. However, why is it sufficient? I.e. What is exact proof that absence of cycles guarantee that such order of chat participants exists?

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

    You have a set of statements where $$$a_i < a_{i+1}$$$ that you can get by ignoring $$$a_0$$$.

    That's an ordering. You cannot have $$$a_1 < a_2$$$, $$$a_2 < a_3$$$ and then another $$$a_3 < a_1$$$ due to transitivity of the ordering on integers. If $$$a_1 < a_2$$$ and $$$a_2 < a_3$$$ then $$$a_1 < a_3$$$. That's what cycle check is for. It finds the case where transitivity is broken if that case exists.

    If you're asking about missing statements to have an ordering where every $$$a_i$$$ is at its true position, then you can easily see that if transitivity holds, you can invent your own statements where it can still hold and create a full order.

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

    If there are no cycles in the directed graph that means that you can run the topological sort algorithm on it.

    The correct sequence will be the sequence after we topologically sort it as it will be satisfying all the conditions ie all the edges in the graph are not forming a cycle.

    Therefore it is enough to no if we can topologically sort the graph or no ie check for any directed cycles.

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

Video Solution for problemD : https://www.youtube.com/watch?v=FPRiSmmyfiE

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

Can anyone explain for me what wrong in my details explanation of problem D: D_practice_Modular
I don't understand why a[i] mod x = (x - a[j] mod x) mod x instead of a[i] mod x = x - a[j] mod x

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

    The value of a[i] mod x should always be in range [0, x - 1] (should be less than x). In the equation a[i] mod x = x - a[j] mod x this property will not always be true as if a[j] mod x becomes zero then a[i] mod x = x which is contradicting the property. For example

    a[j] = 10 , x = 5

    a[i] mod 5 = 5 - 10 mod 5

    a[i] mod 5 = 5

    thus to prevent this and keep the value of a[i] mod x in range we use the equation a[i] mod x = (x - a[j] mod x) mod x

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

      I don't quite understand, one more than is, in range [0, 2x) we have two multiple of x are 0 and x. Why we only choose the case x in the expression instead of both cases? When a[i] mod x + a[j] mod x = 0 ==> a[i] mod x = a[j] mod x = 0

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

        That case a[i] mod x = a[j] mod x = 0 actually gets considered on its own when we use a[i] mod x = (x - a[j] mod x) mod x.

        Let's say a[i] mod x = a[j] mod x = 0 thus a[i] mod x = (x - a[j] mod x) mod x LHS becomes 0 and RHS becomes (x - 0) mod x which is also 0. Hence LHS = RHS. So both cases are being considered in this single equation.

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

Can someone please figure out what the mistake with my submission is? Any help is appreciated. https://codeforces.me/contest/1931/submission/246419122

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    	    sort(trailnums.begin(), trailnums.end(), [&](pair<long long int, long long int> a, pair<long long int, long long int> b) {
    	        return to_string(a.first).length() < to_string(b.first).length();
    	    });
    

    I think this part is the issue. You are sorting the numbers with trailing zeros by their absolute lengths in increasing order (instead of their numbers of trailing zeros in decreasing order). Seems like test #2 was only of integers from 1 to 10, thus this solution will be automatically be correct for just that case (but not when the integers are higher).

    For example: 4000000 should be prioritized more than 711100 since it has 6 trailing zeros (compared to 2 of 711100), but your sorting will make 711100 stand first.

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

      Hi AkiLotus, I also tried that approach before using the number of trailing zeros in decreasing order:

      Submission:https://codeforces.me/contest/1931/submission/246418992

      But even that does not seem to work.

      Appreciate your effort in looking into my code.

      Thanks

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

        I see now. The remtrail function isn't correct either, specifically this part.

            string ans = "";
            for(int i=0;i<n;i++) {
                if(s[i] == '0') break;
                else {
                    ans += s[i];
                }
            }
        

        Take a guess of what the output of remtrail(170011000) would be with this code. Correct answer is supposed to be 170011.

        Spoiler (open only when you figured out the bug)
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From tutorial D: Since (ai + aj) mod x = 0, it follows that (ai mod x + aj mod x) mod x = 0. Since (ai − aj) mod y = 0, it follows that ai mod y − aj mod y = 0.

Quite not clear, how it follows, and why it's not (ai mod y − aj mod y) mod y = 0 for 2nd case then.

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

    0\ \le\ ai\ mod\ y\ \le\ y-1 \newline

    0\ \le\ aj\ mod\ y\ \le\ y-1 \newline

    -(y-1)\ \le\ (ai\ mod\ y − aj\ mod\ y)\ \le y-1 $$$

    So if $$$\ (ai\ mod\ y − aj\ mod\ y)\ mod\ y = 0$$$

    Then $$$\ (ai\ mod\ y − aj\ mod\ y) = 0$$$

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

Solution for D without hash:

We need to count number of pairs equal with respect to $$$(mod\ y)$$$ and sum of which equal to $$$0$$$ with respect to $$$(mod\ x)$$$.

For each $$$a[i]$$$ store pair $$$ \{ a[i] (mod\ y), a[i] (mod\ x) \} $$$. Sort array of pairs.

Now pairs can be divided into continuous blocks of numbers equal with respect to $$$(mod\ y)$$$. And inside each block elements are sorted by their $$$(mod\ x)$$$.

So inside each block we can count number of pairs which add up to $$$0$$$ with respect to $$$(mod\ x)$$$ using 2 pointers in $$$O(n)$$$.

Complexity of solution $$$O(n * log(n))$$$. (Because of sorting)

My submission 246421822

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

Could someone tell me why my code for Question D always returns compilation error? My submission: 246426188

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

Could Someone explain why the following code fails in problem F. My logic for the problem is completely different compared to what the tutorial talks about, but i feel it should work.

I have first constructed a pattern using the first screenshot, using every element except the first, in the first screenshot.

Then I check, if all the other screenshots after this first screenshot follow that pattern or not.

https://codeforces.me/contest/1931/submission/246430531

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

E题代码没看懂啊,有什么小白能看懂的吗

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

.

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

In Problem D,when i use unordered_map,i got TLE on test 30.But if use map,this test only need 70ms.Is this intentional design by the author?

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

    The unordered map uses a certain hashing algorithm and the author has put in testcases that cause collisions to it.

    You can read this for more information.

    So answering your question, yes it is intentional design by the author as the testcases are set in such a way.

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

why tle? D link

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

    int arr [][]= new int [ x ][ y ];

    Constraints: $$$1 \le x, y \le 10^9$$$

    You can't just create such a big matrix.

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

in G, why do we need this condition? It is guaranteed that the sum of ci for all test cases does not exceed 4⋅1000000.

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

https://codeforces.me/contest/1931/submission/246604571

Please help, I am getting TLE for problem D test 5. My code works by iterating k to find (a[i]+yk) % x == 0, a[i]+yk<=a[n-1]. Is it possible to make this solution faster?

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

What does 'tout' mean in problem F's answer? Can't understand

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

Getting RUNTIME_ERROR (Exit code is -1073741819) on large inputs for this solution https://codeforces.me/contest/1931/submission/246676323 for Problem E. Does anyone know what am I doing wrong here?

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

    I tested your code and I think error occured when you sort vector b.

    This is an AC submission based on your code. 247704863

    I don't know what wrong on your code too (maybe Segment fault?).You can make some further study.

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

Question — 1931D

My solution on external java compiler is giving the correct result, but the codeforces judge is saying wrong answer. I am frustated as i cannot find the problem. Plz someone review my code and tell show me the problem:

import java.util.*;

public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0){ int n=sc.nextInt(); int x=sc.nextInt(); int y=sc.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++) arr[i]=sc.nextInt(); int count=0; HashMap<Integer, HashMap<Integer, Integer>> hm=new HashMap<>(); for(int j=0;j<n;j++){ int a=(x-arr[j]%x)%x; if(hm.containsKey(a)){ HashMap<Integer, Integer> hy=hm.get(a); if(hy.containsKey(arr[j]%y)){ count+=hy.get(arr[j]%y); } } if(!hm.containsKey(arr[j]%x)){ hm.put(arr[j]%x, new HashMap<>()); } HashMap<Integer, Integer> hy=hm.get(arr[j]%x); if(!hy.containsKey(arr[j]%y)){ hy.put(arr[j]%y, 1); } else hy.put(arr[j]%y, hy.get(arr[j]%y)+1); } System.out.println(count); } } }

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

My solution is giving the correct result on my external compiler but the codeforces judge is getting wrong answer. I am frustated looking for the problem. Can someone plz show me the problem with my code?

https://codeforces.me/contest/1931/submission/246796190

246796190

import java.util.*;

public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0){ int n=sc.nextInt(); int x=sc.nextInt(); int y=sc.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++) arr[i]=sc.nextInt(); int count=0; HashMap<Integer, HashMap<Integer, Integer>> hm=new HashMap<>(); for(int j=0;j<n;j++){ int a=(x-arr[j]%x)%x; if(hm.containsKey(a)){ HashMap<Integer, Integer> hy=hm.get(a); if(hy.containsKey(arr[j]%y)){ count+=hy.get(arr[j]%y); } } if(!hm.containsKey(arr[j]%x)){ hm.put(arr[j]%x, new HashMap<>()); } HashMap<Integer, Integer> hy=hm.get(arr[j]%x); if(!hy.containsKey(arr[j]%y)){ hy.put(arr[j]%y, 1); } else hy.put(arr[j]%y, hy.get(arr[j]%y)+1); } System.out.println(count); } } }

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

thanks for the problem E! really enjoyed solving it :)

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

Can G use dp?

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

#include<bits/stdc++.h> using namespace std; void solve(){ int n; cin>>n; vectorv(n); for(auto &i:v) { cin>>i; } if(n==1) { cout<<"yes\n"; return; }

long long sum=0;
for(auto i:v)
{
    sum+=i;
}
int req=sum/n;
int flag=0;
long long exc=0;
for(int i=0;i<n;i++)
{
    if(v[i]>=req)
    {
        exc+=(v[i]-req);

    }
    else{
        int req_am=req-v[i];
        if(exc>=req_am){
            exc-=req_am;
        }
        else{
            cout<<"no"<<endl;
        }
    }
}
cout<<"yes\n";

}

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

not run all test case

problem name = B.Make Equal

help me for run it

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

In E can somebody explain why have we used ans -1 instead of ans.

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

    ans : the amount of digits that we have in final number.

    but how many digits does $$$10^m$$$ have ? It's $$$m+1$$$.

    So we need to check if ans >= m+1 ,ans it's the same as ans-1 >= m.

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

1931C can anyone tell me there is i>=1 that means first index of the array is not changeable in order to make the whole array equal . all the other elements of array needs to be equal as first index isn't it ?

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

    select three integers i, j, x(1≤i≤j≤n)

    I think array index range from 1 to n , not 0 to n-1 , and it's ok. first element's index is 1.

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

Can somebody pls help to identify the cause of runtime err in my soln : https://codeforces.me/contest/1931/submission/248125344

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

In tutorial for D., why is the condition for y not the same as the condition for x? Since it a[i] - a[j] is either equal to y or 0 as well.

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

Can someone tell error in my code is gives WA on 3rd test case

void solve() {
    int n, m;  
    cin >> n >> m;
    vi v(n);    input(v);
    vector<pair<int,string>> zeroes;
    int cnt = 0;

    for(int i =0; i < n ; ++i){    
        string s = to_string(v[i]);
            if(s[s.size()-1] != '0'){
                cnt += s.size();
                continue;
            }
        int ending_zeroes = 0;        
        for(int j = s.size()-1; j >= 0 && s[j] == '0' ; --j){
            ending_zeroes++;
        }
        pair<int,string>temp;
        temp.first = ending_zeroes;
        temp.second = s;
        zeroes.push_back(temp);
    }
    sort(all(zeroes), greater<pair<int,string>>());
    for(int i =0; i < zeroes.size() ; ++i){
        if(i % 2){
            cnt += zeroes[i].second.size();
        }else{
            string s = zeroes[i].second;
            for(int j = 0; j < s.size() && s[j] != '0' ; ++j ){
                cnt++;
            }
        }
    }
    if(cnt >= m+1){
        cout << "Sasha";
    }else{
        cout << "Anna";
    }
    cout << endl;
}
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whenever i will be asked for quality,i would reply 1931F

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

Another approach for F

For every pair of screenshot with the 1st screenshot, iterate through elements of both the screenshots , except the first one and try to form the parent pattern from which it could have been made for these two users. If finally you could get a pattern n-1 times, you can say it is possible else not.

Only 3 cases would arise while iterating , either

  1. a[i] equals b[i] ,

  2. a[i] or/and b[i] equal to the beginning of screenshot i.e the user itself ,

  3. a[i] and b[i] being different and unequal to starting user.

Ofc , a is always the first row and b would change as the consecutive rows after that.

Have a look at my submission: 286579692

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

Another approach for F

For every pair of screenshot with the 1st screenshot, iterate through elements of both the screenshots , except the first one and try to form the parent pattern from which it could have been made for these two users. If finally you could get a pattern n-1 times, you can say it is possible else not.

Only 3 cases would arise while iterating , either

  1. a[i] equals b[i] ,

  2. a[i] or/and b[i] equal to the beginning of screenshot i.e the user itself ,

  3. a[i] and b[i] being different and unequal to starting user.

Ofc , a is always the first row and b would change as the consecutive rows after that.

Have a look at my submission: 286579692

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

problem c I think there is a slight error in it

9

9 9 2 9 2 5 5 5 3

in this testcase and according to the text of problem c

we can choose 2 indices i and j where (i <= j)

so the answer is supposed to be 6 but it is 7