kevinsogo's blog

By kevinsogo, history, 5 years ago, In English

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

  • Vote: I like it
  • +99
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1281/submission/66931104

»
5 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Can we print the pairs? 1281E

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it
    Counterexample
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.)

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1281/submission/67296667

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need detail explanation of DIV2 C SEE HERE

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

UPD : Solved!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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