kevinsogo's blog

By kevinsogo, history, 10 months 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

»
10 months 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.com/contest/1281/submission/66931104

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am getting TLE on test 24. Can anybody help me out? I am unable to remove TLE. https://codeforces.com/contest/1281/submission/66993181

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Add an additional condition in this for loop for (LL i = 0; i < s[p-1]-'0' - 1; ++i) {s+= sub;} to exit when the string length crosses x. This would most probably fix the TLE.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh I completely neglected that, only should take substring when we are appending. Thanks a lot!

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are calling substr in every loop, and it works in O(n), so your solution TLEs. I changed this, and it got accepted.

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

Can we print the pairs? 1281E

»
10 months 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.

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it
    Counterexample
»
10 months 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

»
10 months 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

  • »
    »
    10 months 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$$$.

»
10 months 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

  • »
    »
    10 months 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)

    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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.

»
10 months 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.

»
10 months 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)

  • »
    »
    10 months 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.)

    • »
      »
      »
      10 months 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!

»
10 months 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.com/contest/1281/submission/67296667

  • »
    »
    9 months 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.

    • »
      »
      »
      6 months 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?

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks! I was having the same problem.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanku very much scorpion_guy

»
10 months 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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I can't figure out what is wrong on my problem 67396769, it is pretty much the same idea but it is wrong answer on test 2 (subtest 41). Thanks

»
10 months 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 ?

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months 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)

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A subtree needs to be connected, so for instance if you take the tree with vertices 1, 2, 3 and edges (1 -> 2), (1 -> 3) , then 2 and 3 can't be turned into a subtree because they are not connected without 1

»
10 months 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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D's video tutorial: https://youtu.be/SAPSHUv_zZE

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me in problem 1281B. I am getting wrong answer in test2 testcase41 but I am not getting my mistake as that case is not visible. I am doing similar as in editorial solution sketch. https://codeforces.com/contest/1281/submission/68429120

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

Can someone plese get me any testcase where My Solution fails.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need detail explanation of DIV2 C SEE HERE

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

83188939 Can anyone please help me?

»
5 months 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!

»
3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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