tmt514's blog

2024 ICPC Asia Taichung Regional Contest [Online Mirror, ICPC Rules]
By tmt514, history, 4 weeks ago, In English

Hello Codeforces!

I am pleased to invite you to participate in 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams), which will be held on Nov/24/2024 10:05 (Moscow time). This is an online mirror contest for the 2024 ICPC Asia Taichung Regional Contest, and the official offline contest was conducted on November 17th, 2024. The duration of the contest will be 5 hours and the contest is best for teams of three people. The mirror will use the ICPC format.

The contest tasks are proposed by the task authors (baluteshih, waynetuinfor, skylinebaby,samsam2310, hank55663, ltf0501, Jeffrey, Shik, tmt514, Bangye Wu, kasuistry, and Peter Rossmanith), prepared and polished by the judge team (Regional Contest Director Ling-Ju Hung, Chief Judge Peter Rossmanith, kasuistry, Hung-Lung Wang, baluteshih, waynetuinfor, hank55663, cthbst, Sylveon, CindyLinz, marmot0814, tmt514), and tested by the tester team (olmrgcsi, oToToT, jeeeerrrpop, nikilrselvam, Vince729, applepi216). The judges appreciate the testers for their valuable feedback!

We would like to thank MikeMirzayanov for creating the greatest Codeforces platform, and many, many, many helps for making this online mirror contest possible!


This is a photo of the contest venue. Photo Credit: Prof. Jinn-Shyong Yang.

On behalf of the 2024 ICPC Asia Taichung Regional Contest Judge Team, we hope you enjoy this contest and have fun!

Of course, this contest will be unrated.

Updated: the editorial has been released! Please refer to the link in the contest's local website.

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

»
4 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

Spoiler: It is better than last year

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Cheers on the contest! I hope kakaen is not involved.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

As an official participant, the contest is well-prepared

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    as an official participant, inserts duck noise

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will Chinese Statements be offered?

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

    There will be English Statements only.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem M, what is test case 5 :(((((

I wrote the slow solution and made the submission and got TLE on test 7

Then, I tried generate about 200 test case to check but all of test cases passed. So what is test case 5 :( :( :(

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    try this input

    14
0 1 0 1 1 2 1 1 2 2 1 2 1 1
    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution is 106, is it right ?

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        The right answer is 90.sort 0 1 0 and 2 1 1 2 2 1 2 1 1

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          oh thank you so muchhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

          → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem H?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Let's instead solve problem with only inequalities of consecutive elements. Let $$$f_x$$$ be the number of possible sequences of < and > of length $$$x$$$. Then number of ways to choose out of $$$n - 1$$$ total comparisons the $$$x$$$ inequalities is $$$\binom{n-1}{x}$$$. Then the total answer is $$$\sum{f_x \cdot \binom{n-1}{x}}$$$

    Now only inequalities. Let's think, for which sequences of inequalities we can create sequences of elements from $$$1$$$ to $$$k$$$. For example, can we for $$$k = 3$$$ have this sequence: <<><><<<><>?

    The answer
    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      But this condition(The has to be no segments of same signs with length greater than k−1 .) is not enough I guess. For example, k=4 and sequence, <<<><<<

      Here, no segment is present of the same sign with a length greater than 3. But still, it is not a valid sequence.

      Am I missing something?

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

    If you define ai < ai+1 is -1, ai > ai+1 is 1 and ai = ai+1 is 0

    So there was just n — 1 numbers

    You can just count number of array just only 1 and -1 with length x (x <= n — 1). After that, if the array have length x, the final step is just add n — 1 — x zeros to some positions in the array.

    The problem convert to: How many ways to generate an array with just 1 and -1 with length x ? The fact is number of consecutive 1s and -1s is not more than k. Because if you use p numbers 1, after that is -1, so you just make the different is k again.

    And now the problem is easy, just define f[i][0] and f[i][1]: number of arrays with i element and the last is 1 or -1. Just optimize the transition by prefix sum

    → Reply
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Is this the solution to L?

Let $$$S$$$ be the square of the polygon. Let $$$O$$$ be the center of mass. Build another polygon, which is the original one, but reflected across point $$$O$$$. Intersect these to polygons. Let the square of intersection be $$$S_I$$$. Then the answer is $$$S - S_I$$$.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any hint? How to solve cubes?

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

What's the intended solution for K? The minimum chain decomposition is small. If we can find that, the rest would be easy. But is it easy to find?

Update. Apparently, greedily choosing the longest chain each time is sufficient to pass. I am still curious about the intended solution.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Don't be confused, greedily choosing the longest chain is one of our intended solutions! You can prove that this approximates the minimum chain decomposition well. Thus, you can find a small enough number of chains and get Accepted.

    → Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

I don't understand why I'm getting TLE (testcase 23) on my solution, problem M. 293104352

I try every prefix i and for each i I get the best j such that performing the operation prefix_sort(from 0 to i) and suffix_sort(from j to n) the array is sorted. I use ordered_set to find the position of the strictly smaller element in the prefix [0, i] (already sorted) of the smaller element in the suffix [j, n]. This is to find the best j when the smallest element of the suffix is smaller than the biggest element of the prefix. I also used an array cons where cons[j] = j+k such that suffix_sort(from j to n) is the same thing of suffix_sort(from j+k to n) but it is obviously more convenient.

I solve the same problem two times because the above solution works only performing prefix sort first. The second time I solve the problem reversing the input array and multipling it by -1, it could be demonstrated that doing like so we found the best solution performing the suffix sort first.

My solution should be O(N*logN) if I don't miss something. I tried to reduce constant factor as much as possible but nothing.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Using a data structure with a large constant factor can be quite risky when n = 1e6.

    You can refer to my TLE and AC code for comparison; the only difference between them is that I replaced a set with a priority_queue, which resulted in sufficient optimization to get accepted.

    Additionally, I'd like to point out that while my code uses a priority_queue, it can be further optimized to O(n) using a two-pointer approach.

    However, you might want to first explore replacing PBDS with other more efficient data structures. Hope this helps!

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Thank you for the answer, PBDS are more expansive than I thought! For the problem I used a queue and I got AC :)

      → Reply
»
4 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

Will the official tutorial be published?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Please give us some time, it is still in progress...!

    → Reply
»
4 weeks ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

why the answer of this test in problem D is 20

7 15
###############
#S...........T#
#.###########.#
#.............#
#.............#
#..#..#.......#
###############
→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The optimal path here actually is to move down at the start. Since, doing so you can use a pattern such as "RRRDRRRU...", which is more efficient than taking a horizontal line, "RRRLRRRL..."

    A 20 move sequence to solve this case would be: "DDRRRDRRRURRRDRRRUUU"

    → Reply
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the point of modulo in F? Psychological trick??

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the statement of the problem B right? I'm asking because

Spoiler

I'm a little insecure of comment this, because saying that the statement of a problem could not be correct is a little delicated I guess. Please let me know if I misunderstand the statement or I made an error of any kind.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, in the problem description, it is not allowed to use different pin colors in the same row. However, it can be proven that using the formula like what you said in the accepted solution is still correct.

    Your solution program doesn't solve the problem correctly. Any construction given by your solution program will assign the same color in continuous rows, and cannot correctly solve the instance like B=4 W=2.

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

      Ohhh okay, that totally makes sense! Thank you very much

      → Reply
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you provide the editorial?

→ Reply
»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Fun fact: problem A has rating of 1300, which is higher than problem B and problem E

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include<iostream>
#include<vector>
using namespace std;
 
 
int help(int w, int b, int j)
{
   if(w<j and b<j)
   return 0;
   
   int takewhite = 0;
   int takeblack = 0;
   if(w>=j)
    takewhite =  help(w-j, b, j+1);
   if(b>=j)
    takeblack = help(w, b-j, j+1);
    
   return 1+max(takewhite, takeblack);
   
   
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      int w,b;
      cin>>w>>b;
      
      cout<<help(w,b,1)<<endl;
    }
    return  0;
}

Please can anyone help me understand why this DP code is not working for problem B? I want to know is the logic correct? I am getting TLE thats fine but I wanted to know if I am missing something other than the optimization part.

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

    This is not DP, this is just recursion

    The logic is (technically) correct, but not the best/expected.

    Your current program will have exponential time complexity, not sure how to optimize it.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any editorial?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the time complexity in problem C Cubes? I am not able to understand the last simplification there

→ Reply