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

Автор flamestorm, 2 года назад, По-английски

Thanks for participating!

1742A - Sum

Idea: flamestorm

Tutorial
Solution

1742B - Increasing

Idea: mesanu

Tutorial
Solution

1742C - Stripes

Idea: flamestorm

Tutorial
Bonus
Solution

1742D - Coprime

Idea: badlad, SlavicG

Tutorial
Solution

1742E - Scuza

Idea: mesanu

Tutorial
Solution

1742F - Smaller

Idea: SlavicG

Tutorial
Solution

1742G - Orray

Idea: SlavicG

Tutorial
Solution
Разбор задач Codeforces Round 827 (Div. 4)
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

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

B was just a few lines with the help of STL :D (Submission: 176051852)

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

Problem C,When I judge the horizontal and vertical directions of a color,my submission-->175928516, I can't pass the test. But when I only judge the corresponding direction of a color, it passed,my submission-->176020169 Can someone tell me why

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

    Look at the title,some horizontal rows have been painted red, and some vertical columns have been painted blue.

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

      I also didn't read it properly costed me more than an hour to cause it took more than 15 mins to run on pretests :'(

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

    Consider this case

    BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

    Answer : 'R' Output : 'B'

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

for problem C, many of us missed this case :(

BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

Answer : 'R' Output : 'B'

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

    I think the answer should be R, as it has the occurrence 8 consecutive times in a row. Please tell, why are there so many messages related to this?????

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

      Because many of us just checked whether the entire row is same color rather than checking entire row is Red Or Not. This also follow for column also.

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

why is my 176088793 getting WA on 11 (problem D)

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

    when the input array is 2 6 10 15 your output is 0 because when you reach 6 the gcd will be 1 but actually there is no coprime number between 6 , 10 , 15 but it is true that their gcd is 1 The correct output should be 5 by taking 2 and 15

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

I got TLE in problem E. My submission is 176039360 . How can I improve this?

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

    As per your solution I suggest you to have a read on Time Complexity Analysis It would be helpful for you to understand why your code is getting TLE

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

I got TLE on Problem D. Not sure why. How can I improve this solution

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

    Instead of keeping track of every index , you can consider the values of the array elements , that can go up to only 10^3 . Now , if you run two for loops , then time taken O(10^3*10^3) and for T=10 test cases , O(10*10^3*10^3) = O(10^7) [neglecting time complexity for __gcd(a,b) stl ].

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

Video Editorial for Chinese:

Bilibili

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

I think there is an easier way to implement the algorithm in G's tutorial. 176054281

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

Weak pretest in problem F.

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

I am getting the Wrong answer for F on test case 2 .. my submission- here

plz someone help me out ::) I got my mistake

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

sadly, i misread the "OR" as "XOR" and failed to ak

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

flamestorm is the solution of bonus of problem C like this :

we go through each row except the ones with full red then check whether if a column is painted blue whether it is painted red in any of the previous rows and if a column is painted red whether it is painted blue in any of the previous rows and if a column is white whether it is painted blue in any of the previous rows; If any of these three happens then input grid is invalid otherwise valid

Is it correct ?

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

Hey flamestorm,

In problem C, the valid input must contain exactly one of theses situations:

1- Have one or more rows full of R's

2- Have one or more columns full of B's

otherwise, the input is invalid

Is it correct ?

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

    Well, those are a part of the conditions, but there seems to be more invalid cases to consider. The following is one example.

    .B.BB...
    .B.BB...
    .B.BB...
    RBRRBRRR
    RBRBRRRR
    .B.BB...
    .B.BB...
    .B.BB...
    
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      I don't see any reason of downvoting him , he made a correct point.Maybe he has bad record in past in terms of commenting & posting but that doesn't have any relation with this,And why am I saying this? I am saying this because we all make mistakes in life ,doesn't mean we can't move forward

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

I got TLE in F question for Test Case #2, any ideas/hints how can I improve the code? submission

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

In problem D I have gotten wrong answer on test 24 on an invalid test int the statement they said that n must be greater than 2 but I have had wrong answer on a test with n=1 so please rejudge the problem SlavicG , mesanu , flamestorm please do something 175973439 .

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

In $$$C$$$, why didn't they put $$$n$$$ and $$$m$$$ $$$(1$$$ $$$\le$$$ $$$n,m$$$ $$$\le$$$ $$$1000)$$$ or something like that?

I think when $$$n=m=8$$$ problem is more like Div.4 $$$B$$$ problem, this could make problem $$$C$$$ little harder, just as hard as a Div.4 $$$C$$$ should be.

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

In Problem B, the checker log is telling me that I gave a wrong answer in test case #2 while my answer is the same as the output. As you can see in the submission, the 25th token is correct. Am I missing something? 176210112

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

    Your code is dereferencing the value of $$$a[n]$$$. This is undefined behaviour, and may have caused a WA any moment.

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

Have a problem with G

176665365

but the test is really huge and I can catch the problem/

Maybe someone has the idea?

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

I guess I didn't understand F correctly...

The is the 10th test:

1
5
2 1 bb
1 2 b
2 3 b
1 2 c
2 3 bcdbweakpretests

Official answer is:

YES

YES

YES

YES

YES.

Why it isn't:

YES

NO

YES

NO

YES?

UPD: solved it

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

251250861 whats wrong with my code it gives the correct output in the editor

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

For Solution D

We just have to store the value of index to the key of the vector as the for loop is progressing it generally stores the largest index value.

for(int i = 1; i <= n; ++i) { int x; cin >> x; id[x].push_back(i); // we can actually store id[x]=i+1; }