thanhchauns2's blog

Solutions for April Fools Day Contest 2023 in one line (Collection)
By thanhchauns2, history, 21 month(s) ago, In English

Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.

P/s: The editorial was published.

1812A - Вы робот?

Solution

1812B - Was it rated?

Solution

1812C - Цифры

Solution

1812D - Тривиальная гипотеза

Solution

1812E - Не задача по геометрии

Solution

1812F - Факторизация

Solution

1812G - Цветовое зрение

Solution

1812H - Ожидаемое твист

Solution

1812I - Скалолаз

Solution

1812J - Не-загадочный язык

Solution
  • Vote: I like it
  • +28
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

After about 300 — 400 steps, a positive number will be decreased down to 1.

Where did you get those numbers from? the conjecture asks whether every positive integer will eventually get to 1 by applying the operation however many times you'd like.

The biggest answer allowed (103 digits) will take more than 3,000 operations to reach 1, but it might take millions, or never reach 1 (proving the conjecture false), which means that the [REDACTED] part must be pretty small, or the grader wouldn't be able to evaluate a very large submission definitively.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here. Or I could remember the wrong number, I watched it a long time ago.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it is around $$$350$$$:

      void solve(){
	int mx = 0;
	for (int n1 = 1; n1 < 100000; n1++){
		int steps = 0;
		for (int n = n1; n != 1; steps++){
			if (n & 1) n = 3 * n + 1;
			else n /= 2;
		}
		mx = max(mx, steps);
	}
	cout << mx << '\n';
}
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's for numbers up to 1e5, we're talking about numbers up to 1e1000

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe the grader can just simulate $$$10^5$$$ ish steps to check if an answer is valid or not. In testing, the best number I could find was around $$$2.5 \cdot 10^4$$$ steps by just randomly generating $$$1000$$$ digit numbers and running them. In any event, it is probably impossible to find a positive integer that could work on the given constraints, and if you could, you could probably write a paper on it!

    → Reply