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

Автор kevinsogo, история, 4 года назад, По-английски

I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive.

Interestingly, in the onsite ICPC round, while "Kirchhoff" got several accepted solutions, "Miss Punyverse" got no accepted submissions at all! It is the reverse here. (Kirchhoff even has a trickier output format in the onsite round compared to the version presented in Codeforces.) It seems the ICPC scoreboard really affects the results greatly; what the top few teams are working on influences what everyone else will be working on.

I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is not the hardest problem in the round!

1281A - Suffix Three

Solution Sketch
Accepted Code

Accepted Submission: 67015948

1281B - Azamon Web Services

Solution Sketch
Accepted Code

Accepted Submission: 67049609

1281C - Cut and Paste

Solution Sketch
Accepted Code

Accepted Submission: 67016113

1281D - Beingawesomeism

Solution Sketch
Accepted Code

Accepted Submission: 67016167

1281E - Jeremy Bearimy

Solution Sketch
Accepted Code

Accepted Submission: 67020743

1281F - Miss Punyverse

Solution Sketch
Accepted Code

Accepted Submission: 67016189

1280E - Kirchhoff's Current Loss

Solution Sketch
Accepted Code

Accepted Submission: 67016199

1280F - Intergalactic Sliding Puzzle

Solution Sketch
Accepted Code

Accepted Submission: 67026155

Разбор задач Codeforces Round 607 (Div. 1)
Разбор задач Codeforces Round 607 (Div. 2)
  • Проголосовать: нравится
  • +99
  • Проголосовать: не нравится

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

Can somebody help me why my submission to Div2 C that is Div1 A is getting TLE on test 6 when I am using similar thing as the editorial

https://codeforces.com/contest/1281/submission/66931104

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

Can we print the pairs? 1281E

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

For problem 1281F/1280D, why is 67027127 incorrect?

Explanation: this submission closes all partition at the subtree instead of open it. It tries to either union the partitions from the $$$u$$$ subtree and $$$v$$$ subtree, or merge the top partitions from subtree $$$u$$$ and $$$v$$$ together.

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

Here is my implementation of Div1 D, which I think is easier to understand than the one given in the editorial: 67036054

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

Can somebody tell me, why am I getting TLE in this? Problem C

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

    c=s.substr(pos+1); is unnecessary when times==0. You are obtaining a substring, only to find out later that you have to work on it $$$0$$$ times. That's a waste. Handle this and get an $$$AC$$$.

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

I tried my best but I am not able to understand why 67059551 for problem Div2 C gives MLE and also Why 67057569 solution for same problem is giving TLE. please help

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

    For the TLE, I think it is because substr is linear time in the length of the string, and you are potentially calling it quite a lot. If a string is of length close to x and you keep finding the number '1', then you will delete the right half of the string, then append the right half of the string again and again and again, it could easily be quadratic time complexity. Try only appending to s (never set it equal to sleft)

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

      Thanks for the reply man. I tried what you said but still it gives TLE. heres my 67138033 . Also Could you find reason for MLE.

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

        When you do += on the string s it is going to make a whole new string s, maybe you can use the append method instead.

        Besides that there is a bigger problem in both the TLE and MLE one. You think the if statement is checking if n<x, but in actuality, you are checking if (n mod mod) < x. Hence you are going to go into it a bunch more than you want.

        You should try to make a test generator and run it on some larger test cases (random). Then you can use debug mode or print statements to notice the problem. In this case even a random large test case would have revealed it.

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

Can someone please tell me why my submission for B is giving a WA verdict on test set 2? Here is my submission.

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

Can somebody help, I still haven't understood why the complexity of problem 1281F/1280D is O(n^2)

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

    Hi! I wrote this training material for our IOI training camp earlier this year: https://drive.google.com/open?id=1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY. A proof is given in Section 4.2, "Tree convolution DP", and also in the appendix. (It is only shown for the case of binary trees, but it can be extended to general trees by looking at the binary tree of "recursive calls" instead of the actual tree.)

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

      Hello kevinsogo, thank you for sharing this DP3 module could you please share DP1 and DP2 modules?

      also in the link you shared, the proof for general trees is left as an exercise, c in f(i, m, c) simply the index of the child we are at right?

      thank you!

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

Can Somebody help me with code of C Cut and Paste it is giving wrong answer on 108th testcase of test 6 but I can't see the testcase so unable to figure out the mistake. Thanks in Advance :) https://codeforces.com/contest/1281/submission/67296667

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

    Hi, when you are doing answer = (answer + (answer-i)*v)%MOD;, your answer is becoming negative and most programming languages don't know how to tackle negative modulo. Do answer = (answer + (answer-i)*v )%MOD; answer = (answer%MOD + MOD)%MOD; and it should work fine.

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

      Why is amswer turning negative anyway? answer, (answer-i), and v should always be positive. So, (answer + (answer-i)*v ) should be positive too.

      Then, when you take the MOD of a (answer + (answer-i)*v ), shouldn't that also be positive?

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

        this is because..lets assume ur answer becomes 1000000010 and i=100, when you will take mod..answer will become 3,so in next iteration i=11,and answer<i,,,,,so answer-i will be negative

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

In Problem C : Can anyone tell me why my solution using string ( Code with string ) gives runtime error but the same code with vector of char got accepted ( Code with vector

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

OK this is probably a dumb question but I'm still gonna ask . In problem D , wouldn't the optimal solution be counting N the number of the nodes where the condition ( number of bees < number of wasps) holds and returning max(m-1,N) ? (In this case , we will consider ALL the nodes where the condition is false to be a single village and consider every node where the condition holds as a single village as well ) Am I missing any details ?

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

    Not sure I understand what you meant, but the villages need to be connected subtrees, so you can't just turn any bunch of nodes into a single village.

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

      Why can't I turn any bunch of nodes into a single village ? (By considering them to be a sub-tree)

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

In 1281E, Can somebody give me a bit more proof why this technique is correct for maximizing and minimizing? And hopefully links to more problems like this one.

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

If anyone need detail explanation of DIV2 C SEE HERE

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

Why this give Memory limit exceeded on test 6. on Div 2C/1A problem link. Can anyone help me out please.;)

UPD : Solved!

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

In Div 2 F/Div 1 D, Can anyone explain how we can get the transition that runs in O(r)? I don't see a better way than to consider all possible ways to split the r regions among this node's children, which is exponential.

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

why is this wrong on testcase 1 4th test?? https://codeforces.com/contest/1281/submission/87028602