Codeforces Round #169 (Div. 2)

12 лет назад, # ^ |

← Rev. 2 →

this issue has been discussed many times.

you should use generator.

→ Ответить

ymondelo20

12 лет назад, # ^ |

Not available, at least for this contest.

→ Ответить

Metamorphus

12 лет назад, # ^ |

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	printf("200000 200000\n");
	for (int i = 0; i < 199999; i++)
	{
		printf("200000 ");
	}
	printf("200000\n");
	for (int i = 0; i < 200000; i++)
	{
		printf("1 447\n");
	}
	return 0;
}

I sent this test to hack one solution of task C and got the incorrect test verdict with the message: FAIL Expected integer, but "#include" found (stdin) [validator validator.exe returns exit code 3]. Can someone say what's wrong?

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

+27

You submited it as test, not test generator. So it was got to validator as is. #include, which is first token is not an integer. Message informs you about it.

→ Ответить

bohuss

12 лет назад, # ^ |

There are tabs for that purpose ;)

→ Ответить

12 лет назад, # |

Nice problems, Unfortunately I misread problem B so that I didn't solve it until last 15mins.

anyway I enjoyed the contest :)

→ Ответить

olive

12 лет назад, # ^ |

yeah, same here. but still a good contest with clear problems.

→ Ответить

12 лет назад, # |

I submitted problem C a lot of times, but every time judge gave Wrong answer on test case number one. As test number one is same as given in the sample input , I checked on my computer. It was working fine.

I could not even run my code on custom test because Custom test did not work properly and issued an error : Form elements must not have name or id of "submit".

Could anybody tell me what the problem could be ??

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

did you make sure that you give your variables and arrays initial value 0 ?

→ Ответить

12 лет назад, # ^ |

All the arrays were globally declared. I am only using the indices of the array on which I am overwriting data.

Do I explicitly need to make all the global variables zero ??. I think they are zero by default.

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

I don't know why this is happening to you,

but sometimes I face the same problem so I give zero value to arrays and it will be solved

→ Ответить

12 лет назад, # ^ |

I am not able to use custom test due to error "Error: Form elements must not have name or id of "submit".".

It gave output 21 on the test case no one as shown in the final tests. I really do know why it showed output 21 ??

→ Ответить

12 лет назад, # ^ |

In your compare function, what happens if a.value != b.value and a.type != b.type?

→ Ответить

12 лет назад, # ^ |

Oh yes, this is where the actual problem lies. It was somehow working fine on my computer. Thank you very much :)

→ Ответить

Hedayet

12 лет назад, # ^ |

I suggest you to test your code on custom test to see how it works on CF Compiler. I faced the same issue earlier and they told me to do it when I asked in clarification.

→ Ответить

HIR180

12 лет назад, # |

I think these problems are very good without problem statement of B. I'm not good at English, so I used translate system. But I couldn't understand problem B at all. I wish there had been an explanation for samples...

→ Ответить

Fcdkbear

12 лет назад, # |

+60

Всем привет:) Так как пост про раунд по определенным причинам мне запостить не удалось, напишу кое-что здесь.

Во первых, я традиционно хотел бы поблагодарить MikeMirzayanov за созданную систему, Delinur за перевод задач, и, конечно же, Gerald за огромную помощь на всех этапах подготовки контеста.

Надеюсь, вам понравились задачи:)

→ Ответить

nhandi

12 лет назад, # |

← Rev. 2 →

I DP problem C but it seems like there is a trick for this problem :(

→ Ответить

12 лет назад, # ^ |

this is not DP.

you should see the indexes that has most frequent and assign the biggest numbers to this indexes.

it's Greedy.

→ Ответить

nhandi

12 лет назад, # ^ |

← Rev. 2 →

I have Solved it by using DP, you should see my code! :)

→ Ответить

12 лет назад, # ^ |

maybe there is DP solution, but I see that greedy is easier.

→ Ответить

LashaBukhnikashvili

12 лет назад, # ^ |

← Rev. 2 →

You have one solution,how i saw(nhandi,kingofnumbers) and you are talking about different solutions

→ Ответить

12 лет назад, # ^ |

I am not able to read his solution because of strange language but my solution is not DP!

→ Ответить

zulkan

12 лет назад, # ^ |

← Rev. 2 →

non dp : for(int i=0;i<=n;i++){ w+=ct[i]; ct2[i]=w; }

his dp : c[0] := 0; for i := 1 to n do c[i] := c[i — 1] + d[i];

he just store what he found before in c[i]; while on the other hand (on non dp), we just need one variable w to store the previous value

→ Ответить

NiVeR

12 лет назад, # ^ |

It is the same solution for both of you, and it's greedy :)

→ Ответить

12 лет назад, # ^ |

Yes, it's not DP.

→ Ответить

12 лет назад, # |

3184317

→ Ответить

Algiz

12 лет назад, # |

TL по E на 70-м тесте — это не круто!

→ Ответить

boleyn.su

12 лет назад, # |

+12

It is the first time that I solve all the problems in a Codeforces Round! THX!

→ Ответить

zulkan

12 лет назад, # ^ |

you should try div2 contest more often :D

→ Ответить

PetarV

12 лет назад, # |

Here's an unofficial editorial: http://www.codeforces.com/blog/entry/6778

Great round!

→ Ответить

YuukaKazami

12 лет назад, # |

+45

OMG someone fake me

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

there is a different one letter :)

→ Ответить

havaliza

12 лет назад, # ^ |

+10

It's different in all letters, If you use a strict checker. :D

→ Ответить

12 лет назад, # ^ |

+16

I think, they have to ban him

→ Ответить

wjmsbmr

12 лет назад, # ^ |

What about your ID? XD

→ Ответить

12 лет назад, # ^ |

+14

Someone took egor, I take that login name everywhere, but I couldn't do it here. So I liked someone has that number, so I took it too.

→ Ответить

tourist50216

12 лет назад, # ^ |

me too me too~~~~~

→ Ответить

12 лет назад, # ^ |

← Rev. 3 →

You are fake!

UPD: Oh, may be you aren't. tourist50216

→ Ответить

12 лет назад, # ^ |

I can't believe that it's coincidence that new three users have similar names in one contest.

this is not coincidence, this is happening on purposes.

furthermore both have the same number 50216 !!

→ Ответить

Icemore

12 лет назад, # ^ |

I always wanted to ask, does your nickname means anything or it's just random letters?

→ Ответить

rdik

12 лет назад, # ^ |

← Rev. 2 →

What about this one(WJMZ8MR)?

→ Ответить

cssystem8

12 лет назад, # ^ |

He is my schoolmate.

→ Ответить

WJMZ8MR

12 лет назад, # ^ |

Absolutely I'm not the real one :( (I hope I was.)

→ Ответить

adityasinghhh

12 лет назад, # |

Can someone explain why my solution http://codeforces.net/contest/276/submission/3189675 gives output '141517992919' on Codeforces compiler and '9382' on my compiler (which is the expected answer)? I am using i686-apple-darwin11-llvm-g++-4.2 compiler.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

On this test your program produces

/usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/debug/vector:336:
    error: attempt to subscript container with out-of-bounds index 65, but     
    container only holds 65 elements.

Objects involved in the operation:
sequence "this" @ 0x0x8058170 {
  type = NSt7__debug6vectorIiSaIiEEE;
}

→ Ответить

adityasinghhh

12 лет назад, # ^ |

Where did you see this error?

→ Ответить

12 лет назад, # ^ |

+14

I use the _GLIBCXX_DEBUG macro locally, it adds range checks and stuff to the standard containers.

→ Ответить

12 лет назад, # ^ |

On my computer it also gives output 9832. I do not why this is happening. Same is happening with me in problem C with test case number 1. :(

→ Ответить

rituranjna

12 лет назад, # ^ |

I have same problem with problem — C . My solution 3189369 failed on Test-3 ( According to Codeforces ) , But its giving expected 9382 on my pc( Ubuntu-12.04 ).

When i tested here , its giving different result . Can anybody help me to point out errors in my code ..?

→ Ответить

12 лет назад, # |

← Rev. 2 →

-17

Как в С++ функцию xor (^) испольовать для long long? Я пробовал возвращает только int.

В чем разница между long long и __int64?

→ Ответить

12 лет назад, # ^ |

+12

Ни в чём: http://msdn.microsoft.com/en-us/library/cc953fe1.aspx "long long Equivalent to __int64." Разве что __int64 совсем нестандартный.

Оператор ^ работает для long long так же, как и для других целочисленных типов.

→ Ответить

BekzhanKassenov

12 лет назад, # ^ |

← Rev. 2 →

У меня ^ сработал нормально для long long. А разницы между __in64 и long long нет. В каком-то заголовочном файле прописана такая строка #define __int64 long long

→ Ответить

12 лет назад, # ^ |

А функция сдвига (<< и >>) не работает для long long?

l = 1 << 40;
cout << l << ' ';

Вывод: 0.

→ Ответить

sdryapko

12 лет назад, # ^ |

работает, просто правильно писать l = 1ll<<40;

→ Ответить

http://codeforces.net/contest/276/submission/3188798

12 лет назад, # ^ |

а что значит 1ll?

→ Ответить

sdryapko

12 лет назад, # ^ |

Это значит, что 1 у нас будет не int, а long long. По умолчанию, все целые константы имеют тип int.

→ Ответить

Betlista

12 лет назад, # |

Thanks for the contest, very nice problems, everything clear in the statement. I enjoyed this contest ;-)

→ Ответить

EarlOfDitches

12 лет назад, # |

For fun.

→ Ответить

jariasf

12 лет назад, # |

My submission 3189731 failed for test 20. What's wrong with my code? On my pc it gives the correct answer.

→ Ответить

darkdream

12 лет назад, # |

the problems is very good for me

→ Ответить

avinashtrivedi

12 лет назад, # ^ |

-7

when will rating updated??

→ Ответить

Betlista

12 лет назад, # ^ |

it is now

→ Ответить

erreze

12 лет назад, # |

-21

Funny, the same algorithm gave me TLE in java but not in c++. java -> http://ideone.com/wkFEuE c++ -> http://ideone.com/fsUknS Good Codeforces, nice way of discouraging non-c++ coders on your platform

→ Ответить

12 лет назад, # ^ |

+28

You have to know, that Arrays.sort in Java works in Theta(n^2) time for some arrays of n elements. Learn Java.

→ Ответить

Archon.JK

12 лет назад, # ^ |

sort() in java might degenerate to O(n^2), if it applies on an array of primitive type

→ Ответить

erreze

12 лет назад, # ^ |

So, should I use Integer wrapper? it does not pass either.

→ Ответить

12 лет назад, # ^ |

I recommend you to shuffle array before sorting.

→ Ответить

crazydiv

12 лет назад, # ^ |

Is there any method to confirm if shuffle will always lead to a better performance? Also what exactly could be the cases when the Arrays.sort() leads to O(n^2). I am asking as the description given on official Oracle page is quite blurry.

This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

→ Ответить

NiVeR

12 лет назад, # ^ |

What is the probability that from a given worst case — order of elements, doing shuffle you will obtain the same order? The probability to win lotto is bigger than that :)

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Theoretically you can still hit the worst case after shuffle, but the probability of this event is negligible. You can see the anti-Java-sort testcase generator here.

→ Ответить

dalex

12 лет назад, # ^ |

Actually, my generator is not working properly: recursion's depth is not maximal. There's a bug somewhere but I couldn't find it :(
Nevertheless, it works about 2.5 sec. on Codeforces servers.

→ Ответить

12 лет назад, # ^ |

:-(

I still consider it a very valuable effort.

→ Ответить

AZerone

12 лет назад, # |

Почему это вот эта посылка дает ва 59, и если исключить этот тест полное решение

→ Ответить

egor-belikov

12 лет назад, # ^ |

-11

Может, потому, что этот тест валит это решение? Ваш Кэп.

→ Ответить

rituranjna

12 лет назад, # |

C. Little Girl and Maximum Sum

Whats wrong with my code( 3189369 ) ..??

Its giving correct solution for Test-3 on my pc(Ubuntu 12.04), but it failed . :O Does anybody care to explain it .??

Same code gave different output for Test-3 here :O Can anybody help me ..?

→ Ответить

prakash1529

12 лет назад, # |

For problem B, what is the answer for "aabb" ? Below is what i feel, please correct me

The first player can for palindrome "abba". He takes off 'a'
Second player can form palindrome "bab". He takes off 'b'
First player cannot for a palindrome and hence Second player wins.

But correct official answer says "First". What am i missing ? Can some body explain how First player can win ?

→ Ответить

sd0061

12 лет назад, # ^ |

The first can already reorder the string to a palindrome.

"If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins."

→ Ответить

JABAIY

12 лет назад, # ^ |

← Rev. 2 →

The first player can for palindrome "abba". He is a winner! Second — losе

→ Ответить

idwin

12 лет назад, # ^ |

player wins if he CAN form a palindrome before deleting operation

→ Ответить

12 лет назад, # |

Прав ли я что stl-овский sort в с++ это аналог QuickSort?

→ Ответить

JABAIY

12 лет назад, # ^ |

← Rev. 2 →

sort не совсем QuickSort (но похож). Там и QuickSort, и HeapSort вообщем много намешано...

→ Ответить

12 лет назад, # ^ |

+13

В G++ используется Introsort, который в худшем случае работает за $\text{[math]}$ .

→ Ответить

Akshai

12 лет назад, # |

-8

for problem D... can anyone tell the answer of input is 15 and 17..?

→ Ответить

12 лет назад, # ^ |

It's 31

→ Ответить

madxmad

12 лет назад, # |

-8

Why did this submission generate WA? 3186879

→ Ответить