prabowo's blog

By prabowo, history, 3 months ago, In English

Hello Codeforces!

We are going to hold The 2023 ICPC Asia Jakarta Regional Contest.

We invite you to join the online mirror contest 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) on Codeforces. It will be held on Dec/03/2023 07:35 (Moscow time) and will last for 5 hours.

The mirror will be held using ICPC-style scoring with 10 to 13 problems. The problem statements will only be available in English. We encourage participating as a team using only one computer for coding (as in ICPC contests). The mirror will be unrated.

Some useful links:

We hope that you will enjoy the contest. Good luck and have fun!

UPD. The mirror has started! You can also see the public scoreboard of the onsite contest (started 90 minutes earlier) from the provided link.

UPD2. The mirror has ended! You can find the editorial here. The onsite scoreboard will be unfrozen after the closing ceremony. Thank you for participating and we hope that you enjoyed the problemset!

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

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

How to register for team competition?

»
3 months ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

WHY EVERYONE DOWN VOTE ME?

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

I C PnC.

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

Problem solved. Sorry.

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

ICPCount, ICPConstructive

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

Good Problems

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

It seems like there exists a solution for K without additional d&c and only uses FWHT, but I couldn't understand it. Can someone explain it please?

  • »
    »
    3 months ago, # ^ |
    Rev. 5   Vote: I like it +47 Vote: I do not like it

    I'll write this assuming you know how Walsh-Hadamard transform works. If you don't want to, you can use this definition to connect the dots: $$$\displaystyle B_i=\sum_{j=0}^{2^d-1}(-1)^{\texttt{popcount}(i \texttt{&} j)} A_j$$$. Here $$$B$$$ is the forward transform of $$$A$$$, $$$d$$$ is the maximum number of bits, and that's bitwise and in the exponent. The inverse transform is the same, except that we divide everything by $$$2^d$$$ in the end.

    Note that the answer is the constant term of $$$P(x)=\displaystyle\prod_{i=1}^N \left(1+2x^{a_i}\right)$$$ where we define $$$x^i\cdot x^j = x^{i\oplus j}$$$ (bitwise xor). Consider the Walsh-Hadamard transform of $$$1+2x^{a_i}$$$ for some $$$i$$$. The resulting coefficients only take the values $$$1\pm 2$$$. The transform of $$$P(x)$$$ is the elementwise product of the transforms of the $$$1+2x^{a_i}$$$ terms. So you only need to count for each $$$0\leq k < 2^d$$$ the number of $$$1+2x^{a_i}$$$ terms that take each of the coefficients $$$1\pm 2$$$ at the $$$k$$$-th position. This is equivalent to computing the number of $$$a_i$$$ values that have an even/odd number of bits in common with $$$k$$$. Then the corresponding coefficient at $$$k$$$-th position would be something like $$$(-1)^{\texttt{#odd}} 3^{\texttt{#even}}$$$. There are (at least) two ways to do this fast.

    You can do something similar to SOS DP. Define $$$f[i][S][p]$$$ to be the count of numbers in the array with the following property: the parity of their intersection (bitwise and) with the first $$$i$$$ bits of $$$S$$$ is $$$p$$$, while the rest of the bits match $$$S$$$. The transitions are simple, you consider both options for the $$$i$$$-th bit. This was my solution, which doesn't require you to directly apply FWHT.

    Or, you can notice that the Walsh-Hadamard transform of $$$\displaystyle Q(x)=\sum_{i=0}^{2^d-1} c_i x^i$$$ gives us almost the quantity we want, where $$$c_i$$$ is the count of the number $$$i$$$ in the array. The $$$k$$$-th coefficient in the forward transform gives us the value of $$$\texttt{#even}-\texttt{#odd}$$$. Together with the fact that $$$\texttt{#even}+\texttt{#odd}=N$$$, you can derive the required values. I noticed it after a discussion with YouKn0wWho, who solved it this way (and according to whom, a similar problem has appeared somewhere before).

    Both of these approaches lead to an $$$\mathcal O\left (2^d d\right)$$$ solution. One final remark is that you don't need the inverse transform, as the sum of coefficients in the forward transform is the original constant term, times $$$2^d$$$.

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

    TBH, there was an exact same problem in China a few years ago, and various solutions were introduced in the solution.

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

What software is used to make the graphics of the M problem?I would also like to make a picture like this.

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

    I'll be honest, we are using MS PowerPoint :)

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

Can anyone if possible explain the solution of J.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Observe firstly that any newly added node must be a descendant of a node in the $$$L$$$th level or ($$$L-1$$$)th level of the formed bfs tree till now (here $$$L$$$ is the max level of any leaf).

    Imagine building the tree of the array elements from left to right. Let $$$dp(x,y)$$$ denote the number of valid trees formed from the first $$$x$$$ numbers of the array and in which there are $$$y$$$ nodes "eligible" to be a parent of the new node. So they must be some $$$f_1,f_2,....,f_m,g_1,g_2,...,g_{y-m}$$$ where $$$f_i$$$ are in the second last level and $$$g_i$$$ are in the last level (according to the in-order traversal). Clearly here $$$g_{y-m}$$$ is the $$$x$$$th element of the array and $$$f_1$$$ is its parent. So if $$$a[x+1] > a[x]$$$, then you can make $$$f_1$$$ as parent of $$$x+1$$$, but if $$$a[x+1]<a[x]$$$ you can't. Moreover if you choose the $$$k$$$th node of the eligible parents as the parent of $$$x+1$$$, the previous $$$k-1$$$ nodes are no more eligible, and for $$$a$$$ to be a valid BFS, the only extra edges that can be made to $$$x$$$th node are with the $$$y-k$$$ eligible parents ahead of its current parent. Thus for $$$a[x+1]>a[x]$$$ you add $$$2^{z-2}dp(x,y)$$$ to $$$dp(x+1,z)$$$ for $$$1\leq z\leq y+1$$$ and for $$$a[x+1]<a[x]$$$, you add $$$2^{z-2}dp(x,y)$$$ to $$$dp(x+1,z)$$$ for $$$1\leq z\leq y$$$. (note that the newly added node would become an eligible parent for further dp). Thus by maintaining prefixes you can solve the problem in $$$O(n^2)$$$.

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

get pseudo contests like these more often

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

can somebody give its tutorial or solution of A

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

    There are multiple ways to solve it. The method i used was some sort of depth first search to traverse the grid. you just start from a node and move to it's neighbors until you've gotten three characters then you add the resulting string to an array. If you do it for all the node you'll bet every possible combinations then you sort and find the minimum to get the final answer

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

Can anyone help me in an OA? I'll pay

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

I am sorry to hear to that

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

The link provided for the editorial is not working.

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

can anyone please explain the soln of M. Triangle Construction?? I don't get the intution. sorry for my poor english!