O--O's blog

SPEEDFORCES
By O--O, history, 2 years ago, In English

Hello, Codeforces.

Contest: SpeedForces

Time: [contest_time:418314]

Writer: O--O

Tester: JOIN_GROUP, E404_Not_Found, psychobot

You will have 8 problems in 120 minutes.

Problems are very interesting and problem statements are short.

Problem C and D had little mistakes in statement.

Problem F had mistake in sample.

Winners

1. Kirill22

2. Svyat

3. huangxiaohua

4. Kniaz

5. wery0

6. bitset

Did you like the contest?

Solutions are opened.

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

Comments Comments (38)
| Write comment?
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

As a tester, nice problems. I recommend to participate.

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

what the problem rate for this contest?

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

I like your contests! (Mathforces was good)

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

What about the score distribution?

→ Reply
»
2 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I will write it.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Are you sure that everything is fine with problem F?

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

Thanks for Saturday's workout!

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I saw D on codeforces

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you share Problem H solution? I thought of a solution involving set, however, seemed too complicated to implement, especially for 1 second execution time.

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

    My solution was to iterate k, and maintain a data structure for the products a[i]*a[j] for j < k. For each k, you can iterate p, and query the data structure for the number of pairs a[i]*a[j] <= x / (a[k]*a[p]). The complexity should be O(N^2 log N).

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

Condition F says that $$$n \ge 1$$$, but in test 4 $$$n=0$$$.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shit of piece, not a contest. Only idiots will give penalty for WA on first test. Testers are also silly noobs — missed obvious bug in checker in F. Author is so lazy, that decided not write validator for tests, resulting $$$0$$$ appeared in fourth test in F.

SHITOFPIECEOFSHIT!

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

    Thanks bro

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

    Why so rude bro? Mashup contests will give penalty for WA on first test by default and the author can't change this setting, Also do not write any comment with alt account, at least be brave for writing your comments with real account. wery0

    → Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In problem D, does the player have to delete all the substrings or just one? If s = "abababa" and t = "aba", does s become "b" after the 1st move or a player can choose? Why wasn't it specified in the statement or at least in samples?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it 
ll p = 1000005;
ll dp[p];
for(int i=0;i<p;i++){
  dp[i] = INT_MAX;
}
dp[1] = 0;
for (int i=2; i<p; i++) {
   dp[i] = dp[i-1]+1;
   for (int j=2; j<10; j++) {
       if (i % j == 0) {
            dp[i] = min(dp[i], dp[i/j]+j);
       }
   }
}

Link to sol: Soln

In problem E, just traversing inner loop from 2 to 10 passed the test cases. Just wanted to make sure if there is some logic behind this ? Since in the ideal solution, we should have checked for more than that, as given below

ll p = 1000005;
ll dp[p];
for(int i=0;i<p;i++){
  dp[i] = INT_MAX;
}
dp[1] = 0;
for (int i=2; i<p; i++) {
    dp[i] = min(dp[i], dp[i-1]+1);
    for (int j=2; j*i<p; j++) {
        dp[i*j] = min(dp[i*j], dp[i]+j);
    }
}

Link to sol: Soln

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because we can construct a small answer as the upper bound.

    For example $$$n=131071=(11...11)_2=2^{17}-1$$$,we can construct a scheme:

    $$$*2 \rightarrow +1 \rightarrow...(16 times)$$$

    We can simply see that the upper bound of the answer is $$$3 \lceil log_2(n) \rceil$$$.

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

I used segment tree in problem B, and ACed, but felt it was kinda dumb. Anyone thought of anything smarter?
my submission: [submission:186634062]

Help pls :P
thanks in advance.
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Just keep array elements (let's call each element as $$$a_{i}$$$) and the value of xor of all elements (let's call it $$$X$$$), then after each query do this : Do $$$X$$$ xor $$$a_{i}$$$, after that replace $$$a_{i}$$$ with the integer given in query, and then do $$$X$$$ xor $$$a_{i}$$$ and print the answer. The point is when you xored a number and you want to remove it from xor you should xor with that number again, cuz it's like when you xor even times with a number, it's like you haven't added it to xor.

    → Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

Find smallest $$$k$$$ that $$$\log_x k=\sqrt[x]k$$$.

Wait... when $$$x=4$$$ shouldn't $$$k=16$$$ be smaller?

Did I misunderstand something?

Upd: I didn't see $$$=x$$$.

Upd2: nifek said that there was no $$$x$$$. It seems that O--O your team need better testers!

Upd3: I'm really curious about it is something wrong with the statement or with the solution.

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

    = x as well, that wont be = x

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

      Sorry, I didn't see that.

      Sorry for wasting your time.

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

        The author edited the statement, you were correct, there was no = x

        O--O please at least give credit to those who find mistakes in your problems and dont make them look dumb, stop just silently editing

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

          I think = x made the problem very obvious, so maybe he decided not to include it.

          Although, he should clarify this himself.

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

      didn't see =x at first either.

      but now if consider =x, shouldn't that k be unique? how about smallest

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

Any one better idea for F? Im getting TLE

My solution: https://codeforces.net/submissions/_Aryan_#

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do find more updates on these unrated contests?

→ Reply