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

Автор Gol_D, история, 2 года назад, перевод, По-русски

1660A - Вася и монеты

Идея: MikeMirzayanov

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

1660B - Влад и конфеты

Идея: Vladosiya

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

1660C - Получи четную строку

Идея: MikeMirzayanov

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

1660D - Максимальное произведение наносит ответный удар

Идея: Aris

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

1660E - Матрица и сдвиги

Идея: myav, MikeMirzayanov

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

1660F1 - Перспективные подстроки (простая версия)

Идея: MikeMirzayanov

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

1660F2 - Перспективные подстроки (сложная версия)

Идея: MikeMirzayanov

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

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    Can you explain ur solution

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

      in problem I made simple observation that whenever number of negative is greater

      let say r = number of negative in subarray — number of pos in subarray

      if r >0 and r%3 == 0 then subarray will be promissing

      I used divide and conquer to calculate those subarray

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

There is a solution in the f2 order_set or fenw_tree.This is awesome

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

Can anyone please point out for me the difference between these two submissions:

152864441(I used vector and got WA)

152864364 (I used array and got AC)

Thanks in advance!!!

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

    Most likely this is due to integer overflow with arrays.

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

      Can you elaborate more for me ? I'm still confused. Thank you very much!

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

        Look at expression in line 21:

        if((n == 1 && vec[0] > 1) || (vec[n — 1] — vec[n — 2] > 1))

        The condition behind the OR doesn't check for vector size, so for n == 1, then you are evaluating this: (vec[0] — vec[-1] > 1)

        Imagine this input:

        1

        1

        1

        Then:

        (n == 1 && vec[0] > 1) || (vec[0] — vec[-1] > 1)

        (1 == 1 && 1 > 1) || (1 — vec[-1] > 1)

        (true && false) || (1 — vec[-1] > 1)

        false || (1 — ?? > 1)

        So basically you are accessing vec[-1]. Depending on the value in that "illegal" memory position, it may be true or false. Same happens for arr[-1], but you just go lucky there with the memory value there at the time of the submit.

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

Does the solution of F1 take into account the adjacent situation?

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

How can I solve C. Get an Even String with dp ?

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

I think there is a mistake in tutorial for problem C. Instead of used it should be prev.

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

public class A_Vasya_and_Coins {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while(t-->0)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();

            int a1 = a*1;
            int a2 = b*2;

            if(a==0)
            System.out.println(1);
            else 
            {

            int ans = (a1+a2) + 1;

            System.out.println(ans);
            }


        }
    }
}

nice

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

Can someone give me the DP solution of number C? I think it will help me get intuition faster to this types of problems.