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

Автор flamestorm, 18 месяцев назад, По-английски

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
  • Проголосовать: не нравится

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

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

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

    Nice!

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

    Or

    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &x : a) cin >> x;
    cout << (set<int>(a.begin(), a.end()).size()==a.size()?"YES":"NO") << '\n';
    

    which I find even simpler.

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

    But the complexity of your algorithm being O(n*log(n))?? It can easily be solved using O(n) using maps. The logic is simple if any number is present more than once then it is impossible to rearrange in increasing order Here is mine: Submission 177430404

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

      complexity of insertion in map is O(log N).

      While in the worst case, the time complexity of insertion in an unordered_map is O(N). So in worst case your solution is O(N*N) not O(N).

      On the other hand if you used map it would be O(NlogN)

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

    I know your solution is correct but here he elaborates to us the idea of the problem not just the solution. great respect

»
18 месяцев назад, # |
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

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

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

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

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

    Consider this case

    BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

    Answer : 'R' Output : 'B'

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

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

BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

Answer : 'R' Output : 'B'

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

    • »
      »
      »
      18 месяцев назад, # ^ |
      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.

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

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

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

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

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

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

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

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

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

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

Video Editorial for Chinese:

Bilibili

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

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

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

Weak pretest in problem F.

»
18 месяцев назад, # |
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

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

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

»
18 месяцев назад, # |
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 ?

»
18 месяцев назад, # |
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 ?

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

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

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

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

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

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

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

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

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

Have a problem with G

176665365

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

Maybe someone has the idea?

»
15 месяцев назад, # |
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

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

Can someone please explain B solution in Java?

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

In problem 1742D, I am getting my 1st test(5th array) wrong which is 31 instead of 10, also i don't know why 10 is the answer for the fifth array, as 15 and 16 are coprime also.

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

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