YocyCraft's blog

By YocyCraft, history, 14 months ago, In English

In yesterday's contest Codeforces Round 865 (Div. 1) I've got the achievement which I could not imagine just half a year ago — reach 2400 rating and become GM.

The first time I learned about CF was on 2022.2, that time I registered this account and took my first contest. But my first submission 146390589 on contest got TLE, and I solved 0 problem in this contest. (At that time I didn't know that's because the efficiency of java.util.Scanner is extremely low) And because I needed to deal with graduation thesis, I didn't use CF until the end of last year, when I restarted CF contest.

At 4th and 5th contests I solved div2D problems to reach blue. In my 9th contest, I first time solved div2E problem in contest, and I became purple in my 12th contest. In my 14th and 15th contest, I solved div2E problems twice and became orange. In the next weeks, I started to hit the upper limit of my skill, and dropped from orange twice.

In order to improve my skill of competive programming, I practiced problems in CF problemset everyday, and when practicing I tried to solve every problem with 2000-2500 difficulty by the reverse order in the problemset. I took part in every rated CF contest (except Codeforces Round 856 (Div. 2) which was timed at 01:35 UTC+8), and learned many new techniques from problems I could not solve in contests. I also used other CP platfroms like atcoder, where I've reached rating 2233.

It seems that practice was pretty effective for me. I got well performance in last 3 contests rated for div1, and first time became red yesterday. Although there's still a large promotion space for me, it's an important meaningful moment in my life of competitive programming. Hope that I will be more active to face the challange in the future.

Thank for MikeMirzayanov and every contributors of CodeForces community for bring me into the world of competitive programming and helping me find the meaning of my life.

Full text and comments »

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

By YocyCraft, history, 15 months ago, In English

See my comment: There's inconsistency in tutorial and solution code of 1661F.

Full text and comments »

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

By YocyCraft, history, 15 months ago, In English

Problem link: 1796E - Colored Subgraphs

When solving this problem I only know how to solve for a fixed root, and it's better to let a leaf node with smaller distance to the nearest node with degree>=3 to be the root, but I don't know how to choose it. So I sort all leaves by there distance, and try first 40 of them to be the root. I've thought it could fail on some large tests but unexpectedly it got AC. Can someone hack this solution or prove it's correctness?

My submission:195462544

Update: My submission has been hacked

Full text and comments »

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

By YocyCraft, history, 16 months ago, In English

Problem link: 1796F - Странные тройки

Let $$$p =$$$ number of digits of $$$n$$$, $$$q =$$$ number of digits of $$$b$$$, we have $$$n=\frac{a \cdot b \cdot (10^{p}-1)}{a \cdot 10^{q}-b}$$$, by checking every pair of possible $$$(a, b, p)$$$ we have a $$$O(A \cdot B \cdot log(N))$$$ solution, but it will get TLE.

We can modify this solution slightly: let $$$c=gcd(a, b)$$$, $$$k=\frac{a}{c}$$$, we have $$$n=\frac{k \cdot b \cdot (10^{p}-1)}{k \cdot 10^{q}-(b/c)}$$$, because $$$gcd(k, k \cdot 10^{q}-(b/c))=gcd(k, b/c)=gcd(a/c, b/c)=gcd(a, b)/c=1$$$, we have $$$k \cdot 10^{q}-(b/c)$$$ is divisor of $$$b \cdot (10^{p}-1)$$$, therefore, by pre-calculate factors for numbers in range $$$[1, 100000]$$$ and in $$${999999, 9999999, 99999999, 999999999}$$$, we can check answer for $$$b$$$ in $$$O(\sigma(b) \cdot 185)$$$, where $$$\sigma(b)$$$ is the number of divisors of $$$b$$$, and $$$185=\sum_{p=1}^{9}\sigma(10^{p}-1)$$$, and we can solve the problem in $$$O(B \cdot log(B) \cdot 185)$$$, but this solution still get TLE due to large constant factor of division and modular operations.

If we let $$$A, B, N$$$ be their maximum value, we can see there are only $$$172104$$$ possible valid tuples can be the answer, so we could solve the problem by hard-coding-- however, each pair of $$$(a, b)$$$ will add about $$$10 \sim 20$$$ bytes to the size of code, and we need $$$2 \sim 3MB$$$ to store all pairs, which exceed the limit of $$$64KB$$$. By printing all valid tuples, we can see that for almost all pairs of $$$(a, b)$$$, the value of $$$a/b$$$ is some integer power of $$$10$$$, and for other pairs, there are only $$$6143$$$ different possible values of $$$b$$$. Therefore, we can hardcode these values (for $$$34KB$$$), and for $$$b$$$ which is not hardcoded, we can only check for $$$a=10^{t} \cdot b$$$ (for every pair of $$$(b, p)$$$ there are only $$$5$$$ possible values of $$$a$$$), then we can solve the problem in $$$2000ms$$$.

My submission: 195426974

Code for generating values of b

Full text and comments »

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

By YocyCraft, history, 16 months ago, In English

Problem link:1785D - Деревянная ложка

First, WLOG we can assume we arrange the tournament in such way: In every matches, the left player wins. We can achieve this by doing the following operation to the binary tree of the tournament: for each non-leaf node of the binary tree, if the winner of this node is its right child, we "flip" this node by swapping its left subtree and right subtree. Since fliping doesn't change the winner of each match, this will not change the "wooden spoon", and after this operation, the "wooden spoon" is the right-most node. Since there are $$$2^{n}-1$$$ nodes in the binary tree, we can merge $$$2^{2^n-1}$$$ situations into one by this operation.

For example, we can do operation to this tree:

_________1

_____3_______1

-__5___3___1___2

__7_5_3_6_1_8_4_2

-->

_________1

_____1_______3

-__1___2___3___5

__1_8_2_4_3_6_5_7

Where $$$1$$$ (the left-most node) is the champion, and $$$7$$$ (the right-most node) is the "wooden spoon".

Then we assume the right-most node is k, and there's $$$dp[n][k]$$$ different arrangements (after operation). If $$$k$$$ is the $$$j$$$-th smallest element in the right half of the tree, then we have $$$\sum_{i=1}^{2^{n-1}}dp[n-1][i]$$$ ways to arrange the left half, and $$$dp[n-1][j]$$$ ways to arrange the right half (since $$$k$$$ is also the right-most node in the right-subtree). But in how many ways we can distribute $$$2^{n}$$$ elements into $$$2$$$ halves? Well, since $$$1$$$ is the left-most element, there are $$$k-2$$$ elements we could put in the right part (which are in the range $$$[2, k-1]$$$), and there are actually $$$j-1$$$ elements of them in the right part, so we have $$$\binom{k-2}{j-1}$$$ ways to choose them. Similarly, we have $$$\binom{2^{n}-k}{2^{n-1}-j}$$$ ways to choose elements from $$$[k+1, 2^k]$$$. Therefore, we can get such formula:

$$$dp[n][k]=\displaystyle \sum_{j=1}^{2^{n-1}}(\displaystyle \sum_{i=1}^{2^{n-1}}dp[n-1][i]) \cdot dp[n-1][j] \cdot \binom{k-2}{j-1} \cdot \binom{2^{n}-k}{2^{n-1}-j}$$$

Then we can calculate them by FFT. The answer is $$$2^{2^{n}-1} \cdot dp[n][k]$$$.

Code example

Full text and comments »

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

By YocyCraft, history, 16 months ago, In English

Don't forget to update the rating of #848 for me later. I was in div1 when registered in this contest, but that's because my negative rating in TypeDB round was rolled back temporarily, and I should be counted as div2 in this contest.MikeMirzayanov

Update: This screenshot is definately contradict with the rule of codeforces rounds. If this won't be fixed, how can I explain this weird result to new users of codeforces?

Full text and comments »

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

By YocyCraft, history, 16 months ago, In English

I've just posted a topic complaining about slow judge, and it received 4 downvotes in just 5 minutes, so I have no choice but to delete it. So could someone tell me is it normal that a submission need to wating for over 10 minutes to be judged?

Update: Now my new submission 191736305 has got AC, but it also has waited for 6 minutes.

Update; Encounter a problem on CF ---> post a blog for asking for it ---> get downvoted by unknown reason ---> be forced to delete the blog to save contribution ---> encounter more problems. How can this vicious cycle be stopped? The greatest disadvantage of CF downvoting system: I will never know the reason I being downvoted.

Update: If you're getting annoyed by this blog, please comment something like "asking for system technical issue is not welcomed on codeforces" instead downvote.

Full text and comments »

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

By YocyCraft, history, 17 months ago, In English

Problem:1713D - Tournament Countdown

My submission in java:189203654 (TLE on test3)

My submission in c++:189201160 _(779ms)(Most part of them are same, expect time cost of IO)

If there are no testers of rounds using java, maybe I should give up.

Full text and comments »

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

By YocyCraft, history, 17 months ago, In English

Will the next div1+div2 round be open for us?

Update: Now the registration has begun.

Full text and comments »

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

By YocyCraft, history, 17 months ago, In English

Today when I upsolving 1768F - Wonderful Jump in which the intended solution is pretty simple. But the time complexity is O(n^1.5) and n=4*10^5 the time limit is pretty strict. I implemented the intended solution in java for many times but I always got TLE. Then I copied the submission 188424856 _(483ms) which is simpler the the official solution, and implemented in java, and got AC for 3322ms (My submission:188904779). It seems that sometimes you must to optimize the solution further than intended.

Also the official judge runs java code much more slowly than on my computer. I tested for cases where a[i]=1+(i%mod), where mod was about sqrt(400000). The code ran for about 0.6s but for the similar cases of the official judge it ran for about 2.3s.

The code for testing time cost on my computer

Full text and comments »

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

By YocyCraft, history, 17 months ago, In English

In the recent educational round, there's a hacking attempt still in "waiting" situation, despite the open hacking phase has ended for 10 hours, which caused system test phase cannot start. Is there any bug of hacking system? Please fix it quickly I'm impatient to be orange

Update: Now rating is updated and finally I've become orange! excited

Full text and comments »

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

By YocyCraft, history, 17 months ago, In English

In 1718C - Tonya and Burenka-179 I implemented a solution with intended complexity (which was O(n*log(n)*PrimeFactorCount(n))), which need a multiset to update the possible answer between queries, and answer the max element of the multiset for each query. But since there's no multiset in java, I had to simulate a multiset by a TreeMap, which caused TLE (my submission:188008030)

I looked at other java solution for this problem and no one got AC. Is this problem unsolvable for java or there's better implementation for multiset?

Full text and comments »

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

By YocyCraft, history, 18 months ago, In English

Today I implemented the intended solution of 1767E

Which unexceptedly got TLE...

Then I tested the sample which input is small (n=10, m=40) and recorded the time consuming of each step in my first solution

I discoverd that when good mask1 of vertex set A (1-m/2) is too much (about 2^19), the preparation of dp takes very long time (about 1000ms on my computer but 1700+ms on official judge)

However, in most of test samples the time consuming is not that much beacuse of a smaller set of good mask1. So I thought about if I permute the number of colors randomly......

In 1st attempt I still got TLE, but after changed the seed of java.util.Random, I got AC in the 2nd attempt

(I know there must be better implementation but I'm lazy QwQ)

Full text and comments »

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

By YocyCraft, history, 18 months ago, In English

Today I got 1700ms after many TLEs in problem 1774F1

submission in java17

Then I submitted the same code in java8 again then got 1352ms

submission in java8

It seems that java8 performs better

Full text and comments »

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

By YocyCraft, history, 18 months ago, In English

No rating update for educational #139

No editorial for div2 #837

Waited for so looooooooooooooooooong time

What happened

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it